1. Задача о максимальном потоке в транспортной сети.

Определение 1. Транспортной сетью называется конечный граф , состоящий из () вершин , ,…, и из дуг (,), соединяющих некоторые пары этих вершин, причем каждой дуге поставлено в соответствие число ³ 0, называемое пропускной способностью дуги (,).

Вершина называется входом сети, а – выходом транспортной сети.

Будем считать, что граф симметрический, т.е. если в него входит дуга (,), то входит и дуга (,).

– определяет количество вещества (машин, и т.п.), которое может протекать по дуге в единицу времени.

Например:

= 0, если и не соединены дугой.

По путям m(, , ,…, , ), составленным из дуг (,), (,), …, (,) сети направляется транспорт из в .

Потоком по дуге (,) (, ) называется количество вещества, проходящее через эту дугу в единицу времени.

Потоком по сети или просто потоком будем называть совокупность {} потоков по всем дугам сети.

Потоки должны удовлетворять следующим ограничениям:

1. (, ),

2. (), что означает: количество вещества, притекающее в вершину сети равно количеству вещества, вытекающего из него (кроме и ).

Поток, удовлетворяющий ограничениям 1 и 2 будем называть допустимым.

Из (2) видно, что общее количество вещества, вытекающего из , , совпадает с общим количеством вещества, притекающего в , , т.е.

3. .  Линейная форма называется потоком по сети.

Задача о максимальном потоке в транспортной сети заключается в отыскании такого решения () системы (1 – 2) (т.е. такого допустимого потока), который максимизирует .

Это решение {} называется максимальным потоком сети.

Рассмотрим такой простейший пример:

Найти максимальный поток из в . Толстые дуги насы­ще­ны, т.е.   = , пол­ный поток  , а максимальный поток равен 6. Разобьем множество всех вершин на два подмножества и так, что и . Сечением (,) сети назо­вем совокупность всех дуг (,), концы которых принадлежат разным подмножествам.

Каждому сечению поставим в соответствие неотрицательное число – пропускную способность сечения, равную сумме всех дуг сечения, начинающихся в U и кончающихся в V, т.е.

Любой путь из в обязательно содержит хоть одну дугу сечения (,), которая начинается в U и заканчивается в V. Ясно, что пропускная способность пути не превышает пропускной способности каждой его дуги. Поэтому величина любого потока из в , которая является суммарной величиной пропускной способности всех путей из в , не может превысить пропускной способности любого сечения (,), т.е. всегда .

Теорема Форда-Фалкерсона утверждает: Для заданной транспортной сети наибольшая величина потока равна наименьшей пропускной способности сечения, т.е.

по всем возможным сечениям. Т.е. если удастся построить такой поток {}, что , то этот поток будет максимальным, а сечение  – обладать минимальной пропускной способностью.

Естественно, что каждую транспортную сеть стремятся использовать оптимально, т.е. организовать перевозки по транспортным путям таким образом, чтобы поток перевозимых грузов был максимальным.

Алгоритм построения максимального потока в транспортной сети

Предварительный шаг:

Условия 1. записываются в виде следующей таблицы:

Если , , то в клетке ставим 0,

Если же , то клетки и не заполняем.

Начальная таблица:  (4)

		…		…		…
…
…
…

Общий шаг: (из трех действий)

1. Отыскание по таблице нового пути из в . Сначала отмечаем –й столбец *. Затем отыскиваем в строке все положительные и содержащие их столбцы отмечаем сверху числом 0 (номером вершины )

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

Просматриваем затем строки затем строки, имеющие те же номера, что и отмеченные столбцы.

В каждой такой строке (например ) отыскиваем все неотрицательные , расположенные в неотмеченных столбцах, и отмечаем эти столбцы номером рассматриваемой строки (например ).

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

Продолжаем аналогичный просмотр строк с номерами отмеченных столбцов. Процесс оканчивается, если:

а) Отмечен –й столбец, т.е. удалось выделить дугу (, ) с > 0, которая служит последней дугой некоторого пути из в .

б) Просмотрены все строки и нельзя отметить новых столбцов (т.е. в неотмеченных столбцах нет > 0), это означает отсутствие пути из в , все дуги которого обладают положительными пропускными способностями (Алгоритм закончен). В случае а) искомый новый путь из в отыскиваем следующим образом. Начиная от . Пусть столбец был отмечен номером k, т.е. предшествующая вершина в пути, соединяющем с , – . (При просмотре строки был отмечен столбец ). Число > 0 помечаем знаком “–“ (). Число , расположенное симметрично к диагонали, помечаем знаком “+” (). Раз рассматривалась –я строка, значит перед этим был отмечен столбец номером (например). По столбцу двигаемся вверх до –ой строки. отмечаем “–“ (), а знаком “+”. Этот процесс продолжаем до тех пор, пока не придем к – ой строке и не отметим элемент этой строки и симметричный элемент.

2. Определяем пропускную способность найденного пути

3. Вычисляем новые пропускные способности дуг найденного пути и симметричных с ними

,   ,

,  .

В результате получаем новую таблицу, с которой повторяем эти 3 шага.

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

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

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

Обозначим через множество вершин сети , которые достижимы из по некоторому пути в последней таблице, а множество остальных вершин через .

Тогда увидим, что все дуги сечения (,), направленные из в , загружены полностью до пропускных способностей (т.е. для (,), что , , ), а дуги (,) противоположного направления, идущие из в в построенном потоке не используются (т.е. =0, ,), так что величина потока равна:

т.е. построенный поток максимален, а (,) – сечение с минимальной пропускной способностью.

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

.