Теория графов: задачи с пошаговыми решениями

1Вершины, рёбра и степени

Граф состоит из вершин (точек) и рёбер (линий между двумя вершинами). В простом графе нет петель и кратных рёбер.

Степень вершины — это число рёбер, которые в ней сходятся. У каждого ребра два конца, поэтому оно добавляет 1 к степени каждого конца. Отсюда лемма о рукопожатиях:

Два следствия: сумма степеней всегда чётна, и число вершин нечётной степени тоже чётно.

• Полный граф K_n соединяет каждую пару: n(n − 1)/2 рёбер.
• Полный двудольный граф K_m,n соединяет каждую вершину одной доли с каждой вершиной другой: m·n рёбер.
• У k-регулярного графа на n вершинах n·k/2 рёбер.

В матрице смежности стоит 1 в позиции (i, j), когда i и j соединены. Для неориентированного графа она симметрична, сумма строки — это степень, а элемент (i, j) матрицы Mᴸ считает маршруты длины L из i в j.

2Эйлер и Гамильтон

Эйлеров цикл проходит каждое ребро ровно один раз и возвращается в начало. Эйлеров путь проходит каждое ребро один раз, но может закончиться в другом месте. Для связного графа:

• все степени чётные: эйлеров цикл существует;
• ровно две нечётные степени: эйлеров путь существует, от одной нечётной вершины к другой;
• больше двух нечётных степеней: нет ни того, ни другого.

Гамильтонов цикл посещает каждую вершину ровно один раз. Простого признака по степеням для него нет. В K_n имеется (n − 1)!/2 различных гамильтоновых циклов: зафиксируйте начало, упорядочьте остальные n − 1 вершин и разделите на 2 из-за двух направлений.

3Деревья

Дерево — это связный граф без циклов. В любом дереве с n вершинами ровно n − 1 ребро. Добавление любого ребра создаёт цикл; удаление любого ребра делает граф несвязным.

В лесу из c деревьев на n вершинах n − c рёбер. Связный граф с m рёбрами сохраняет остовное дерево после удаления m − n + 1 рёбер.

Лемма о рукопожатиях позволяет посчитать листья: Σ deg = 2(n − 1). Короткая форма: L = 2 + Σ (d − 2) по вершинам степени d ≥ 3. У дерева с двумя вершинами степени 3, а остальными листьями, 2 + 1 + 1 = 4 листа.

4Алгоритм Дейкстры и минимальные остовные деревья

Алгоритм Дейкстры находит кратчайшие расстояния от начальной вершины в графе с неотрицательными весами.

1. Задайте начальной вершине расстояние 0, а всем остальным — ∞.
2. Зафиксируйте нефиксированную вершину с наименьшим расстоянием; теперь её расстояние окончательное.
3. Для каждого соседа v обновите d(v) = min(d(v), d(u) + w(u, v)).
4. Повторяйте, пока не будет зафиксирована целевая вершина.

Минимальное остовное дерево соединяет все вершины с наименьшим суммарным весом. Краскал сортирует рёбра от лёгких к тяжёлым и берёт каждое, если оно не замыкает цикл. Прим растит одно дерево из начальной вершины, всегда добавляя самое лёгкое ребро, выходящее из него. Оба останавливаются после n − 1 рёбер.

5Типичные ошибки

• Забывать разделить сумму степеней на 2, чтобы получить число рёбер.
• Проверять наличие эйлерова цикла, не проверив, что граф связный.
• Фиксировать вершину в алгоритме Дейкстры до того, как у неё стало наименьшее предварительное расстояние.
• Брать n − 1 самых лёгких рёбер, не проверяя наличие циклов.
• Считать гамильтоновы циклы в K_n как n!, а не (n − 1)!/2.

6Как выглядят экзаменационные задачи

• Лёгкий: степени и рёбра. Вы используете лемму о рукопожатиях, считаете рёбра в K_n, K_m,n, регулярных графах и деревьях, читаете матрицу смежности или выбираете вершину с заданной степенью.
• Средний: эйлеровы пути и деревья. Вы определяете, есть ли в графе эйлеров цикл или путь, считаете листья дерева, считаете, сколько рёбер удалить для остовного дерева, или считаете гамильтоновы циклы в K_n.
• Сложный: кратчайшие пути и остовные деревья. Вы выполняете алгоритм Дейкстры, находите вершину, зафиксированную на заданном шаге, находите вес минимального остовного дерева, выбираете ребро, которое Краскал или Прим добавит следующим, или считаете маршруты с помощью матрицы смежности.