Graph Theory

Теория графов — раздел дискретной математики, изучающий графы (структуры из вершин, соединённых рёбрами). Граф G = (V, E): V — множество вершин, E — множество рёбер. Применяется в социальных сетях (граф друзей), GPS-навигации (граф дорог), интернете (граф маршрутизации), биологии (граф взаимодействий белков). Основана Леонардом Эйлером (1736).

Задача, которую нельзя решить прогулкой

Кёнигсберг, 1736 год. Город на реке Прегель: два острова, семь мостов. Местные жители бились над головоломкой: можно ли пройти по всем мостам ровно один раз и вернуться в начальную точку?

Попытки предпринимались годами. Никто не смог — но и доказать невозможность тоже никто не мог.

Математик Леонард Эйлер подошёл иначе. Он абстрагировался от географии: не важно, какой длины мосты, какая ширина реки. Важна только структура связей.

Граф Кёнигсберга:

Вершины — 4 района города (два берега + два острова)
Рёбра — 7 мостов между районами

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

В Кёнигсберге все четыре вершины имели нечётную степень (3 или 5 мостов). Вывод: задача неразрешима.

Это была первая работа по теории графов. Эйлер создал новую область математики, решая головоломку о прогулке.

Контринтуитивный факт: в 1944 году Кёнигсберг (теперь Калининград) бомбили, два моста разрушили. Теперь мостов пять, и эйлеров цикл существует! Но никто не интересуется — задача решена математически в 1736, физическая прогулка неважна.

Что такое граф: формальное определение

Граф G = (V, E):

V (vertices): конечное множество вершин {v₁, v₂, ..., vₙ}
E (edges): множество рёбер {(v₁, v₂), (v₂, v₃), ...}

Типы графов:

Неориентированный: ребро (u, v) = (v, u). Дружба в Facebook: если A друг B, то B друг A.

Ориентированный (орграф): ребро (u → v) ≠ (v → u). Подписки в Twitter: A подписан на B, но B не подписан на A.

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

Степень вершины: количество рёбер, выходящих из неё. Для орграфа: степень входа (in-degree) и степень выхода (out-degree).

Путь: последовательность вершин, где каждая пара соседних соединена ребром. v₁ → v₂ → v₃ → v₄.

Цикл: путь, который начинается и заканчивается в одной вершине. v₁ → v₂ → v₃ → v₁.

Связный граф: из любой вершины можно дойти до любой другой.

Социальные сети: граф из 3 миллиардов вершин

Facebook (2004). Граф:

Вершины — пользователи (~3 миллиарда)
Рёбра — дружба (~150 миллиардов связей)

Задача: найти кратчайший путь от пользователя A до пользователя B (степень разделения).

Гипотеза шести рукопожатий (Милграм, 1967): любые два человека на Земле связаны цепочкой из ~6 знакомых.

Facebook провёл исследование (2011): средняя степень разделения — 4.74. Не шесть, а меньше пяти! Интернет сделал мир теснее.

Алгоритм BFS (поиск в ширину):

1. Начинаем с вершины A, помечаем расстояние 0
2. Смотрим всех друзей A — расстояние 1
3. Смотрим друзей друзей — расстояние 2
4. Продолжаем, пока не найдём B

Сложность: O(V + E). Для Facebook: ~3 млрд + 150 млрд = 153 млрд операций. Звучит много, но с распределённой базой данных (миллионы серверов) — секунды.

Центральность вершины: мера «важности» вершины в графе.

Degree centrality: степень вершины. Чем больше друзей, тем важнее.
Betweenness centrality: сколько кратчайших путей проходит через вершину. «Мосты» между сообществами.
PageRank (Google, 1998): важность = сумма важности ссылающихся вершин. Итерационный алгоритм.

GPS-навигация: алгоритм Дейкстры

Граф дорог:

Вершины — перекрёстки
Рёбра — дороги с весами (расстояние или время)

Задача: найти кратчайший путь из A в B.

Алгоритм Дейкстры (1956):

1. Начинаем с вершины A, расстояние 0. Все остальные — бесконечность
2. Выбираем вершину с минимальным расстоянием (сначала A)
3. Смотрим всех её соседей, обновляем расстояния: если через текущую вершину короче, обновляем
4. Помечаем вершину как обработанную
5. Повторяем, пока не дойдём до B

Сложность: O(E log V) с приоритетной очередью (куча). Для города с 100 000 перекрёстками и 300 000 дорог — миллисекунды.

