- •Предисловие
- •1. Начальные понятия Определение графа
- •Способы задания графов
- •Окрестности и степени
- •Некоторые специальные графы
- •Изоморфизм
- •Подграфы
- •Операции над графами
- •Пути, циклы, связность
- •Расстояния и метрические характеристики
- •Графы пересечений
- •2. Перечисление графов Помеченные графы
- •Непомеченные графы
- •3. Важнейшие классы графов Деревья
- •Двудольные графы
- •Планарные графы
- •3.22. Какие из следующих графов планарны: 1) ; 2) ; 3) ; 4) ?
- •4. Методы обхода графа
- •5. Циклы Эйлеровы циклы
- •Гамильтоновы циклы
- •6. Независимые множества, клики, вершинные покрытия
- •7. Паросочетания Паросочетания и реберные покрытия
- •Паросочетания в двудольных графах
- •7.6*. Докажите утверждение о бесполезных вершинах.
- •8. Раскраски Раскраска вершин
- •Раскраска ребер
- •9. Оптимальные каркасы и пути
- •Алгоритм Прима
- •Алгоритм Краскала
- •10. Потоки
- •Вариант 4
- •Вариант 5
- •9.6. Найдите наибольшее паросочетание с помощью потокового алгоритма.
10. Потоки
В этом разделе будем рассматривать ориентированные графы без петель и кратных ребер. Для вершины x множество всех входящих в нее ребер обозначается через , а множество выходящих – через . Сетью называется орграф, в котором
каждому ребру e приписано положительное число , называемое пропускной способностью ребра;
выделены две вершины s и t, называемые соответственно источником и стоком, при этом .
Вершины сети, отличные от источника и стока, будем называть внутренними.
Пусть задана сеть N с множеством вершин V и множеством ребер Е. Пусть f –функция с вещественными значениями, определенная на множестве Е. Для вершины х обозначим , . Функция f называется потоком в сети N, если она удовлетворяет условиям:
(1) для каждого ребра e;
(2) для каждой внутренней вершины x.
На рисунке 11 показан пример сети и потока в ней. В дроби, приписанной каждому ребру, числитель представляет пропускную способность ребра, а знаменатель – величину потока на этом ребре.
Рис. 11.
Условие (2) называется условием сохранения потока. Так как каждое ребро является входящим для одной вершины и выходящим для другой, то
.
Из этого равенства и условия сохранения потока следует, что
.
Эта величина обозначается через и называется величиной потока. В примере на рисунке . Задача о максимальном потоке состоит в том, чтобы для данной сети найти поток наибольшей величины.
Поток на рисунке 11 не является максимальным – можно, например, добавить по единице на ребрах пути . Получится поток величины 5, показанный на рисунке 12 слева. Но и он не максимален. Можно увеличить поток на 1 на ребрах , , и уменьшить на 1 на ребре . Условие сохранения останется выполненным, а величина потока станет равной 6 (рисунок 12, справа).
Рис. 12.
Приведенный пример иллюстрирует общий метод, на котором основаны многие алгоритмы решения задачи о максимальном потоке – метод увеличивающих путей. Он является обобщением метода увеличивающих путей для задачи о паросочетании.
Допустим, имеется сеть N и в ней поток f. Пусть – неориентированный путь в сети. Ребро назовем прямым ребром этого пути, если , и обратным, если . Путь назовем подходящим относительно потока f, если для каждого прямого ребра выполняется неравенство , а для каждого обратного – неравенство . Таким образом, на каждом прямом ребре подходящего пути поток можно увеличить, а на каждом обратном – уменьшить. Увеличивающий путь – это подходящий путь из источника в сток.
Если имеется увеличивающий путь для потока f, то поток можно увеличить на величину , равную минимуму из величин «недогрузок» (разностей ) прямых ребер этого пути и величин потока на обратных ребрах. Нужно прибавить к потоку на каждом прямом ребре пути и вычесть из потока на каждом обратном ребре. Условие сохранения останется выполненным, а величина потока увеличится на .
Теорема об увеличивающем пути. Поток максимален тогда и только тогда, когда относительно него нет увеличивающего пути.
Пусть , , причем , . Множество всех ребер, у которых начальная вершина принадлежит X, а концевая – , называется разрезом сети. Пропускная способность разреза есть сумма пропускных способностей его ребер.
Теорема о максимальном потоке и минимальном разрезе. Максимальная величина потока равна минимальной пропускной способности разреза данной сети.
Многие известные алгоритмы построения максимального потока основаны на теореме об увеличивающем пути и различаются, в частности, стратегией поиска увеличивающих путей. Первый алгоритм, для которого была получена верхняя оценка трудоемкости, предложили Эдмондс и Карп в 1972 г. В этом алгоритме всегда ищется кратчайший (по числу ребер) увеличивающий путь. Удобно этот поиск вести не на исходной сети N, а на остаточной сети R, которая при заданном на сети N потоке f определяется следующим образом. Множество вершин, источник и сток у остаточной сети те же, что у исходной. Пусть e – ребро исходной сети. Тогда
если , то ребро e включается в сеть R и ему в этой сети присваивается пропускная способность ;
если , то к сети R добавляется ребро противоположного направления с пропускной способностью .
Легко видеть, что увеличивающие пути в исходной сети находятся во взаимно однозначном соответствии с ориентированными путями из источника в сток в остаточной сети. В алгоритме Эдмондса-Карпа нужно в остаточной сети искать кратчайший ориентированный путь из s в t. Это можно сделать за линейное время с помощью поиска в ширину. Если увеличивающий путь обнаружен, поток увеличивается. Для нового потока строится остаточная сеть и т.д., пока не будет построен поток, относительно которого нет увеличивающего пути (в остаточной сети нет ориентированного пути из источника в сток. Общая оценка трудоемкости алгоритма Эдмондса-Карпа . В настоящее время известны и более быстрые алгоритмы для задачи о максимальном потоке.
Задачи
10.1. Найдите максимальные потоки в изображенных на рисунке сетях.