Часть 5, Алгоритмы на графах. Свойство 22.12. Алгоритм выталкивания превосходящего потока вычисляет максимальный поток.

Свойство 22.12. Алгоритм выталкивания превосходящего потока вычисляет максимальный поток.

Доказательство: Прежде всего, мы должны доказать, что алгоритм останавливается. Должен наступить момент, когда не останется ни одной активной точки. Как только мы вытесним все избыточные потоки из некоторой вершины, эта вершина не может снова стать активной, пока какая-то часть этого потока не будет вытолкнута назад, и этот вытолкнутый поток может иметь место только тогда, когда высота этой верши­ны возрастет. Если имеется последовательность активных вершин неограниченной длины, одна из вершин должна появиться в этой последовательности неограниченное число раз, а это может случиться только в том случае, когда ее высота возрастает нео­граниченно, что противоречит свойству 22.9.

Если активных вершин нет, то поток осуществим. Так как согласно свойству 22.11, в остаточной сети путь от истока в сток отсутствует, то рассуждения, использованные при доказательстве свойства 22.5, приводят нас к заключению, что поток в сети пред­ставляет собой максимальный поток. ■

Можно уточнить доказательство этого алгоритма в части его останова и показать, что он остановится в худшем случае по истечении промежутка времени О(V²E). Все детали этого доказательства мы оставляем читателям на самостоятельную проработку (см. упраж­нения 22.66 и 22.67), а здесь отдадим предпочтение более простому доказательству 22.13, которое относится к более простой версии алгоритма. В частности, в основу рассматри­ваемых нами реализаций положим более конкретные инструкции, касающиеся итераций:

Выберите активную вершину. Увеличьте поток в подходящем ребре, исходящем из этой вершины (если это возможно), продолжая этот процесс до тех пор, пока или верши­на не перестанет быть активной либо не останется ни одного подходящего ребра. В последнем случае увеличьте высоту вершины.

Другими словами, как только будет выбрана вершина, мы выталкиваем из нее как можно больший поток. Если мы выйдем в вершину, в которой все еще имеет место из­быток потока, но в то же время не осталось ни одного подходящего ребра, мы увеличи­ваем высоту этой вершины. Мы будем называть этот метод вершинным (vertex-based) алго­ритмом выталкивания превосходящего потока. Это специальный случай реберного обобщенного алгоритма, в условиях которого мы продолжаем выбирать одну и ту же вер­шину до тех пор, пока она не перестанет быть активной, либо пока не перепробуем все подходящие ребра, исходящие из нее. Доказательство свойства 22.12 сохраняет коррект­ность применительно к любой реализации реберного обобщенного алгоритма, отсюда не­медленно следует, что вершинный алгоритм вычисляет максимальный поток.

Программа 22.5 представляет собой реализацию обобщенного вершинного алгоритма, который использует обобщенную очередь активных вершин. Это непосредственная реа­лизация только что описанного метода, она представляет собой семейство алгоритмов, которые отличаются только исходными функциями высоты (см. например, упражнение 22.52) и реализацией АДТ обобщенной очереди. Такая реализация построена в предпо­ложении, что обобщенная очередь блокирует хранение дубликатов вершин; в противном случае мы можем добавить в программу 22.5 код, запрещающий прием дубликатов в оче­редь (см. упражнения 22.61 и 22.62).