7. Транспортная сеть. Основные понятия и определения. Поток в транспортной сети. Теорема Форда – Фалкерсона. Алгоритм Форда – Фалкерсона. Разрез транспортной сети и его свойства. Поиск максимального паросочетания

Транспортная сеть. Основные понятия и определения.

Транспортная сеть — ориентированный граф G = (V, E) , в котором каждое ребро (u,v) \in E имеет неотрицательную пропускную способность c(u,v)>=0 и поток f(u,v).

Выделим теперь специальные типы вершин в сети.

Вершина y, из которой дуги только исходят, т.е. если , называется источником или входом сети S.

Вершина z, в которую дуги только входят, т.е. если , называется стоком или выходом сети S.

Потоком в транспортной сети Т называется неотрицательная вещественная функция, определенная на множестве дуг, удовлетворяющая условиям:

• ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги;
• сохранения: суммарный поток , заходящий в любую вершину сети ( кроме истока и стока ) равен суммарному потоку , выходящему из этой вершины.

Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности этой дуги.

Поток по пути называется полным, если хотя бы одна дуга пути насыщена.

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

Разрезом сети называется множество, которому принадлежит исток, и не принадлежит сток. Т.е. разрез - это минимальное (в смысле отношения включения) множество дуг, удаление которых “ разрывает” все пути, соединяющие исток и сток.

Пропускной способностью разреза называется число, равное сумме пропускных способностей дуг этого разреза. Разрез называется минимальным, если имеет наименьшую пропускную способность.

Теорема Форда – Фалкерсона.

В любой транспортной сети величина любого максимального потока равна пропускной способности любого минимального разреза.

Алгоритм Форда – Фалкерсона.

Алгоритм начинает свою работу с нулевого потока и на каждой своей итерации увеличивает поток в сети. На каждом шаге находится увеличивающая величину потока цепь. Поток увеличивается вдоль дуг этой цепи, пока она не станет насыщенной.

1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
   1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью Cmin.
   2. Для каждого ребра на найденном пути увеличиваем поток на Cmin, а в противоположном ему — уменьшаем на Cmin.
   3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
4. Возвращаемся на шаг 2.

Или так

Для определения потока в сети используют алгоритм Форда-Фалкерсона:

а) ищем любую цепь из истока графа в сток;

б) каждой дуге приписываем возможный больший поток из истока в сток (записываем его через дробь с весом дуги; при этом поток не может превысить вес дуги, но может быть ему равен);

в) если поток становится равен весу дуги, то эта дуга является насыщенной, то есть через нее нельзя пройти при рассмотрении цепей в графе;

г) так перебираем все возможные цепи, пока станет невозможно попасть из истока в сток;

д) поток в сети будет равен сумме потоков всех дуг, инцидентных стоку графа (следует заметить, что сумма потоков всех дуг, инцидентных стоку графа равна сумме потоков всех дуг, инцидентных истоку графа).