Проблема: Дейкстра ищет глобальный минимум — проверяет все направления. Неэффективно, если цель далеко на север, а алгоритм проверяет юг.

Алгоритм A* (1968): улучшение Дейкстры с эвристикой. Приоритет вершины = расстояние до неё + оценка расстояния до цели (обычно прямая линия — эвклидово расстояние).

A* ищет «в направлении цели», а не во все стороны. В 10-100 раз быстрее Дейкстры на картах.

Google Maps (2005): использует A* с динамическими весами (учёт пробок в реальном времени). Граф обновляется каждые несколько минут на основе данных GPS от миллионов телефонов.

Задача коммивояжёра: самая известная NP-полная задача

Дано: N городов, расстояния между ними.
Найти: кратчайший маршрут, посещающий все города ровно один раз и возвращающийся в начальную точку.

Вариантов маршрута: (N-1)! / 2

Для 10 городов: 181 440 — перебор за секунды.
Для 20 городов: 10¹⁸ — миллиарды лет на обычном ПК.
Для 50 городов: 10⁶⁴ — больше, чем атомов в наблюдаемой Вселенной.

Это NP-полная задача: нет эффективного алгоритма точного решения. Если кто-то найдёт — докажет P = NP, получит $1 млн от Clay Mathematics Institute и сломает всю криптографию.

Приближённые методы:

Жадный алгоритм: каждый шаг — ближайший непосещённый город. Быстро, но неоптимально (~25% хуже оптимума).

Генетический алгоритм: эволюция маршрутов (скрещивание, мутации) → отбор лучших. Находит решение на 95-98% от оптимума.

Муравьиный алгоритм: симуляция поведения муравьёв (феромоны на рёбрах, вероятностный выбор). Эффективен для динамических графов.

Рекорд (2006): точное решение TSP для 85 900 городов (все города мира с населением >5000). Алгоритм Concorde, вычисления на суперкомпьютере — несколько месяцев. Но это предел для точных методов.

Деревья: графы без циклов

Дерево — связный граф без циклов. Любые две вершины соединены ровно одним путём.

Свойства: для дерева с N вершинами — всегда N-1 ребро.

Остовное дерево (spanning tree): подграф графа G, который:

1. Включает все вершины G
2. Является деревом (связный, без циклов)
3. Имеет минимальный суммарный вес рёбер (минимальное остовное дерево, MST)

Применение MST: проектирование сетей (дороги, интернет-кабели, трубопроводы). Задача: соединить все города с минимальными затратами.

Алгоритм Прима (1957):

1. Начинаем с произвольной вершины
2. Добавляем ребро минимального веса, соединяющее дерево с новой вершиной
3. Повторяем, пока не добавим все вершины

Сложность: O(E log V). Для графа с миллионом вершин — секунды.

Алгоритм Крускала (1956): сортируем все рёбра по весу, добавляем в дерево по возрастанию, пропуская те, что создают циклы. Проще для разреженных графов.

Раскраска графов и расписания

Задача: раскрасить вершины графа так, чтобы соседние вершины имели разные цвета. Минимизировать количество цветов.

Применение: составление расписаний.

Граф конфликтов:
Вершины — экзамены
Рёбра — студенты, сдающие оба экзамена (нельзя назначить в одно время)

Цвет вершины = временной слот. Минимальное число цветов = минимальное число временных слотов.

Теорема о четырёх красках (1976, доказана с помощью компьютера): любую карту можно раскрасить четырьмя цветами так, что соседние страны имеют разные цвета.

Граф карты: вершины — страны, рёбра — граница. Хроматическое число (минимум цветов) ≤ 4.

Это был первый крупный математический результат, доказанный компьютером (перебор ~1500 случаев). Математики спорят: это доказательство или вычислительная проверка?

Где теория графов не работает

Граф — статическая структура. Реальный мир динамичен.

Пример: социальная сеть. Дружба появляется и исчезает. Граф меняется каждую секунду. Алгоритмы должны работать с инкрементальными обновлениями, а не пересчитывать всё с нуля.

Темпоральные графы: расширение теории графов, где рёбра существуют в определённые моменты времени. Применение: эпидемиология (кто с кем контактировал когда), транспортные сети (метро с расписанием).

Но вычисления на темпоральных графах сложнее на порядки. Кратчайший путь в метро зависит от времени выезда — нельзя применить Дейкстру напрямую.

Теория графов работает с абстракцией. Чем сложнее реальность, тем больше приходится упрощать модель — и терять точность.