Алгоритмы и структуры данных

Основные определения теории графов

• Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
• Лемма о рукопожатиях
• Ориентированный граф
• Вариант леммы о рукопожатиях для ориентированного графа
• Теорема о существовании простого пути в случае существования пути
• Теорема о существовании простого цикла в случае существования цикла
• Матрица смежности графа
• Связь степени матрицы смежности и количества путей
• Матрица инцидентности графа
• Циклическое пространство графа
• Фундаментальные циклы графа
• Дерево, эквивалентные определения

Связность в графах

• Отношение связности, компоненты связности
• Отношение реберной двусвязности
• Отношение вершинной двусвязности
• Граф компонент реберной двусвязности
• Граф блоков-точек сочленения
• Точка сочленения, эквивалентные определения
• Мост, эквивалентные определения
• k-связность
• Теорема Менгера
• Вершинная, реберная связность, связь между ними и минимальной степенью вершины

Остовные деревья

• Матрица Кирхгофа
• Связь матрицы Кирхгофа и матрицы инцидентности
• Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
• Количество помеченных деревьев
• Коды Прюфера

Обходы графов

• Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
• Покрытие ребер графа путями
• Алгоритм построения Эйлерова цикла
• Произвольно вычерчиваемые из заданной вершины графы
• Гамильтоновы графы
• Теорема Хватала
• Следствия теоремы Хватала:
  • Теорема Дирака
  • Теорема Оре
• Турниры
• Теорема Редеи-Камиона

Укладки графов

• Укладка графа на плоскости
• Формула Эйлера
• Непланарность [math]K_5[/math] и [math]K_{3,3}[/math]
• Укладка дерева
• Укладка графа с планарными компонентами реберной двусвязности
• Укладка графа с планарными компонентами вершинной двусвязности
• Теорема Понтрягина-Куратовского
• Двойственный граф планарного графа

Раскраски графов

• Раскраска графа
• Двудольные графы и раскраска в 2 цвета
• Хроматический многочлен
  • Хроматический многочлен полного графа
  • Хроматический многочлен пустого графа
  • Хроматический многочлен дерева
  • Рекуррентные формулы для хроматических многочленов
  • Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность
• Формула Зыкова
• Формула Уитни

Обход в глубину

• Обход в глубину, цвета вершин
• Лемма о белых путях
• Использование обхода в глубину для проверки связности
• Использование обхода в глубину для поиска цикла в ориентированном графе
• Использование обхода в глубину для топологической сортировки
• Использование обхода в глубину для поиска компонент сильной связности