Информатика · объяснение и практика
Поток и разрез: как получить проверяемую верхнюю границу
Разрез сети как доказательство оптимальности: направленные ёмкости через границу, верхняя оценка потока и совпадение с допустимым решением.

В теме Графы и маршруты · Учебная карта
В маршруте Графы, разрезы и динамические запросы · 10 тем
Главная мысль
Разрез делит вершины потоковой сети на две группы: источник находится в первой, сток — во второй. Ёмкость разреза складывается только из направленных рёбер первой группы во вторую. Любой допустимый поток ограничен сверху этой величиной.
Граница задаётся группами вершин
Чтобы задать разрез, недостаточно нарисовать произвольную линию между некоторыми рёбрами. Нужно явно распределить все вершины по двум сторонам и оставить источник со стоком на разных сторонах. После этого однозначно определяется, какие направленные связи пересекают границу наружу из стороны источника.
Рёбра внутри одной стороны в сумму не входят. Рёбра через границу в обратном направлении тоже не прибавляют к ёмкости разреза. Они могут быть важны для допустимого движения или вычисления чистого потока, но не являются дополнительной возможностью вывести поток из первой стороны во вторую.
Сопоставляем верхнюю оценку с найденным потоком
Рассмотрим сеть с рёбрами S→A ёмкости 3,A→T ёмкости 3,S→B ёмкости 5,B→T ёмкости 5. По ветке через A можно провести 3,по ветке через B —5. Вместе получается допустимый поток 8: ограничения рёбер и сохранение во внутренних вершинах соблюдены.
Разрез, в котором на стороне источника остаётся только S,имеет ёмкость 3+5=8. Значит, любое решение ограничено восьмью, а наше решение уже достигает восьми. Эти два независимых факта доказывают оптимальность: больше нельзя, а указанное количество действительно возможно.
Пример
Допустимый поток 8 и разрез ёмкости 8 совпали. Следовательно,8 — значение максимального потока и ёмкость минимального разреза.
Одна только маленькая граница дала бы верхнюю оценку. Одно только хорошее распределение дало бы достижимый результат. Совпадение оценок закрывает промежуток между ними.
Не объявляем любую границу минимальной
Если найден поток 7,а выбранный разрез имеет ёмкость 9,это не доказывает, что ответ равен одному из этих чисел. Пока установлены только нижняя достижимая граница 7 и верхняя граница 9. Возможно, поток удастся увеличить или найти другой более тесный разрез.
После завершённого поиска максимального потока один минимальный разрез получают по достижимости источника в остаточной сети через положительные остаточные возможности. До завершения алгоритма такая граница ещё не обязана давать нужное доказательство. В задаче могут существовать разные минимальные разрезы с одной ёмкостью; уникальность самого разбиения из теоремы не следует.
От чтения к действию
А теперь — вы
Частые вопросы
В ёмкость разреза входят рёбра из стороны стока назад?
Нет. Складывают ёмкости направленных рёбер из стороны источника в сторону стока.
Совпадение допустимого потока с ёмкостью разреза доказывает максимум?
Да. Поток достигает верхнего ограничения, превышать которое ни один допустимый поток не может.
Углублённый разбор
Непересекающиеся пути и минимальный вершинный разделитель
Независимость маршрутов может означать отказоустойчивость по вершинам, а не по рёбрам. Теорема Менгера связывает максимальное число путей с общими только концами и минимальное число внутренних вершин, удаление которых разрывает связь. Расщепление вершин делает такую задачу обычным целочисленным потоком.
Перед началом: Максимальный поток и разрез; Простой путь.
Сначала уточняем, что разрешено путям разделять
Рассмотрим конечный простой неориентированный граф и различные несмежные вершины s,t. Пути могут совместно использовать s,t, но никакую другую вершину. Разделитель X не содержит s,t и пересекает каждый s–t путь. Любые k внутренне непересекающихся путей требуют не меньше k вершин разделителя: каждая его вершина может перекрыть не больше одного из этих путей.
Несмежность терминалов существенна для этой простой формулировки. Если есть непосредственное ребро s–t, удалить внутренние вершины недостаточно, чтобы его разрушить, и минимальный разделитель такого вида не существует. Теорема Менгера утверждает равенство двух конечных величин именно при выбранных условиях; терминалы нельзя незаметно разрешить удалять, иначе ответ почти всегда станет тривиальным.
Единичная внутренняя дуга кодирует ёмкость вершины
Каждую внутреннюю вершину v заменим v_in и v_out с дугой v_in→v_out ёмкости 1. Исходное ребро uv заменяется дугами из выхода одного конца во вход другого в обе стороны; их ёмкость берём M=|V|. Терминалы не расщепляем. Любой проход через v обязан пересечь единичную дугу, поэтому два целочисленных маршрута не смогут совместно использовать v.
Из целочисленного максимального потока удаляем циклы и выделяем единичные s–t маршруты. После склеивания половин получаем нужные пути. С другой стороны, удаление всех внутренних вершин даёт разрез ёмкости |V|−2<M, поскольку s,t несмежны. Значит минимальный разрез не использует дорогие исходные дуги и состоит из внутренних единичных. Они задают вершинный разделитель. Теорема о потоке и разрезе теперь доказывает равенство.
Два свидетельства проверяются в исходном графе
Для ответа не обязательно доверять каждой детали потоковой реализации: достаточно предъявить k путей с непересекающимися внутренностями и разделитель размера k. Первое даёт нижнюю, второе верхнюю границу. Проверка разделителя — обычная достижимость после его удаления. Рёберно непересекающиеся пути являются более слабым требованием: несколько маршрутов могут проходить через одну внутреннюю вершину, не разделяя ни одного ребра, и для вершинной устойчивости это уже недопустимо.
Два маршрута и две критические вершины
Условие. У графа рёбра sa,sb,ac,bc,bd,ct,dt; других рёбер нет. Найдите максимум внутренне непересекающихся s–t путей и минимальный внутренний разделитель.
- Путь s–a–c–t использует внутренние вершины a,c. Путь s–b–d–t использует b,d. Эти наборы не пересекаются, значит максимум не меньше 2.
- Удалим X={c,d}. Оба ребра в t исчезают, поэтому из s до t больше нельзя дойти. Разделитель имеет размер 2 и даёт верхнюю границу 2.
- Следовательно обе оптимальные величины равны 2. В расщеплённой сети два маршрута используют разные внутренние дуги ёмкости 1.
- Одно удаление недостаточно: любой одиночный внутренний v лежит не больше чем на одном из двух предъявленных путей, поэтому второй остаётся. Это независимо проверяет минимальность X.
Ответ. Максимум путей и минимум разделителя равны 2; свидетели — два указанных пути и X={c,d}.
Проверка. Полный перебор внутренних подмножеств размера 0 и1 сохраняет достижимость t. Перебор простых путей независимо находит максимальное семейство размера 2, а удаление c,d разрывает связь.
Где легко ошибиться. Не подменяйте вершинную ёмкость единичной ёмкостью исходных рёбер. Это решает другую задачу устойчивости и может разрешить совместное прохождение через внутренний узел.
Проверьте понимание
Вопросы к этой главе
Можно ли удалить сам t и получить разделитель размера 1?
В выбранной задаче нет: разделитель обязан состоять из внутренних вершин. Иначе терминальный отказ сделал бы искомую меру почти бессодержательной и нарушил бы сопоставление с внутренне независимыми маршрутами.
Что если s и t уже несвязны?
Пустой разделитель подходит, а путей нет. Обе величины равны 0. Расщеплённая сеть также имеет нулевой максимальный поток; связность исходного графа отдельно не предполагается.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Alexander Hulpke: Combinatorics, §3 Menger’s theorem
Прочитаны определения независимых внутренних путей, вершинного разделителя и Theorem35 для несмежных терминалов. Расщепление с единичными внутренними дугами и конкретные пути/разделитель даны автором главы; источник доказывает теорему другим способом.
Дерево разрезов хранит все парные минимальные разрезы
Дерево Гомори — Ху хранит значения минимальных разрезов между всеми парами вершин неориентированной сети. Его веса являются ёмкостями разрезов исходного графа, а не весами выбранных исходных рёбер. Вместе с числом дерево даёт и само разбиение, удостоверяющее верхнюю границу.
Перед началом: Неориентированный разрез; Единственный путь в дереве.
Фундаментальный разрез задаёт сильный сертификат дерева
Пусть G — конечный неориентированный граф с неотрицательными ёмкостями. Дерево T строится на том же множестве вершин. Для каждого его ребра uv удаление ребра разбивает T на две части. Требуем, чтобы соответствующий разрез исходного G был минимальным u–v разрезом, а вес ребра T равнялся его ёмкости. Это условие определяет дерево разрезов и позволяет проверять его по отдельным рёбрам.
Теорема Гомори — Ху гарантирует существование такого дерева и построение с |V|−1 вычислениями минимального разреза. Веса дерева могут вообще не совпадать с весами исходных рёбер, и ребро дерева не обязано существовать в G. Поэтому это не минимальное остовное дерево. Его цель — сохранить разрезы, а не суммарную длину или минимаксный вес маршрутных рёбер.
Минимальное ребро пути даёт точное значение для любой пары
Для s,t найдём путь в T и его самое лёгкое ребро e. Удаление e даёт s–t разрез исходного графа, значит λ(s,t)≤w(e). Обратная граница следует из свойства λ(x,z)≥min(λ(x,y),λ(y,z)): любой x–z разрез отделяет y хотя бы от одного конца. Повторяя это по пути и используя значения его соседних пар, получаем λ(s,t)≥min w(e).
Так дерево хранит квадратичное число парных ответов линейным числом рёбер. При нескольких одинаковых минимумах можно выбрать любое соответствующее ребро пути; полученный фундаментальный разрез будет оптимальным. Это не означает, что найдены все оптимальные разрезы данной пары. Разные деревья также могут одинаково правильно кодировать одну сеть.
Границы применимости определяются симметрией разреза
Для ориентированной сети значение разреза s→t может отличаться от t→s, тогда одно неориентированное дерево уже не может хранить оба ответа в такой форме. Нулевые ёмкости допустимы: несвязные компоненты можно соединить в дереве нулевыми рёбрами. Для проверки конкретного примера полезно независимо перебрать все разбиения малой исходной сети, а не сравнивать дерево с другой процедурой чтения его же пути.
Одна тройка рёбер хранит шесть ответов
Условие. В G рёбра AB=2,AC=1,BC=3,BD=4; других рёбер нет. Проверьте дерево T с рёбрами BA=3,BC=4,BD=4 и найдите минимальный C–D разрез.
- Удаление BA в T выделяет {A}. Ёмкость этого разреза в G равна 2+1=3; прямой перебор A–B разрезов показывает минимум 3.
- Удаление BC выделяет {C}. Ёмкость равна 1+3=4, и это минимальный B–C разрез. Удаление BD выделяет {D} с единственным ребром ёмкости 4; это минимальный B–D разрез.
- Значит выполнено фундаментальное условие для всех трёх рёбер. На пути C–B–D минимальный вес равен 4, поэтому λ(C,D)=4.
- Можно выбрать разрез {C} либо {D}, оба имеют ёмкость 4 и разделяют C,D. Для сравнения λ(A,D)=min(3,4)=3: отдельное ребро BD не определяет все парные ответы.
Ответ. T является деревом Гомори — Ху; минимальный C–D разрез имеет ёмкость 4.
Проверка. Полный перебор всех разрезов четырёхвершинного G подтверждает значения для шести пар: AB=3,AC=3,AD=3,BC=4,BD=4,CD=4. Они независимо совпадают с минимумами на путях T.
Где легко ошибиться. Не подставляйте в формулу веса произвольного остовного дерева исходной сети. Нужны сертифицированные ёмкости разрезов и фундаментальное свойство, а не просто наличие дерева на тех же вершинах.
Проверьте понимание
Вопросы к этой главе
Всегда ли самый лёгкий разрез сети виден в дереве?
Да. Минимальный вес ребра T равен глобальному минимальному разрезу, потому что он является минимумом всех парных значений. Его фундаментальное разбиение даёт сам оптимальный разрез.
Хранит ли дерево все варианты минимального C–D разреза?
Нет. Оно позволяет получить хотя бы один оптимальный разрез и точное значение для пары. Полное семейство может быть значительно больше числа рёбер дерева и требует другого представления.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Chandra Chekuri: Gomory–Hu Trees, Definition2/Theorem1
Прочитаны свойства фундаментального разреза дерева и минимум на пути, доказательство через неравенство для парных разрезов. Конспект курса Illinois размещён у преподавателя Pittsburgh; свой граф на4 вершинах и полный перебор разрезов отличаются от Figure1.
Минимальная стоимость потока и отсутствие отрицательного остаточного цикла
Для потока заданной величины недостаточно доказать допустимость или отсутствие увеличивающего пути. Стоимость можно уменьшить, не меняя величину, если в остаточной сети есть отрицательный цикл. Отсутствие таких циклов даёт точный критерий оптимальности по цене.
Перед началом: Допустимый поток и сохранение баланса; Остаточные дуги и стоимость пути.
Обратная дуга возвращает уже заплаченную стоимость
Рассматриваем конечную сеть с ёмкостями и линейной стоимостью единицы потока. Баланс каждой вершины фиксирован; в частности, фиксирована величина s–t потока. Для дуги u→v ёмкости U, цены c и текущего потока f остаточная сеть содержит прямую дугу ёмкости U−f и цены c, если U−f>0. При f>0 имеется обратная дуга v→u ёмкости f и цены −c.
Обратная дуга означает уменьшение старого потока, поэтому возвращает ранее внесённую цену. Если пройти остаточный цикл и изменить поток на одинаковую величину по всем его дугам, баланс каждой вершины сохранится. Допустимая величина изменения ограничена наименьшей остаточной ёмкостью цикла. Стоимость изменится на произведение этой величины и суммы цен цикла.
Отрицательный цикл является полным критерием
Если сумма цен цикла отрицательна, любое положительное допустимое продвижение по нему удешевляет текущий поток. Поэтому оптимальный поток не может иметь такой цикл. Важно, что цикл может включать обратные дуги: поиск только среди исходных направлений пропустит перестройку уже оплаченного маршрута.
Обратно, разность любого другого допустимого потока с теми же балансами представима как неотрицательная циркуляция в остаточной сети текущего потока. Конечная циркуляция раскладывается на направленные циклы. При отсутствии отрицательных циклов стоимость каждого слагаемого неотрицательна. Следовательно, никакое другое допустимое решение не дешевле. Фиксированные балансы здесь необходимы: иначе разность могла бы иметь незамкнутую часть.
Потенциалы дают короткий проверяемый сертификат
Вместо перечисления всех циклов можно предъявить числа h(v), для которых каждая положительная остаточная дуга имеет приведённую цену c(u,v)+h(u)−h(v)≥0. В сумме по циклу потенциалы сокращаются. Значит, исходная цена каждого цикла также неотрицательна. Проверка требует одного просмотра остаточных дуг.
При отсутствии отрицательного цикла такие потенциалы можно получить кратчайшими расстояниями из дополнительного источника с нулевыми дугами ко всем вершинам. Это сертификат стоимости уже допустимого потока, а не свидетельство максимальности его величины. Достижение требуемого баланса и соблюдение ёмкостей проверяются отдельно, до применения ценового критерия.
Перенаправление единицы с сохранением общего последнего участка
Условие. Все ёмкости равны 1. Дуги и цены: s→a:4, a→c:0, c→t:2, s→b:1, b→c:1, a→b:0. Текущий единичный поток идёт s–a–c–t. Найдите поток минимальной стоимости той же величины.
- Исходный поток допустим и стоит 4+0+2=6. В остаточной сети имеются обратные дуги a→s цены −4 и c→a цены 0.
- Цикл s→b→c→a→s имеет цену 1+1+0−4=−2 и минимальную остаточную ёмкость 1. Он заменяет первые два участка потока, не изменяя баланс и общий участок c→t.
- Продвигаем одну единицу по циклу. Дуги s→a,a→c обнуляются, s→b,b→c получают поток 1, c→t сохраняет поток 1. Новая стоимость равна 1+1+2=4.
- Положительные остаточные дуги теперь s→a:4, a→c:0, a→b:0, c→b:−1, b→s:−1, t→c:−2. Возьмём h(s)=−4,h(a)=0,h(b)=−3,h(c)=−2,h(t)=0.
- Приведённые цены в этом порядке равны 0,2,3,0,0,0. Все неотрицательны, поэтому отрицательных циклов нет и стоимость 4 оптимальна при фиксированной величине 1.
Ответ. Оптимальный поток идёт s–b–c–t и имеет стоимость 4 вместо 6.
Проверка. Независимый перебор всех 64 двоичных назначений потоков проверяет ёмкости и заданные балансы. Допустимые единичные решения имеют стоимости 4,6,7; минимум совпадает с сертификатом потенциалов.
Где легко ошибиться. Не используйте отсутствие отрицательного цикла как доказательство максимальной величины потока. Критерий сравнивает только решения с одинаковыми балансами.
Проверьте понимание
Вопросы к этой главе
Зачем отрицательная цена у обратной дуги?
Уменьшая поток исходной дуги на единицу, мы вычитаем её цену из общей стоимости. Знак обратной цены выражает именно эту отмену, а не новую платную перевозку.
Почему нельзя искать только отрицательный путь от s до t?
Такой путь изменяет величину потока. Для удешевления при фиксированной величине нужна циркуляция; в примере она использует обратные участки и оставляет общий последний участок c→t без изменения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- MIT 6.854: Costs in flow networks
Остаточные цены и критерий отсутствия отрицательного цикла при сравнении потоков одинаковой величины. Сертификат неотрицательных приведённых цен обоснован в главе отдельно.
Стоер—Вагнер находит глобальный минимальный разрез без заданных терминалов
Глобальный минимальный разрез выбирает самую дешёвую непустую границу без заранее заданной пары источник–сток. Алгоритм Стоера—Вагнера строит фазы максимального присоединения: следующей берётся вершина с наибольшим суммарным весом связей в уже набранное множество. Последние две вершины фазы определяют парный минимальный разрез; затем они сливаются, сохраняя возможность найти глобальный оптимум на меньшем графе.
Перед началом: Ёмкость неориентированного разреза; Стягивание вершин и сложение параллельных весов.
Максимизируется связь со всем набранным множеством
Конечный связный неориентированный граф хотя бы из двух вершин с неотрицательными весами; обе стороны разреза непусты, терминалы заранее не фиксируются.
Начинаем фазу с произвольной вершины. Для каждой ещё не взятой вершины храним сумму весов её рёбер в набранное множество A. Каждый раз добавляем вершину максимальной суммы, затем увеличиваем ключи её оставшихся соседей. Это не выбор одного самого тяжёлого ребра и не минимальный приоритет Дейкстры.
Обозначим последние добавленные вершины через s,t. Теорема фазы утверждает: разрез, отделяющий только t от остальных текущих супервершин, является минимальным s–t разрезом текущего графа. Его вес уже хранится в последнем ключе t. Пара s,t является результатом поиска, а не заданием пользователя.
Почему можно слить последние две вершины
Любой глобальный разрез либо разделяет s,t, либо оставляет их вместе. В первом случае он не может быть дешевле найденного минимального s–t разреза. Во втором случае он полностью представим после слияния s и t. Поэтому глобальный ответ равен минимуму веса текущей фазы и глобального ответа стянутого графа.
При слиянии веса связей s и t к каждой другой супервершине складываются, а внутренние рёбра исчезают. Каждая супервершина хранит множество исходных вершин. Если забыть эти множества, правильное число не позволит восстановить исходное оптимальное разбиение. Нельзя менять сумму параллельных связей на минимум: это занизило бы ёмкости сохраняемых границ.
Нужны все фазы, а не только первая маленькая граница
Повторяем фазы, пока не останется одна супервершина, сохраняя лучший вес и соответствующую исходную сторону t. В простой матричной реализации одна фаза требует O(n²), все фазы — O(n³). Более быстрые очереди меняют оценку, но не нужны для обоснования маленького точного примера.
Один фазовый разрез ещё не обязан быть глобально минимальным. Он гарантирован только для найденной на этой фазе пары. В отличие от дерева Гомори—Ху здесь сохраняется один глобальный ответ, а не все парные значения. Для проверки короткой сети отдельно перебирают все непустые разбиения исходных вершин и суммируют исходные пересекающие рёбра.
Два плотных треугольника разделяются двумя лёгкими связями
Условие. Вершины A,…,F. Рёбра AB:4,AC:5,BC:6,DE:3,DF:4,EF:5,CD:2,BE:1. В каждой фазе начинайте с A и при равных ключах выбирайте меньший сохраняемый буквенный представитель.
- Первая фаза присоединяет A,C,B,D,E,F. Последний ключ F равен DF+EF=9; сохраняем сторону {F}, затем сливаем F в E.
- Вторая фаза даёт A,C,B,D,EF с весом последней стороны 8. После слияния EF в D третья фаза имеет порядок A,C,B,DEF и последний ключ 3.
- Сторона третьей фазы соответствует исходному множеству {D,E,F}. Через её границу идут только CD веса 2 и BE веса 1. Сумма равна 3; внутренние веса треугольников в неё не входят.
- Оставшиеся фазы дают веса 12 и 9. Минимум всех пяти фаз равен 3. Сохраняем разбиение {A,B,C}|{D,E,F}, а не последний одноточечный разрез.
Ответ. Глобальный минимальный разрез имеет вес 3 и отделяет два треугольника друг от друга.
Проверка. Независимый перебор 31 непустого разбиения с A на фиксированной стороне подтверждает минимум 3. Все одноточечные разрезы имеют веса не меньше 9, поэтому поиск только самого лёгкого набора рёбер вокруг одной исходной вершины здесь не сработал бы.
Где легко ошибиться. Не заменяйте максимальную сумму рёбер в A на максимум отдельного ребра. Доказательство минимальности фазового разреза относится именно к суммарному ключу.
Проверьте понимание
Вопросы к этой главе
Почему в третьей фазе один узел обозначает сразу D,E,F?
Он хранит объединённое множество после предыдущих стягиваний. Вес его внешних связей равен сумме исходных связей через эту границу; внутренние рёбра уже исчезли.
Нужно ли угадывать, какие вершины окажутся терминалами?
Нет. Максимальное присоединение само выбирает последнюю пару каждой фазы. Возможность выбрать такую пару отличает задачу глобального разреза от заранее заданного s–t запроса.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Uri Zwick — Global minimum cuts, §2
Максимальное присоединение, теорема последней пары и сохранение оптимума при стягивании. Два треугольника, все пять фаз и независимый перебор разрезов рассчитаны отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Остаточная сеть: зачем потоку обратные рёбра
Остаточная сеть потока: свободная пропускная способность, обратное ребро как отмена и увеличение по узкому месту пути.
Открыть темуПаросочетание: как чередующийся путь увеличивает число пар
Увеличивающий путь в двудольном паросочетании: перестановка занятых назначений вместо жадного отказа свободной вершине.
Открыть тему