Эйлеровы и гамильтоновы пути

Эйлеровы пути

Эйлеров путь — маршрут, проходящий по каждому ребру ровно по одному разу.

Теорема Эйлера (1736): Граф имеет эйлеров цикл тогда и только тогда, когда он связен и все вершины имеют чётную степень.

Эйлеров путь (не цикл) существует ⟺ связен и ровно 2 вершины нечётной степени.

Задача Кёнигсбергских мостов: семь мостов через реку — можно ли пройти каждый ровно раз? Четыре острова, все нечётные степени → нет.

Гамильтоновы пути

Гамильтонов путь — путь, проходящий через каждую вершину ровно раз.

В отличие от Эйлерова: нет простого критерия! Задача нахождения гамильтонова цикла NP-полна.

Достаточное условие (теорема Дирака): Если каждая вершина имеет степень ≥ n/2 (n ≥ 3), то гамильтонов цикл существует.

Задача коммивояжёра (TSP): минимальный гамильтонов цикл в полном взвешенном графе. NP-трудна; приближённые алгоритмы: 2-opt, Lin–Kernighan.

Потоки в сетях

Сеть: орграф с источником s и стоком t, пропускные способности c(u,v) ≥ 0.

Поток f: функция f(u,v) с 0 ≤ f(u,v) ≤ c(u,v) и сохранением потока в каждой вершине (кроме s и t).

Теорема Форда–Фалкерсона (Максимальный поток = Минимальный разрез): max f = min C(S,T) по всем разрезам.

Алгоритм Эдмондса–Карпа (BFS): O(VE²). Алгоритм Диница: O(V²E).

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

Алгоритм Форда-Фалкерсона: детали и корректность

Идея: Ищем увеличивающий путь (augmenting path) из s в t в остаточной сети G_f, где пропускная способность r(u,v) = c(u,v) − f(u,v) для прямых рёбер и r(v,u) = f(u,v) для обратных. Увеличиваем поток вдоль пути на минимальную остаточную ёмкость.

Теорема Форда-Фалкерсона: Поток максимален тогда и только тогда, когда нет увеличивающего пути в G_f. Эквивалентно: max flow = min cut (теорема макс-поток/мин-разрез).

Версия Эдмондса-Карпа (BFS для выбора пути): O(VE²). При иррациональных ёмкостях базовый алгоритм Форда-Фалкерсона может не сходиться, а BFS-версия всегда завершается.

Эйлеровы цепи: алгоритм Флёри

Алгоритм Флёри строит эйлеров путь жадно: начинаем с вершины нечётной степени (или любой), на каждом шаге выбираем ребро, которое не является мостом (если есть альтернатива). Удаляем пройденное ребро. За O(E²) находим эйлеров путь. Более эффективный алгоритм Хирхольцера работает за O(E): строим циклы жадно и соединяем их.

Китайская почтальонская задача: Найти минимальный маршрут почтальона, обходящего каждую улицу хотя бы раз. Если граф эйлеров — это эйлеров цикл (оптимально). Иначе — нужно «задублировать» рёбра между вершинами нечётной степени (минимальное паросочетание нечётных вершин с минимальным суммарным весом). Решается за O(V³).

Гамильтоновы пути и задача коммивояжёра

TSP (задача коммивояжёра) — NP-трудная: для n городов перебор всех маршрутов занимает O(n!). Точные методы (ветвей и границ, динамическое программирование Беллмана-Хелда-Карпа O(n²2ⁿ)) практичны до n ≈ 20-30. Для больших n — приближённые алгоритмы: алгоритм ближайшего соседа (жадный, не оптимальный), 2-opt (итерационное улучшение), алгоритм Кристофидеса (гарантия ≤ 3/2 оптимума для метрических экземпляров).

Раскраска рёбер (хроматический индекс)

Хроматический индекс χ'(G) — минимальное число цветов для правильной раскраски рёбер (смежные рёбра разного цвета). Теорема Визинга (1964): Δ ≤ χ'(G) ≤ Δ+1 (Δ — максимальная степень). Класс 1: χ'(G) = Δ. Класс 2: χ'(G) = Δ+1. Определение класса NP-трудно в общем случае. Для двудольных графов: χ'(G) = Δ (теорема Кёнига). Применение: составление расписаний, раскраска временных интервалов в телекоммуникации.

Теория совершенных графов

Совершенный граф: χ(G) = ω(G) для любого индуцированного подграфа (ω — кликовое число). Слабая теорема о совершенных графах (Ловас, 1972): G совершенен ↔ дополнение G совершенно. Теорема Чадни-Робертсона-Чудновского-Томаса (2006): G совершенен ↔ не содержит нечётных дырок (odd holes, нечётные циклы длины ≥ 5) и их дополнений — «Теорема о сильных совершенных графах».

Совершенные графы включают: двудольные, хордальные, сравнимостные, интервальные. Для совершенных графов χ(G) = ω(G) вычисляется полиномиально через SDP (эллипсоидный метод Гровчча).

Случайные графы: модель Эрдёша-Реньи

G(n,p) — случайный граф на n вершинах, каждое ребро независимо с вероятностью p. Теория пороговых значений: при p < (1−ε)ln(n)/n граф почти наверное не является связным, при p > (1+ε)ln(n)/n — почти наверное связен. Порог появления треугольников: p ~ n^{−1}. Порог гамильтонова цикла: p ~ ln(n)/n. Эти «пороговые функции» открыты Эрдёшем и Реньи (1960) и породили «эволюцию случайных графов».

Экспандерные графы и их применения

Экспандер: семейство d-регулярных графов Gₙ с |V|→∞, где спектральный зазор λ₁−λ₂ ≥ ε > 0 (λ₁=d — первое собственное значение матрицы смежности). Экспандеры имеют хорошие свойства распространения: случайное блуждание быстро перемешивается. Применения: дерандомизация алгоритмов (экспандеры заменяют случайность), коды (Тернер-Сипсер), сетевые алгоритмы. Конструкция: группы Рамануджана — явные экспандеры через теорию модулярных форм.

Численный пример: порог связности G(n,p)

Задача: G(n=100, p). Найти p* и проверить вероятность изоляции вершин при p=0.046.

Шаг 1: Критическое значение: p* = ln(n)/n = ln(100)/100 = 4.605/100 = 0.0461.

Шаг 2: P(конкретная вершина изолирована) = (1−p)^{99} ≈ e^{−99p}. При p=0.046: e^{−99·0.046}=e^{−4.554}≈0.0105.

Шаг 3: E[число изолированных вершин] = 100·0.0105 ≈ 1.05. Именно на пороге ожидаем около 1 изолированной вершины.

Шаг 4: При p=0.07 (выше порога): e^{−99·0.07}=e^{−6.93}≈0.0010. E[изол.]≈0.1 — граф почти наверное связен. Для G(n,p) второе собственное значение матрицы смежности A концентрируется около 2√(np(1−p)) (теорема Фюреди-Комлоша): при n=100, p=0.07 это ≈2√(6.51)≈5.1, тогда как первое СЗ ≈np=6.93. Спектральный зазор положителен — граф связен с высокой вероятностью.