Информатика · объяснение и практика
Остаточная сеть: зачем потоку обратные рёбра
Остаточная сеть потока: свободная пропускная способность, обратное ребро как отмена и увеличение по узкому месту пути.

В теме Графы и маршруты · Учебная карта
В маршруте Графы, разрезы и динамические запросы · 10 тем
Главная мысль
Остаточная сеть показывает, как ещё можно изменить текущий поток. Прямое остаточное ребро позволяет добавить до свободной пропускной способности, обратное — отменить часть уже проведённого потока. Обратное ребро не означает новую физическую связь исходной сети.
Сначала проверяем допустимость текущего потока
В ориентированной сети каждой связи задана неотрицательная пропускная способность. Поток не должен её превышать, а во внутренних вершинах суммарный вход согласуется с суммарным выходом. Источник создаёт общий поток, сток принимает его. В этом учебном разборе нет нижних обязательных границ или стоимости передачи.
Если по ребру u→v ёмкости 5 уже проходит 3,вперёд можно добавить ещё 2. В обратном направлении остаточная возможность равна 3: столько можно отменить из текущего назначения. Эти числа описывают допустимое изменение существующего потока, а не две независимые исходные трубы ёмкостей 2 и 3.
Исправляем прежний выбор пути
Пусть все пять исходных рёбер S→P,S→Q,P→Q,P→T,Q→T имеют ёмкость 1. Сначала отправили единицу по S→P→Q→T. Теперь S→P и Q→T заполнены. Если смотреть только на ещё свободные прямые рёбра, нового полного пути до T не видно.
Но в остаточной сети есть путь S→Q→P→T. Его участок Q→P обратный к занятому P→Q. Увеличение на единицу отменяет поток P→Q,добавляет S→Q и P→T. Итог можно представить двумя независимыми маршрутами S→P→T и S→Q→T,каждый с единицей. Общее значение стало 2.
Пример
После первой передачи P→Q несло 1. При движении по обратному остаточному Q→P на 1 его исходный поток становится 0,а не−1.
Обратный шаг отменяет прежнее решение. Он помогает перераспределить движение и получить второй полный маршрут без добавления нового исходного ребра.
Увеличиваем не больше узкого места
На каждом остаточном пути берут минимум доступных возможностей его рёбер. Это узкое место ограничивает единое увеличение по всему пути; выбор большего числа нарушил бы допустимость хотя бы одной связи. После шага заново обновляют прямые и обратные остаточные возможности.
Для целочисленных ёмкостей и целочисленных увеличений значение растёт минимум на единицу за успешный шаг и ограничено сверху. Для произвольных вещественных данных гарантии конкретного метода выбора путей требуют отдельного анализа. Не следует объявлять любой жадный поиск линейным или всегда быстро завершающимся только потому, что его удобно нарисовать на маленькой сети.
От чтения к действию
А теперь — вы
Частые вопросы
Обратное остаточное ребро обязано быть физическим ребром исходной сети?
Нет. Оно может обозначать только возможность отменить ранее назначенный прямой поток.
Можно увеличить поток по пути на максимум ёмкостей его рёбер?
Нет. Ограничивает минимальная остаточная возможность на этом пути, а не максимальная.
Углублённый разбор
Все минимальные разрезы из компонент остаточной сети
После нахождения одного максимального потока можно описать не один, а все минимальные разрезы. Для этого ищут множества, из которых не выходит положительная остаточная дуга. Сжатие сильно связных компонент превращает условие в замкнутость по достижимости на ациклическом графе.
Перед началом: Остаточная сеть потока; Сильно связная компонента.
Равенство границы характеризует оптимальный разрез
Зафиксируем максимальный поток f в конечной ориентированной сети с неотрицательными ёмкостями. Для любого разреза S с s∈S,t∉S разность c(S,V\S)−|f| равна сумме незаполненных прямых ёмкостей из S наружу и потоков по исходным дугам, входящим в S. Все слагаемые неотрицательны. Равенство достигается тогда и только тогда, когда все они нулевые.
В остаточной сети это означает отсутствие положительной дуги из S наружу: прямая незаполненная дуга и обратная к входящему потоку как раз описывают два типа запаса. Поэтому S является стороной минимального разреза ровно тогда, когда содержит s, исключает t и замкнуто по исходящим остаточным дугам. Используется именно остаток максимального потока; для произвольного потока такое равенство не удостоверяет минимальность.
Компоненту нельзя разрезать пополам
Если замкнутое S содержит одну вершину остаточной SCC, оно обязано содержать все достижимые из неё, значит всю компоненту. Сожмём SCC в DAG. Теперь можно выбирать объединения компонент, содержащие компоненту s и не содержащие компоненту t, с условием: вместе с выбранной компонентой выбираются все её последователи. Это компактное описание семейства без повторного запуска потока для каждого разреза.
Компоненты, достижимые из s, обязательны. Компоненты, из которых достижим t, запрещены. Остальные могут быть свободны лишь с учётом зависимостей DAG. Поэтому нельзя просто независимо включать каждую неопределённую компоненту. Количество минимальных разрезов иногда экспоненциально, хотя представляющий DAG имеет линейное число вершин по размеру остаточной сети.
Замкнутые стороны образуют семейство с понятными операциями
Пересечение и объединение двух допустимых замкнутых сторон снова замкнуты, содержат s и исключают t. Следовательно они также дают минимальные разрезы. Это объясняет существование наименьшей стороны, достижимой из s, и наибольшей, исключающей всё, что достигает t. Но произвольное удаление вершины из допустимого S может разрушить замкнутость и увеличить ёмкость разреза. Полный перебор маленькой сети проверяет именно это различие.
| S | Выходящие исходные дуги | Ёмкость |
|---|---|---|
| {s} | s→a,s→b | 2 |
| {s,a} | s→b,a→t,a→b | 3 |
| {s,b} | s→a,b→t | 2 |
| {s,a,b} | a→t,b→t | 2 |
Три минимума вместо четырёх независимых выборов
Условие. Дуги сети: s→a=1,s→b=1,a→t=1,b→t=1,a→b=1. Поток 1 идёт по s–a–t и ещё 1 по s–b–t; на a→b поток 0. Найдите все стороны S минимального s–t разреза.
- Поток имеет значение 2 и насыщает весь выход s, поэтому максимален. Положительные остаточные дуги: a→s,b→s,t→a,t→b и a→b.
- Все SCC одноэлементны. Сторона S обязана содержать s и исключать t. Единственная дополнительная зависимость между необязательными a,b: включение a требует включения b.
- Допустимы ровно {s}, {s,b}, {s,a,b}. Их исходные выходящие ёмкости равны соответственно 2,2,2.
- Четвёртый кандидат {s,a} нарушает замкнутость из-за a→b. Его разрез пересекает s→b,a→t,a→b и имеет ёмкость 3, поэтому не оптимален.
Ответ. Все минимальные стороны: {s}, {s,b}, {s,a,b}; общая ёмкость 2.
Проверка. Независимый перебор всех четырёх сторон между s и t вычисляет ёмкости 2,3,2,2. Семейство замкнуто по объединению и пересечению, а его зависимость a⇒b видна в остаточном DAG.
Где легко ошибиться. Не включайте свободные SCC независимо друг от друга: остаточные дуги между ними задают обязательные зависимости. Также обязательно исключайте компоненту стока.
Проверьте понимание
Вопросы к этой главе
Зависит ли семейство минимумов от выбранного максимального потока?
Исходные оптимальные разрезы от него не зависят. Разные максимальные потоки могут давать разные остаточные графы, но условие отсутствия выходящего остаточного запаса характеризует одно и то же семейство исходных минимумов.
Почему нельзя пересечь SCC границей разреза?
Из любой её выбранной вершины достижима любая другая. На первом выходе пути из S была бы положительная остаточная дуга наружу, что нарушает необходимую замкнутость.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Sanders, Schulz: Engineering Multilevel Graph Partitioning Algorithms, §3
Прочитаны теорема Picard–Queyranne о замкнутых множествах остаточной сети и её сжатие по SCC. Для нашего фиксированного s–t разреза явно добавлено t∉S. Алгоритм балансировки статьи не используется. Иной KITURL h-cdggq-08.pdf вернул 404; использован этот читаемый PDF.
Обязательные потоки и сертификат несовместного баланса
У потока могут быть обязательные минимальные значения на дугах и заданный чистый приток в вершины. Начальная установка всех нижних границ обычно нарушает баланс. Вспомогательная сеть проверяет, можно ли исправить этот остаток, а недостаточный разрез даёт конечный сертификат невозможности.
Перед началом: Максимальный поток и разрез; Баланс как приток минус отток.
Нижний поток вычитается вместе с его дисбалансом
Для дуги e заданы 0≤l_e≤u_e. Требуется l_e≤f_e≤u_e и Σ_in f−Σ_out f=b_v в каждой вершине. Положительное b означает потребление чистого притока, отрицательное — чистую подачу. Необходимое условие Σb_v=0 следует из сокращения каждой дуги при суммировании балансов.
Положим f=l+x. Остаточная ёмкость для x равна u−l, а требуемый остаточный баланс r_v=b_v−L_v, где L_v — приток минус отток нижних значений. Просто уменьшить ёмкости без исправления правой части нельзя: нижние обязательства уже внесли реальные потоки в вершины.
Знак остаточного баланса определяет сторону вспомогательной дуги
Создадим сверхисточник SS и сверхсток TT. При r_v<0 добавим SS→v ёмкости −r_v; при r_v>0 добавим v→TT ёмкости r_v. Исходные остаточные дуги имеют ёмкости u−l. Требуемая величина D=Σ_(r>0)r равна сумме отрицательных обязательств по модулю.
Если максимальный поток SS→TT достигает D, все вспомогательные обязательства насыщены. Его значения на исходных дугах дают x, а прибавление l восстанавливает допустимый f. Обратно, любой допустимый f задаёт такой насыщенный вспомогательный поток. Для целых входов алгоритм максимального потока может дать целочисленное свидетельство без дробных округлений.
Неудача проверяется разрезом, а не сообщением алгоритма
Если полученная величина меньше D, минимальный SS–TT разрез той же ёмкости доказывает невозможность полного насыщения. Его ёмкость вычисляется суммой направленных дуг из стороны SS наружу. Такой разрез является проверяемым отрицательным свидетельством независимо от того, каким методом искали поток.
Лаборатория использует явное соглашение о чистом притоке и показывает нижний баланс, остаточные требования и восстановленные значения. При положительном результате следует заново проверить все исходные нижние и верхние границы и каждый исходный b. Вспомогательные дуги служат только доказательству и не являются дополнительными физическими каналами исходной задачи.
Обязательный приток требует закрыть боковую ветвь
Условие. Вершины 0,1,2,3; дуги 0→1:[2,4],1→2:[1,3],2→0:[0,3],1→3:[1,2],3→0:[0,2]. Требуемые балансы b=(−1,0,1,0). Найдите допустимые потоки и исследуйте запрет последней дуги ёмкостью нуль.
- Нижние значения равны (2,1,0,1,0). Их чистые притоки L=(−2,0,1,1), поэтому остаточное требование r=b−L=(1,0,0,−1).
- Нужно передать одну единицу от SS в вершину три, затем по остаточной дуге 3→0 и из нуля в TT. Её остаточная ёмкость два допускает такой перенос.
- Прибавление к нижнему потоку даёт f=(2,1,0,1,1). Чистые притоки равны (−1,0,1,0), все пять значений лежат в исходных допустимых интервалах.
- Если верхнюю границу 3→0 заменить нулём, остаточная вершина три не имеет исходящего канала. Сторона {SS,3} образует разрез ёмкости нуль при требуемом D=1.
- Прямое исходное объяснение отказа совпадает с разрезом: в вершину три обязательно входит хотя бы единица по 1→3, а её требуемый чистый приток нулевой и выход запрещён. Сбалансировать её невозможно.
Ответ. Для исходных границ допустим f=(2,1,0,1,1). При запрете 3→0 задача несовместна; вспомогательный разрез ёмкости 0<1 подтверждает отказ.
Проверка. Полный ограниченный перебор всех целых значений дуг независимо проверяет существование первого варианта и отсутствие второго. Подстановка найденного f проверяет каждый исходный баланс.
Где легко ошибиться. Не перепутайте знак r при подключении SS и TT. В этой записи отрицательный остаточный приток означает источник подачи, к которому идёт дуга от SS.
Циркуляция с обязательными потоками
Вершины 0,…,n−1, до 8 вершин и20 различимых дуг. Строка: начало конец нижняя верхняя границы; 0≤нижняя≤верхняя≤1000. Баланс b — требуемый приток минус отток. До 20000 по модулю, сумма 0; пустое поле означает нулевые балансы. Параллельные дуги разрешены.
Проверьте понимание
Вопросы к этой главе
Почему исходные нижние значения нельзя сразу назвать допустимым потоком?
Они удовлетворяют границам дуг, но могут нарушать заданные балансы вершин. В примере у вершины три нижний чистый приток один вместо требуемого нуля.
Достаточно ли нулевой суммы b для существования?
Нет. Это только глобальное необходимое условие. Локальные нижние границы и отсутствие нужного выхода могут создать недостаточный разрез даже при сумме балансов нуль.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- O. Cheong: Circulations with demands and lower bounds
Прочитаны соглашение fin−fout=d, подключение сверхисточника/стока и преобразование d′=d−L,c′=c−l. Четырёхвершинный пример, восстановленный поток и нулевой недостаточный разрез рассчитаны независимо.
Предпоток и высоты: максимальный поток без поиска целого пути
При поиске максимального потока можно временно накапливать входящий поток во внутренней вершине. Такой предпоток сохраняет ограничения ёмкости, но разрешает неотрицательный избыток. Алгоритм проталкивания и подъёма переносит избытки по одному ребру, используя высоты как локальный сертификат направления. Когда внутренние избытки исчезают, получается обычный поток, а высоты исключают оставшийся увеличивающий путь.
Перед началом: Остаточная сеть и обратное ребро; Поток и разрез между источником и стоком.
Нарушается равенство сохранения, но не ограничение ёмкости
Конечная ориентированная сеть с неотрицательными целыми ёмкостями, разными источником s и стоком t; без нижних границ.
Избыток e(v) равен входящему потоку минус исходящий. У предпотока e(v)≥0 для всех v, кроме источника; внутренние вершины могут хранить ещё не переданную массу. Активна внутренняя вершина с положительным избытком. Источник и сток не выбираются для обычной обработки активных вершин.
Для инициализации насыщаем исходящие рёбра источника. Ставим h(s)=n, h(t)=0 и нулевые высоты остальных вершин. После насыщения из источника нет свободных прямых рёбер, поэтому выполняется условие допустимых высот h(u)≤h(v)+1 на каждом положительном остаточном ребре. Избыток возле источника не означает, что весь первоначально отправленный объём дойдёт до стока.
Push тратит избыток, relabel создаёт допустимое направление
По остаточному ребру u→v разрешён push, если h(u)=h(v)+1. Передаём δ=min(e(u),r(u,v)), обновляя обе остаточные ёмкости и оба избытка. Обратный остаточный шаг может отменить прежнюю передачу. Высоты после push остаются допустимыми, включая возникшее обратное ребро.
Если у активной u нет допустимого ребра, поднимаем её до 1+min h(v) по положительным остаточным выходам. Высота строго растёт. Такой выход существует: положительный избыток был доставлен из источника, и в остаточной сети сохраняется возможность возврата. Высота не является точным расстоянием до стока и может стать больше n, позволяя вернуть лишний объём источнику.
Окончание требует исчезновения всех внутренних избытков
Пока есть активная вершина, выполняем одну из двух операций. Для стандартного общего алгоритма действует конечная полиномиальная оценка числа операций; выбор порядка влияет на промежуточную трассу. На маленькой сети можно намеренно выбрать неудобный порядок и увидеть многократные возвраты избытка, не нарушая корректности.
При отсутствии внутренних избытков предпоток становится допустимым потоком. Увеличивающего пути из s в t нет: вдоль простого остаточного пути из не более n−1 рёбер высота могла бы уменьшиться суммарно не более n−1, а h(s)−h(t)=n. Достижимые из s остаточные вершины задают разрез; его ёмкость равна полученному значению потока.
Часть начального избытка возвращается источнику
Условие. В сети вершины s,a,b,c,t, рёбра s→a:7, s→b:4, a→c:3, b→c:4, c→t:5, a→t:1. Выполните предпотоковый поиск, затем подтвердите максимальное значение разрезом.
- Насыщение s→a и s→b создаёт e(a)=7,e(b)=4 и высоту источника 5. После подъёма a до 1 отправляем 3 в c и 1 в t. Оставшиеся 3 можно вернуть по обратному a→s после подъёма a до 6.
- Поднимаем b до 1 и отправляем его 4 единицы в c. Теперь e(c)=7. Подъём c до 1 разрешает отправить 5 в t; остаётся избыток 2.
- Поскольку c→t насыщено, оставшийся объём должен вернуться. Локальные подъёмы и обратные передачи через b в итоге возвращают 2 источнику. Возможная конечная высота всех a,b,c равна 6; их избытки равны нулю.
- Получаем потоки s→a=4,s→b=2,a→c=3,b→c=2,c→t=5,a→t=1. Разрез {s,a,b,c}|{t} имеет ёмкость 5+1=6 и совпадает с входом стока.
Ответ. Максимальное значение потока равно 6. Из первоначально отправленных 11 единиц пять возвращаются источнику.
Проверка. Проверка каждого ребра подтверждает ёмкости, а балансы a,b,c равны нулю. Независимый перебор восьми разрезов с s на одной стороне и t на другой даёт минимальную ёмкость 6; значит большего допустимого потока нет.
Где легко ошибиться. Не выдавайте сумму насыщенных исходящих рёбер источника за готовое значение максимального потока. Внутренний избыток может потребовать возврата, прежде чем выполнится сохранение.
Проверьте понимание
Вопросы к этой главе
Зачем высоте внутренней вершины превышать высоту источника?
Тогда обратное остаточное ребро к источнику может стать допустимым. Это необходимо для возврата массы, которой не хватает пропускной способности на пути к стоку.
Отсутствие допустимого ребра означает завершение?
Нет. Если избыток положителен, вершину поднимают. Завершение общего алгоритма означает отсутствие активных внутренних вершин во всей сети, а не только отсутствие текущего push.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Dalhousie — Generic Preflow-Push Algorithm, §5.2.1
Активные вершины, допустимые высоты и локальные операции Push/Relabel. Сеть, неудобная последовательность возвратов и независимый перебор разрезов подготовлены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Поток и разрез: как получить проверяемую верхнюю границу
Разрез сети как доказательство оптимальности: направленные ёмкости через границу, верхняя оценка потока и совпадение с допустимым решением.
Открыть темуПаросочетание: как чередующийся путь увеличивает число пар
Увеличивающий путь в двудольном паросочетании: перестановка занятых назначений вместо жадного отказа свободной вершине.
Открыть тему