Глава 4. Теория графов

52. Определение графа как отношения. Смежность, множества смежности. Графическая интерпретация графа (диаграммы). Экскурс в историю: Кенигсбергские мосты, задача о трех колодцах, игра «Вокруг Света» (Гамильтон), раскраска карты в 4 цвета, закон Кирхгофа, изомеры предельных углеводородов, потоки в сетях и др.

53. Мультиграф. Псевдограф (с петлями). Ориентированный граф. Дополнение графа. Степень вершины. Степень графа. Лемма о рукопожатиях. Следствие о количестве «нечетных» вершин. Утверждение о двух вершинах одинаковой степени.

54. Примеры (виды) графов: пустой, полный, двудольный (в т.ч. полный), звезда, простой цикл, скелеты платоновских тел, графы Куратовского, граф Петерсона, звезда Давида. Планарность графа. Связность графа.

55.Представление графов в компьютере. Матрица смежности. Матрица инциденций. Списки смежности. Массив дуг. Достоинства и недостатки представлений. (Cписок инцидентности)

56. Обходы графов*: поиск в ширину и в глубину. Теорема о корректности обходов и следствия* из нее. Пример обхода.

57. Изоморфные графы. Помеченные графы, их количество. Формула Пойа. Проблема изоморфности и поиск полного инварианта. Примеры неполных инвариантов: n, m, вектор степеней, плотность, хроматическое число, порождающие функции. Канонический код графа, двоичный код смежности.

58. Подграф. Остовный и порожденный подграф. Гипотеза восстановления (по колоде). Маршруты, цепи, циклы. Утверждения о простых маршрутах и простых циклах.

59. Эйлеров цикл и эйлеров граф. Критерий эйлеровости графа. Алгоритм построения эйлерова цикла. Теорема о количестве эйлеровых графов (только схема доказательства).

60. Гамильтонов цикл и гамильтонов граф. Необходимые и достаточные условия гамильтоновости графа. Теорема Оре, следствие Дирака. Теорема о количестве гамильтоновых графов (без д-ва). Задача коммивояжера.

61. Связные и несвязные графы. Связность дополнения графа. Лемма о циклическом ребре. Теорема о количестве ребер в графе с k компонентами связности.

62. Метрические характеристики графа. Геодезическая, эксентриситет, радиус, диаметр, центр графа. Пример. Двудольные графы, критерий двудольности.

63. Орграфы. Дуги, узлы. Сильная, односторонняя и слабая связность. Достижимость. Транзитивное замыкание.

64. Деревья. Теорема о деревьях*. Доказать один из пунктов. Следствие о висячих вершинах. Центр дерева. Лес. Остовный подграф.

65. Теорема о количестве деревьев. Код Прюфера*. Пример построения кода и восстановления по нему.

66. Ориентированные, бинарные, упорядоченные деревья. Представление упорядоченных деревьев: список, упакованный массив, польская запись. Примеры представлений. Теорема* об ориентированных деревьях.

67. Обходы бинарных деревьев: прямой, обратный, концевой. Алгоритмы* обходов. Примеры обходов.

68. Ассоциативная память. Способы реализации: упорядоченный массив, неупорядоченный массив, дерево сортировки, хэш-таблица. Алгоритмы* вставки, поиска и удаления для массивов.

69. Деревья сортировки. Алгоритмы* поиска, вставки и удаления для деревьев сортировки.

70. Выровненные, заполненные и полные деревья. Сбалансированное дерево. Оценка высоты этих видов деревьев (только схема доказательства). Балансировка* деревьев. Пример балансировки.

71. Отыскание кратчайшего остова. Постановка задачи. Алгоритм* Краскала.

72. Отыскание кратчайшего остова. Алгоритм* Прима. Задача Штейнера.

73. Точки сочленения, мосты и блоки. Свойства точек сочленения и мостов. Вершинная и реберная связность. Теорема о связи вершинной и реберной связности. Примеры.

74. Непересекающиеся цепи и разделяющие множества. Теорема Менгера в вершинной форм (только схема д-ва). Критерий вершинной связности. Теорема Менгера в реберной форме. Критерий реберной связности.

75. Лемма Холла (с д-вом) и ее варианты. Примеры применения.

76. Потоки в сетях. Постановка задачи об отыскании максимального потока. Насыщенные, пустые, допустимые дуги. Разрезы. Алгоритм* Форда-Фалкерсона.

77. Потоки в сетях. Насыщенные, пустые, допустимые дуги. Лемма о разрезах. Теорема* Форда-Фалкерсона. Связь с теоремой Менгера. Алгоритм* Эдмондса-Карпа.

77. Компоненты сильной связности. Алгоритм* отыскания КСС.

78. Кратчайшие пути. Алгоритм* Дейкстры.

79. Кратчайшие пути. Алгоритм* Флойда.

80. Кратчайшие пути. Алгоритм* Форда-Беллмана.

81. Независимые и покрывающие множества вершин и ребер. Пример. Связь чисел независимости и чисел покрытий (доказать любое неравенство).

82. Построение независимых множеств вершин. Полный перебор, поиск с возвратами*, улучшенный перебор*. Доминирующие множества. Задача о наименьшем покрытии*.

83. Хроматическое число графа. Примеры. Оценки для хроматического числа (с д-вом). Хроматическое число дополнения графа (без д-ва). Точный алгоритм раскрашивания.

84. Приближенный алгоритм* последовательного раскрашивания. Улучшенный алгоритм* последовательного раскрашивания.

85. Планарный граф. Теорема Эйлера и следствия из нее. Теорема о пяти красках.

* - можно воспользоваться заранее подготовленными справочными материалами.