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

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

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

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

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

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

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

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

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