Теория графов в оптимизации: потоки и паросочетания

Графы как модели реального мира

Граф — математическая абстракция сети: вершины (узлы) и рёбра (связи). Интернет — граф маршрутизаторов. Социальная сеть — граф пользователей. Транспортная сеть — граф городов и дорог. Многие задачи дискретной оптимизации — это задачи на графах. Три классических класса: задачи потоков (как направить трафик по сети), паросочетания (как назначить задачи исполнителям), остовные деревья (как соединить все узлы минимально). Все они решаются за полиномиальное время!

Максимальный поток

Постановка: ориентированная сеть G = (V, E) с пропускными способностями c(e) > 0 на каждом ребре. Источник s, сток t. Найти максимальный поток из s в t.

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

Теорема Форда-Фалкерсона: max flow = min cut.

Разрез (S, V∖S) с s ∈ S, t ∈ V∖S: мощность разреза = сумма пропускных способностей рёбер из S в V∖S. Минимальный разрез = «узкое место» сети.

Алгоритм Форда-Фалкерсона: ищем «увеличивающий путь» (augmenting path) в остаточной сети: путь из s в t, где каждое ребро имеет остаточную пропускную способность > 0. Увеличиваем поток вдоль пути. Повторяем до отсутствия пути.

Сложность: O(E · f_max) для рациональных пропускных способностей. Алгоритм Эдмондса-Карпа (Edmonds-Karp) — использует BFS для поиска кратчайшего пути → O(V E²).

Полный разбор примера: сеть: s→a (c=4), s→b (c=3), a→t (c=3), a→b (c=2), b→t (c=4).

Путь 1: s→a→t, поток = 3. Путь 2: s→b→t, поток = 3. Остаточная сеть: s→a (c=1), a→b (c=2). Путь 3: s→a→b→t, поток = 1. Итого max flow = 7. Минимальный разрез: {s,a,b} и {t} → мощность = 3 + 4 = 7. ✓

Паросочетания в двудольных графах

Двудольный граф: V = A ∪ B, рёбра только между A и B.

Паросочетание M: набор рёбер, не имеющих общих вершин. Максимальное паросочетание — наибольшее по числу рёбер M.

Алгоритм Хопкрофта-Карпа: O(E√V). Ищет увеличивающие пути с помощью BFS (находит все кратчайшие увеличивающие пути одновременно), затем DFS для нахождения максимального паросочетания этой длины.

Венгерский алгоритм (задача назначения): дан полный двудольный граф с весами wᵢⱼ (стоимость назначения задачи i исполнителю j). Найти минимальное назначение (= паросочетание минимального суммарного веса). Сложность: O(n³).

Применения паросочетаний:

• Назначение учителей классам в школе
• Распределение заказов между водителями такси (Яндекс.Такси — задача паросочетания в реальном времени!)
• Медицина: совместимость доноров и реципиентов почки
• Рекомендательные системы: сопоставление пользователей с контентом

Минимальное остовное дерево (MST)

Остовное дерево графа G = (V, E): связный ациклический подграф, включающий все вершины. Число рёбер = |V| − 1.

Задача MST: найти остовное дерево минимального суммарного веса рёбер.

Алгоритм Крускала: O(E log E)

1. Отсортировать рёбра по весу
2. Перебирать рёбра в порядке возрастания
3. Добавлять ребро в T, если оно не создаёт цикл (проверка через Union-Find)

Алгоритм Прима: O(E log V) с кучей

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

Доказательство оптимальности (обрезающее свойство): для любого разреза (S, V∖S) минимальное ребро через разрез входит в любое MST.

Полный разбор: граф 4 вершин: a-b (4), a-c (3), b-c (2), b-d (5), c-d (1).

Крускал: сортировка рёбер: c-d (1), b-c (2), a-c (3), a-b (4), b-d (5). Добавляем: c-d (1) ✓, b-c (2) ✓, a-c (3) ✓. Дерево: {c-d, b-c, a-c}. Вес = 6. Следующее ребро a-b (4) создаст цикл a-b-c-a → пропускаем.

Применения: прокладка кабелей в сети при минимальной длине кабеля (телефонные, электрические сети), кластеризация данных (single-linkage), приближённые алгоритмы для TSP.

Кратчайшие пути

Алгоритм Дейкстры: неотрицательные веса. O((V+E) log V) с двоичной кучей. Идея: жадно расширяем «фронт» кратчайших путей от s.

Bellman-Ford: допускает отрицательные веса (но не отрицательные циклы). O(VE). Обнаруживает отрицательные циклы.

Floyd-Warshall: все пары кратчайших путей. O(V³). Простая реализация через DP.

Алгоритм A*: эвристическое ускорение Дейкстры. При наличии допустимой эвристики h(v) ≤ d(v,t) алгоритм исследует меньше вершин. Используется в GPS-навигации, играх, планировании пути роботов. При h = 0 вырождается в Дейкстру.