Эйлеровы и гамильтоновы циклы, раскраска графов

Три знаменитых сюжета теории графов: пройти по всем рёбрам, обойти все вершины и раскрасить граф минимумом цветов.

Эйлеров путь проходит по каждому ребру графа ровно один раз; гамильтонов путь проходит через каждую вершину ровно один раз.

Зачем это нужно

Эти задачи — не просто головоломки. Эйлеровы пути — это маршруты уборочных машин и почтальонов (пройти все улицы), сборка последовательностей ДНК. Гамильтоновы — задача коммивояжёра (объехать все города), логистика, планирование. Раскраска графов — это распределение частот, расписание экзаменов (чтобы не пересекались), выделение регистров в компиляторе. А ещё здесь живёт важнейшая для CS граница: эйлеров путь находится легко, а гамильтонов — пример NP-трудной задачи, для которой быстрого алгоритма не известно. Эта тема показывает, где «легко» переходит в «трудно».

Эйлеров путь: задача о мостах Кёнигсберга

С неё началась вся теория графов. В городе Кёнигсберге было семь мостов, и горожане спорили: можно ли прогуляться, пройдя по каждому мосту ровно один раз и вернувшись назад? Эйлер в 1736 году доказал, что нельзя — и заодно дал общий критерий.

Критерий Эйлера (для связного графа):

Эйлеров цикл (замкнутый, вернуться в старт) существует ⟺ все вершины имеют чётную степень.
Эйлеров путь (не обязательно замкнутый) существует ⟺ ровно две вершины нечётной степени (это начало и конец), остальные чётные.

Интуиция изящна: каждый раз, проходя через промежуточную вершину, мы «входим» по одному ребру и «выходим» по другому — рёбра тратятся парами. Значит, у транзитной вершины степень должна быть чётной. Нечётную степень могут иметь только концы пути. В Кёнигсберге все четыре участка суши имели нечётное число мостов — поэтому обход невозможен. Проверим оба случая кодом.

def euler_type(degrees):
    odd = [v for v, d in degrees.items() if d % 2 == 1]
    if len(odd) == 0:
        return "эйлеров ЦИКЛ существует (все степени чётны)"
    if len(odd) == 2:
        return "эйлеров ПУТЬ существует (две нечётные вершины)"
    return "эйлерова обхода НЕТ"

# Квадрат: каждая вершина степени 2 (все чётные)
square = {'A': 2, 'B': 2, 'C': 2, 'D': 2}
print("Квадрат:", euler_type(square))

# Кёнигсберг: степени участков суши 3, 3, 3, 5 (все нечётные)
konigsberg = {'A': 3, 'B': 3, 'C': 3, 'D': 5}
print("Кёнигсберг:", euler_type(konigsberg))

Вывод:

Квадрат: эйлеров ЦИКЛ существует (все степени чётны)
Кёнигсберг: эйлерова обхода НЕТ

Критерий работает мгновенно — нужно лишь посчитать степени и проверить их чётность. Это и есть «лёгкая» задача: ответ получаем за один проход по вершинам, не перебирая маршруты. Для Кёнигсберга четыре нечётные вершины — обход невозможен, спор горожан разрешён математически.

Гамильтонов цикл: обманчиво похожая, но трудная задача

Гамильтонов цикл проходит через каждую вершину ровно один раз и возвращается в начало. Звучит похоже на эйлеров — но это иллюзия. Простого критерия для гамильтонова цикла не существует. Есть лишь достаточные условия (например, теорема Дирака: если степень каждой вершины не меньше n/2, цикл есть), но в общем случае единственный надёжный способ — перебор, который для больших графов взрывается экспоненциально.

Задача «есть ли гамильтонов цикл» — NP-полная. Это значит: быстрого (полиномиального) алгоритма для неё не известно, и найти такой — одна из главных открытых проблем информатики (P vs NP). На гамильтоновых циклах основана знаменитая задача коммивояжёра. Вот наглядный урок: две внешне похожие задачи (по рёбрам vs по вершинам) лежат по разные стороны границы «легко/трудно».

