Алгоритмы и структуры данных — различия между версиями
(Новая страница: «== Основные определения теории графов == * [[Основные определения теории графов|Основные опр…») |
(Добавлена тема "Укладка графов") |
||
| Строка 42: | Строка 42: | ||
* [[Алгоритм построения Эйлерова цикла]] | * [[Алгоритм построения Эйлерова цикла]] | ||
* [[Произвольно вычерчиваемые из заданной вершины графы]] | * [[Произвольно вычерчиваемые из заданной вершины графы]] | ||
| + | * [[Гамильтоновы граф]] | ||
| + | * [[Теорема Хватала]] | ||
| + | * [[Следствия теоремы Хватала: теорема Дирака, теорема Оре]] | ||
| + | * [[Турниры]] | ||
| + | * [[Гамильтоновы турниры, теорема Редеи-Камиона]] | ||
| + | |||
| + | == Укладки графов == | ||
| + | * [[Укладка графа на плоскости]] | ||
| + | * [[Формула Эйлера]] | ||
| + | * [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] | ||
| + | * [[Укладка дерева]] | ||
| + | * [[Укладка графа с планарными компонентами реберной двусвязности]] | ||
| + | * [[Укладка графа с планарными компонентами вершинной двусвязности]] | ||
| + | * [[Теорема Понтрягина-Куратовского]] | ||
| + | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
Версия 06:20, 1 октября 2010
Содержание
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Ориентированный граф
- Вариант леммы о рукопожатиях для ориентированного графа
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- k-связность
- Теорема Менгера
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
Остовные деревья
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьв
- Коды Прюфера
Обходы графов
- Эйлеров цикл, Эйлеров путь
- Эйлеровы графы
- Эйлеровость орграфов
- Покрытие ребер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Гамильтоновы граф
- Теорема Хватала
- Следствия теоремы Хватала: теорема Дирака, теорема Оре
- Турниры
- Гамильтоновы турниры, теорема Редеи-Камиона
