Алгоритмы и структуры данных — различия между версиями
(Обновление тем до состояния на 07.10.2010) |
(→Остовные деревья) |
||
| Строка 31: | Строка 31: | ||
* [[Связь матрицы Кирхгофа и матрицы инцидентности]] | * [[Связь матрицы Кирхгофа и матрицы инцидентности]] | ||
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] | * [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] | ||
| − | * [[Количество помеченных | + | * [[Количество помеченных деревьев]] |
* [[Коды Прюфера]] | * [[Коды Прюфера]] | ||
| − | |||
== Обходы графов == | == Обходы графов == | ||
Версия 21:52, 8 октября 2010
Содержание
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Ориентированный граф
- Вариант леммы о рукопожатиях для ориентированного графа
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- k-связность
- Теорема Менгера
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
Остовные деревья
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Обходы графов
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие ребер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Гамильтоновы графы
- Теорема Хватала
- Следствия теоремы Хватала:
- Турниры
- Гамильтоновы турниры
- Теорема Редеи-Камиона
