Конечные графы

§ 1. Основные понятия теории графов.

Ориентированные и неориентированные графы, их вершины, рёбра и дуги. Мультиграфы. Псевдографы. Изоморфные графы. Нулевой граф. Полный граф. Часть графа. Подграф. Собственный подграф. Число помеченных графов на n вершинах.

§ 2.Операции над графами.

Дополнение. Объединение графов. Произведение графов. Композиция графов.

§ 3.Способы задания псевдографов.

Матрица смежности. Матрица инцидентности. Список ребер. Списки смежности.

§ 4.Степени вершин.

Степени вершин псевдографа. Лемма о рукопожатиях. Однородный (регулярный) граф.

§ 5. Отношение связности для вершин неориентированного графа.

Маршрут, цепь и цикл. Отношение связности и его свойства. Компоненты связности. Связный граф. Точка сочленения. Мост.

§ 6. Отношение достижимости для вершин орграфа.

Путь, ориентированная цепь и ориентированный цикл. Отношение достижимости и его свойства. Базисный граф. Алгоритм построения базисного графа.

§ 7.Эйлеров псевдограф.

Эйлеров цикл и условия его существования. Эйлерова цепь и условия ее существования.

§ 8.Гамильтонов граф.

Гамильтонов цикл и простейшие условия его существования.

§ 9.Деревья.

Деревья и их свойства. Формула Кэли. Задача о минимальном соединении. Остовное дерево. Построение минимального остовного дерева.

§ 10.Двудольный граф.

Определение двудольного графа. Условия, при которых граф двудольный.

§ 11.Планарность.

Укладка графа. Плоский граф. Планарный граф. Теорема Эйлера о связи между количеством вершин, ребер и граней плоского графа. Следствия из теоремы Эйлера: относительно количества ребер планарного графа; относительно графов K₅ и K_3,3; относительно степени вершины планарного графа. Теорема Понтрягина-Куратовского.

§ 12.Раскраска графа.

Правильная раскраска графа. Хроматическое число графа. Теорема о пяти красках. Гипотеза четырех красок.