# Питер Шор о теореме о максимальном потоке и минимальном разрезе Источник: https://www.youtube.com/watch?v=pX-HnYwO454 Канал: MIT OpenCourseWare Опубликовано: 17.12.2025 --- В лекции MIT OpenCourseWare знаменитый профессор Питер Шор разбирает одну из фундаментальных концепций комбинаторной оптимизации — теорему о максимальном потоке и минимальном разрезе. На примере сетевых моделей он демонстрирует глубинную связь между первообразной и двойственной задачами линейного программирования. Этот математический аппарат находит неожиданное применение не только в анализе коммуникаций, но и в доказательстве классических теорем теории графов, таких как теорема Кёнига. ## 🌐 Сети, потоки и интуиция разрезов [[JUMP:0:17]] Профессор Питер Шор начинает лекцию с определения базовых понятий сетевых моделей. Сетью может выступать любая система коммуникаций: от физических трубопроводов и дорожных систем до электронных сетей передачи данных. У каждого ребра в такой системе есть фиксированная пропускная способность. Главная задача исследователя — определить, какой максимальный объем условного потока можно переместить из источника в сток. Для обозначения ключевых узлов математики традиционно используют латинские буквы $s$ (source — источник) и $t$ (sink — сток). Шор с иронией замечает, что если выбор буквы $s$ интуитивно понятен, то логика присвоения стоку обозначения $t$ до сих пор остается для него загадкой. Чтобы продемонстрировать логику поиска решений, лектор рисует на доске граф с числовыми ограничениями пропускной способности ребер (6, 4, 3 единицы и т.д.). Вместе со слушателями в аудитории он пошагово распределяет потоки вдоль различных путей. Активно взаимодействуя со студентами и принимая их подсказки, Шор строит корректное распределение, при котором суммарная величина потока на выходе составляет 9 единиц, а нагрузка на ребра не превышает их лимиты. Однако возникает закономерный вопрос: как математически доказать, что найденный поток действительно является максимально возможным? Для этого вводится понятие разреза. Разрезом называется такое разделение множества вершин графа на две части, при котором источник $s$ попадает в одно подмножество, а сток $t$ — в другое. Пропускная способность разреза рассчитывается как сумма емкостей всех ребер, направленных из подмножества источника наружу. Любой поток из точки $s$ в точку $t$ физически обязан пересечь этот разрез, поэтому величина максимального потока никогда не может превысить пропускную способность минимального из возможных разрезов. Центральным утверждением лекции становится знаменитая теорема: величина максимального потока всегда строго равна значению минимального разреза. ## 📊 Линейное программирование и двойственность потоков [[JUMP:9:38]] Профессор Шор объясняет, что равенство максимального потока и минимального разреза — это не просто удачное свойство графов, а прямое следствие теоремы о сильной двойственности в линейном программировании. В этой парадигме поиск максимального потока формулируется как прямая задача (primal LP), а поиск минимального разреза становится решением зеркальной двойственной задачи (dual LP). Для составления прямой задачи Шор вводит переменные $x_{ij}$, обозначающие реальный поток, проходящий через ребро между узлами $i$ и $j$. Математическая модель требует соблюдения строгих рамок. Прямая задача линейного программирования включает в себя следующие условия: * Закон сохранения потока: для любого промежуточного узла сумма входящих потоков минус сумма выходящих должна быть равна нулю. * Ограничение пропускной способности: поток на каждом ребре $x_{ij}$ не может превышать заданный лимит ребра $u_{ij}$. * Условие неотрицательности: поток на ребре не может быть меньше нуля. Главная цель этой системы уравнений — максимизировать переменную $z$, которая отражает совокупный объем потока, приходящий в финальный сток $t$. Переходя к построению двойственной задачи, профессор связывает каждое ограничение прямой модели с новыми двойственными переменными. Для ограничений пропускной способности ребер вводится переменная $\alpha_{ij}$, а для баланса потоков в узлах — потенциалы вершин $\beta_i$. Поскольку исходная задача была направлена на максимизацию, двойственная система стремится к минимизации. Её целевая функция выглядит как минимизация выражения $\sum \alpha_{ij} u_{ij}$ при условии, что для каждого ребра выполняется неравенство $\alpha_{ij} + \beta_i - \beta_j \ge 0$. ## 🧩 Секрет целочисленности: почему разрез всегда минимален [[JUMP:23:51]] Наиболее сложная и глубокая часть лекции посвящена объяснению того, почему непрерывное оптимальное решение двойственной задачи линейного программирования гарантированно дает дискретные (целочисленные) параметры разреза. Профессор задает граничные потенциалы вершин: для источника $\beta_s = 0$, для стока $\beta_t = 1$. В процессе оптимизации переменные $\alpha_{ij}$ стремятся к минимально возможным значениям, принимая вид $\max(0, \beta_j - \beta_i)$. Если все потенциалы узлов $\beta_i$ принимают строго полярные значения 0 или 1, то ребра, у которых параметр $\alpha_{ij}$ равен 1, автоматически образуют искомый разрез графа. Чтобы доказать отсутствие дробных значений в оптимуме, Шор предлагает оригинальный геометрический метод. Он мысленно проецирует все вершины графа на отрезок числовой прямой от 0 до 1 в соответствии с их вычисленными потенциалами $\beta_i$. Если провести через этот отрезок произвольную вертикальную линию, она пересечет определенный набор ребер, формируя физический разрез. При этом ребра, идущие в обратном направлении, не вносят вклад в пропускную способность, поскольку их вклад обнуляется формулой. В результате целевую функцию двойственной задачи удается представить как интегральную взвешенную сумму (или среднее значение) пропускных способностей различных разрезов. По базовым математическим законам среднее значение непрерывного набора величин не может быть меньше минимального элемента этого набора. Таким образом, для минимизации функции наиболее выгодно сдвинуть все потенциалы вершин к краям диапазона (в 0 или 1), выбрав разрез с наименьшей пропускной способностью. Это изящно доказывает эквивалентность двойственного решения минимальному разрезу. Питер Шор подчеркивает, что подобный подробный анализ двойственных систем — это фундаментальное правило комбинаторной оптимизации, позволяющее находить глубокие скрытые смыслы в математических моделях. ## 🔄 Алгоритм увеличивающихся путей и остаточные сети [[JUMP:50:37]] Установив эквивалентность потоков и разрезов, профессор переходит к вопросу вычислений: если все емкости ребер в сети выражены целыми числами, гарантирует ли это существование строго целочисленного максимального потока?. Напрямую из уравнений линейного программирования это свойство неочевидно, поэтому Шор предлагает использовать алгоритмический подход — метод увеличивающихся путей. Базовый принцип алгоритма заключается в итеративном поиске любого доступного пути от источника к стоку и проталкивании по нему максимально возможного объема потока. Этот объем лимитируется минимальной остаточной емкостью среди ребер выбранного пути. Профессор наглядно демонстрирует, что «наивное» заполнение первых попавшихся путей может завести вычисления в тупик, заблокировав оптимальное распределение. Ключом к решению этой проблемы становится концепция остаточных сетей (residual networks). В остаточной сети для каждого ребра исходного графа динамически рассчитываются новые параметры. Правила пересчета емкостей в остаточной сети выглядят так: * Если по ребру течет поток $x_{ij}$, меньший его емкости $u_{ij}$, в остаточной сети сохраняется прямое ребро с доступной емкостью $u_{ij} - x_{ij}$. * Если текущий поток на ребре $x_{ij}$ больше нуля, в остаточной сети создается виртуальное обратное ребро с пропускной способностью, равной величине этого потока. Наличие обратных ребер позволяет алгоритму «отменять» ранее принятые неоптимальные шаги. Проталкивая поток по обратному ребру, мы фактически уменьшаем реальный поток в исходной сети. Шор демонстрирует на схеме, как за счет циклического обновления остаточной сети итоговый поток успешно увеличивается до максимального значения 5. Когда в остаточной сети физически исчезают любые свободные пути от $s$ к $t$, алгоритм останавливается, а группа вершин, до которых еще можно добраться из источника, наглядно очерчивает границы минимального разреза. ## 🤝 Применение теории: Теорема Кёнига для двудольных графов [[JUMP:1:08:16]] В финальной части лекции Питер Шор иллюстрирует прикладную ценность изученной теоремы, с ее помощью доказывая классическое положение дискретной математики — теорему Кёнига для двудольных графов. Данная теорема утверждает, что в любом двудольном графе размерность максимального паросочетания (matching) строго равна мощности минимального вершинного покрытия (vertex cover). Паросочетание представляет собой подмножество ребер, не имеющих общих смежных вершин, а вершинное покрытие — это набор узлов, который содержит хотя бы один конец каждого ребра графа. Для доказательства Шор трансформирует исходный двудольный граф в сеть для поиска максимального потока. Слева от графа добавляется узел искусственного источника $s$, соединенный со всеми вершинами левой доли ребрами с пропускной способностью 1. Справа добавляется узел стока $t$, соединенный со всеми вершинами правой доли аналогичными единичными ребрами. Емкости оригинальных внутренних ребер графа принимаются равными бесконечности. Благодаря тому, что внешние ребра имеют строго единичную емкость, целочисленный максимальный поток в такой системе выберет только уникальные, не пересекающиеся в узлах внутренние ребра. Это подмножество ребер и будет являться максимальным паросочетанием. В свою очередь, минимальный разрез в созданной сети будет вынужден перекрыть все пути сквозь граф, проходя исключительно через внешние ребра с весом 1. Узлы, прилегающие к этим разрезанным внешним ребрам, составят идеальное вершинное покрытие минимального размера. Равенство максимального потока и минимального разреза автоматически делает равными объемы паросочетания и покрытия, что завершает элегантное доказательство теоремы Кёнига.