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

Определение и виды

Граф G = (V, E): V — множество вершин, E — множество рёбер (пар вершин).

Ориентированный (орграф): рёбра направлены. Взвешенный: рёбра имеют веса.

Степень вершины deg(v) — число рёбер, инцидентных v. Лемма о рукопожатиях: Σ deg(v) = 2|E| (каждое ребро вносит 2 в сумму степеней). Следствие: число вершин нечётной степени чётно.

Пути и связность

Маршрут: последовательность вершин v₀, v₁, ..., vₖ с рёбрами v_{i-1}v_i. Путь: маршрут без повторяющихся вершин.

Граф связен, если между любыми двумя вершинами есть путь.

Компоненты связности — максимальные связные подграфы.

Кратчайшие пути: алгоритм Дейкстры (неотрицательные веса) O((V+E)log V); Беллман–Форд (допускает отрицательные) O(VE); Флойд–Уоршелл (все пары) O(V³).

Деревья

Дерево — связный граф без циклов. Эквивалентные условия (для n вершин):

• n−1 рёбер
• Любые две вершины соединены единственным путём
• Связен и добавление любого ребра создаёт цикл

Остовное дерево связного графа — подграф-дерево, содержащий все вершины. Минимальное остовное дерево (MST): алгоритм Крускала (E log E) или Прима (E log V).

Числа Кирхгофа

Матрица Лапласа: L = D − A (D — диагональная матрица степеней, A — матрица смежности).

Число остовных деревьев = любой кофактор L (теорема Кирхгофа). Красивый результат, связывающий топологию графа со спектром матрицы.

Спектральная теория графов

Матрица смежности A и лапласиан L = D − A связывают структуру графа с алгеброй. Собственные значения лапласиана 0 = λ₁ ≤ λ₂ ≤ ... ≤ λₙ содержат богатую структурную информацию. λ₂ > 0 тогда и только тогда, когда граф связен. λ₂ — алгебраическая связность (связность Фидлера): чем больше λ₂, тем «связнее» граф. Разрезание по вектору Фидлера (соответствующему λ₂) — основа спектральной кластеризации в машинном обучении.

Теорема Кирхгофа о матричном дереве: Число остовных деревьев τ(G) = (1/n)λ₂λ₃...λₙ (произведение ненулевых собственных значений L). Для полного графа Kₙ: все ненулевые собственные значения L равны n, поэтому τ(Kₙ) = nⁿ⁻². Это формула Кэли (1889), доказанная алгебраическим путём через 80 лет.

Алгоритмы на графах: практика

Поиск в глубину (DFS): Рекурсивный обход, строит дерево DFS. Сложность O(V+E). Применения: топологическая сортировка DAG, нахождение компонент сильной связности (алгоритм Тарьяна, Косараджу), проверка двудольности, нахождение мостов и точек сочленения.

Поиск в ширину (BFS): Обход уровнями, кратчайшие пути в невзвешенном графе O(V+E). В взвешенных с неотрицательными весами — алгоритм Дейкстры O((V+E)log V) с приоритетной очередью (кучей Фибоначчи даёт O(E + V log V)).

Алгоритмы MST: Алгоритм Крускала сортирует рёбра по весу и жадно добавляет, не создавая цикл — O(E log E). Алгоритм Прима растит дерево от произвольной вершины — O(E log V) с бинарной кучей. Корректность обоих основана на свойстве разреза: для любого разреза (S, VS) ребро минимального веса, пересекающее разрез, входит в MST.

Теоретико-графовые задачи в Computer Science

Связность и потоки используются в сетевом дизайне: как найти минимальный разрез сети (минимальная пропускная способность для отказа), где поставить дублирующие каналы. Теорема Менгера: минимальный вершинный разрез = максимальное число вершинно-непересекающихся путей — это двойственность min-cut/max-flow в вершинной формулировке.

Графы используются в компиляторах: граф потока управления (Control Flow Graph), граф конфликтов при распределении регистров (раскраска = распределение регистров), граф зависимостей данных для параллелизации. NP-полнота раскраски графов объясняет, почему оптимальное распределение регистров NP-трудно в общем случае (современные компиляторы используют эвристики).

Планарность: алгоритм Планара и формула Эйлера

Формула Эйлера для связного планарного графа: V − E + F = 2 (V вершин, E рёбер, F граней включая внешнюю). Для многосвязного: V − E + F = 1 + C (C компонент связности). Следствие: E ≤ 3V − 6. Для двудольных планарных: E ≤ 2V − 4 (нет треугольников). Поэтому K₅ и K_{3,3} непланарны: K₅ имеет E=10, 3V−6=9; K_{3,3} имеет E=9, 2V−4=8.

Теорема Куратовского: Граф планарен ↔ не содержит подразделения K₅ или K_{3,3}. Алгоритм проверки планарности за O(V): алгоритм Хопкрофта-Тарьяна (1974) на основе DFS с ST-нумерацией. Практически: для V < 10⁶ вершин — быстро.

Гипер-графы и их применения

Гиперграф H = (V, E), где E ⊆ 2^V (рёбра — произвольные подмножества вершин). Двудольный граф — это двудольное представление гиперграфа (вершины ↔ вершины графа, рёбра ↔ «рёберные» вершины). Гиперграфы моделируют многосторонние связи: сотрудники ↔ проекты, гены ↔ болезни, термины ↔ документы.

Раскраска гиперграфов (Property B): Гиперграф 2-раскрашиваем, если его вершины красятся в 2 цвета так, что ни одно ребро не одноцветно. Не все гиперграфы 2-раскрашиваемы — вероятностный метод Эрдёша даёт условие: если каждое ребро содержит ≥ k вершин и каждая вершина в ≤ 2^{k−2} рёбрах, то 2-раскрашиваем. Применяется в балансировке нагрузки и теории игр.

Численный пример: алгоритм Дейкстры

Задача: Найти кратчайшие пути из A в графе: A−B:4, A−C:2, C−B:1, B−D:5, C−D:8.

Шаг 1: Инициализация: d(A)=0, d(B)=∞, d(C)=∞, d(D)=∞. Приоритетная очередь: {A}.

Шаг 2: Извлечь A (d=0). Обновить соседей: d(B)←min(∞,0+4)=4; d(C)←min(∞,0+2)=2.

Шаг 3: Извлечь C (d=2). Обновить: d(B)←min(4,2+1)=3; d(D)←min(∞,2+8)=10.

Шаг 4: Извлечь B (d=3). Обновить: d(D)←min(10,3+5)=8. Извлечь D (d=8). Готово.

Результат: d(A→B)=3 (путь A→C→B), d(A→C)=2, d(A→D)=8 (путь A→C→B→D). Все кратчайшие пути из A найдены: длины 2, 3, 8. Это расстояния, а не потоки — алгоритм Дейкстры решает задачу кратчайшего пути, не максимального потока.