Раскраска графа

Правильная раскраска графа — это назначение вершинам цветов так, чтобы соседние (соединённые ребром) вершины имели разные цвета. Минимальное число цветов, которого хватает, называется хроматическим числом графа.

Зачем это нужно? Представь составление расписания экзаменов: вершины — экзамены, ребро — «эти два экзамена сдаёт общий студент, их нельзя в одно время». Раскраска = распределение по слотам времени, цвета = слоты. Хроматическое число — минимальное число временных слотов. Та же модель — для распределения радиочастот, выделения регистров процессора, раскладки задач по ресурсам.

# «Жадная» раскраска: каждой вершине — наименьший доступный цвет
g = {1: [2, 3], 2: [1, 3], 3: [1, 2, 4], 4: [3]}

def greedy_coloring(g):
    color = {}
    for v in sorted(g):
        used = {color[u] for u in g[v] if u in color}
        c = 0
        while c in used:          # ищем наименьший свободный цвет
            c += 1
        color[v] = c
    return color

coloring = greedy_coloring(g)
print("Раскраска (вершина: цвет):", coloring)
print("Использовано цветов:", len(set(coloring.values())))

Вывод:

Раскраска (вершина: цвет): {1: 0, 2: 1, 3: 2, 4: 0}
Использовано цветов: 3

Жадный алгоритм раскрасил граф в 3 цвета. Вершины 1, 2, 3 образуют треугольник (все попарно соседи) — им нужны три разных цвета, меньше трёх тут не выйдет. А вершина 4 переиспользовала цвет 0, так как с вершинами 1 и 2 не соседствует. Заметь: жадная раскраска не всегда даёт минимум цветов — точное вычисление хроматического числа тоже NP-трудная задача. Знаменитая теорема о четырёх красках гласит, что любую плоскую карту можно раскрасить четырьмя цветами — её доказали лишь в 1976 году с помощью компьютера.

Кратчайший путь: почему BFS находит его «бесплатно»

У обхода в ширину есть свойство, ради которого его чаще всего и применяют: BFS находит кратчайший путь (по числу рёбер) от старта до всех остальных вершин невзвешенного графа. Это прямое следствие того, что BFS идёт «волнами»: сначала он навещает все вершины на расстоянии 1, затем все на расстоянии 2, и так далее. Когда волна впервые достигает вершины — это гарантированно по кратчайшему пути, ведь более короткого волна достигла бы раньше.

Поэтому BFS — сердце навигации в простых случаях: поиск выхода из лабиринта, минимальное число ходов коня на шахматной доске, «число рукопожатий» между двумя людьми в соцсети. Достаточно при первом посещении вершины запоминать, откуда мы пришли, — и потом восстановить весь путь «назад по родителям». Для взвешенных графов (где у рёбер разная длина) BFS уже не годится, и нужен алгоритм Дейкстры — но идея «расширяющейся волны» остаётся той же. Так выбор между очередью и стеком определяет не только порядок обхода, но и то, какую задачу мы умеем решать.

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

Путать эйлеров и гамильтонов. Эйлеров — по всем рёбрам, критерий по чётности степеней (легко). Гамильтонов — по всем вершинам, простого критерия нет (трудно).
Думать, что жадная раскраска оптимальна. Она даёт правильную раскраску, но не всегда минимальным числом цветов — результат зависит от порядка обхода вершин.
Забывать про связность в критерии Эйлера. Критерий чётности степеней работает для связного графа; у несвязного эйлерова обхода нет независимо от степеней.

Итог

Эйлеров путь — по всем рёбрам; существует ⟺ нечётных вершин ноль (цикл) или две (путь).
Гамильтонов путь — по всем вершинам; простого критерия нет, задача NP-полна.
Раскраска: соседние вершины разных цветов; минимум — хроматическое число.
Эйлер «лёгкий», Гамильтон и точная раскраска «трудные» — наглядная граница сложности.