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

Потоки в сетях - это теория, за которой стоят реальные деньги. Пропускная способность интернет-магистралей, распределение трафика в CDN, назначение задач в Jira, маршрутизация в авиакомпаниях - всё это задачи max-flow.

• **CDN и сети:** нахождение min-cut показывает узкие места сети, расширение которых даёт максимальный прирост пропускной способности
• **Планировщики задач:** Kubernetes, Apache Mesos распределяют контейнеры по нодам через алгоритмы паросочетания
• **Биоинформатика:** выравнивание последовательностей ДНК сводится к задаче паросочетания в двудольном графе
• **Финансы:** оптимизация потоков капитала через транзакционные сети - задача min-cost max-flow

Предварительные знания

• Planarity and Graph Coloring

Сети и потоки: базовые понятия

**Транспортная сеть** - ориентированный граф G = (V, E) с двумя выделенными вершинами: **исток s** (source) и **сток t** (sink). Каждое ребро (u, v) имеет **пропускную способность** c(u, v) ≥ 0 - максимальное количество единиц, которое можно пропустить через ребро.

**Поток f** - функция f: E → ℝ≥0, удовлетворяющая: 1. **Ограничение пропускной способности:** 0 ≤ f(u,v) ≤ c(u,v) для каждого ребра. 2. **Закон сохранения потока:** для каждой вершины v ≠ s, t: сумма входящих потоков = сумма исходящих. **Величина потока** |f| = сумма потоков из истока s.

Закон сохранения потока - это «закон Кирхгофа» для потоков: что «вошло» в промежуточную вершину - то и «вышло». Нарушение этого закона означает, что где-то теряется или создаётся ресурс - физически невозможно.

Форд-Фалкерсон и Эдмондс-Карп

**Алгоритм Форда-Фалкерсона**: многократно находит **увеличивающий путь** (augmenting path) из s в t в **остаточной сети** и пропускает через него максимально возможный поток. Остаточная сеть учитывает и обратные рёбра - возможность «отменить» ранее отправленный поток.

**Эдмондс-Карп** - реализация Форда-Фалкерсона с BFS (кратчайший путь по числу рёбер). Сложность: O(VE²) - не зависит от величины потока. Базовый Форд-Фалкерсон с DFS: O(E × |f*|), где |f*| - величина максимального потока. На иррациональных весах может не сходиться!

Теорема max-flow min-cut

**Разрез (s, t)-cut** - разбиение вершин на два множества S ∋ s и T ∋ t, где T = V \ S. **Пропускная способность разреза** = сумма пропускных способностей рёбер из S в T. Максимальный поток ограничен пропускной способностью любого разреза.

**Теорема max-flow min-cut (Форд, Фалкерсон, 1956):** величина максимального потока из s в t равна пропускной способности минимального (s, t)-разреза. Иными словами: узкое место сети точно определяет её пропускную способность.

Практическое следствие: **min-cut показывает узкие места**. Если нужно увеличить пропускную способность сети - расширяйте именно рёбра минимального разреза, а не случайные. Все остальные улучшения не дадут прироста.

В теории надёжности сетей min-cut отвечает на вопрос: «сколько рёбер нужно удалить, чтобы отключить t от s?». Это **связность рёбер** (edge connectivity) - важная характеристика отказоустойчивости.

Двудольное паросочетание как задача потока

**Двудольный граф** - граф, вершины которого разбиты на два непересекающихся множества L и R, и рёбра идут только между L и R. **Паросочетание** - подмножество рёбер, в котором каждая вершина встречается не более одного раза. **Максимальное паросочетание** - паросочетание максимальной мощности.

**Теорема Холла (1935):** двудольный граф имеет совершенное паросочетание тогда и только тогда, когда для любого подмножества S ⊆ L выполняется |N(S)| ≥ |S|, где N(S) - множество соседей S. На практике: нет «узкого горлышка» в назначениях.

Реальные применения двудольного паросочетания: назначение задач исполнителям (scheduling), маршрутизация запросов на серверы (load balancing), составление пар в системах рекомендаций (recommender systems), компиляция bipartite-запросов в базах данных.

Алгоритм Куна (венгерский алгоритм для поиска паросочетания) работает за O(VE) и не требует явного построения flow-сети. Однако сведение к max-flow универсально: оно работает для взвешенных паросочетаний и более сложных ограничений.

Ключевые идеи

• **Транспортная сеть:** ориентированный граф с исток s, стоком t и пропускными способностями рёбер
• **Закон сохранения:** поток в каждую промежуточную вершину = поток из неё
• **Эдмондс-Карп:** BFS-реализация Форда-Фалкерсона, O(VE²), гарантированно полиномиальная
• **Max-flow = min-cut:** максимальный поток равен пропускной способности минимального разреза
• **Двудольное паросочетание:** сводится к max-flow добавлением supersource и supersink

Связанные темы

Потоки в сетях объединяют идеи из теории графов, линейного программирования и комбинаторики.

• Планарность и раскраска — Двудольные графы (χ = 2) обладают совершенным паросочетанием при условии Холла
• Деревья и их свойства — Остовные деревья - частный случай потока без возвратных рёбер
• Теория графов: основы — BFS/DFS - ядро алгоритмов поиска увеличивающих путей

Вопросы для размышления

• Как задача распределения задач между разработчиками формально записывается как задача max-flow? Нарисуйте граф для 3 разработчиков и 4 задач.
• Почему базовый Форд-Фалкерсон с DFS может зациклиться на иррациональных пропускных способностях, а Эдмондс-Карп нет?
• Что означает min-cut физически для задачи пропускной способности интернет-провайдера?

Связанные уроки

• alg-14-dijkstra