Пример решения задачи о максимальном потоке

Рассмотрим пример решения задачи о максимальном потоке.

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

Рис. 1.

1. Определим начальный поток . Разумеется, .

Рис. 2.

2. Алгоритм Форда-Фалкерсона построения максимального потока в сети.

Определение 13. Цепь от входа до выхода называется повышающей поток , если выполнены условия 1. и 2. .

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

В соответствии с определением 13 сформулируем простое правило: пометки можно наносить либо по ненасыщенным дугам по направлению дуги или по дугам, на которых , но в обратном направлении (по “обратным” дугам). Повторно пометки не наносятся.

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

()

*

Рис. 3. ()

Теперь просматриваем помеченные вершины и в каком-либо фиксированном порядке, например, сверху вниз. Вначале просмотрим вершину . Из нее пометим вершины и (вершина уже помечена).

() ()

*

Рис. 4. () ()

Из вершины ничего не помечаем, поскольку вершина уже помечена.

Просмотрим вершины и . Из пометим вершину - выход сети.

() ()

* ()

Рис. 5. () ()

На этом алгоритм пометок заканчивает свою работу. Выписываем построен­ную первую повышающую цепь , начиная с вершины , помеченной, как это видно на рисунке 5, из вершины , помеченной из , в свою очередь помеченной из . Таким образом, имеем: .

Пусть , где (1).

В силу условий 1. и 2. определения 13 и , если , и , если . Найдем новый поток , полагая

(2).

Так как в нашем случае дуги , и включены в цепь , то и , , .

Ясно, что для так определенного нового потока условие неразрывности (как и все остальные условия определения 3) будет выполнено. Новый поток изобразим на следующем рисунке. Ясно, что .

Рис. 6.

Как обычно, на рисунке индексы для простоты опускаем. Здесь для удобства мы отметили пунктиром насыщенную дугу , поскольку на следующем шаге мы не можем включать ее в повышающую цепь, и, следовательно, использовать в алгоритме пометок.

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

Заметим, что мы теперь можем включать во вторую повышающую цепь дуги обратные дугам , и , то есть дуги , и .

Пометив звездочкой вершину , пометим из нее вершины и . Затем из пометим вершины и (вершина уже помечена).

() ()

*

Рис. 7. () ()

Из ничего не помечаем, так как вершина уже помечена. Просматриваем вершины и . Теперь из мы ничего пометить не сможем, поскольку дуга - насыщенная. Пометив из вершины выход , заканчиваем алгоритм пометок и получаем повышающую цепь . Находим . Следовательно, новый поток имеет вид

Рис. 7.

и . Как обычно, на рисунке индексы опускаем.

Построим теперь третью повышающую цепь для потока . Из вершины , пометим вершину . Затем из пометим вершину . Так как на дуге имеется положительный поток , то из вершины мы можем пометить вершину , используя обратную дугу . Затем из пометим вершину , а из нее пометим . Результат пометок представлен на следующем рисунке.

() ()

* ()

Рис. 8. () ()

Как обычно, начиная с конца и выписывая в обратном порядке по очереди вершины ,,,,, из которых были нанесены пометки, получаем третью повышающую цепь . Для нее определяем величину

.

Здесь в силу правила (1), поскольку и .

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

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

Особенно наглядный смысл имеют рассмотренные манипуляции для реальных потоков товаров. Так на первом шаге решения мы отправили партии товара из пункта в пункт , а на третьем шаге «вернули» 2 из них обратно в , заменив двумя партиями товара, доставленными из пункта через в . Затем отправили обе возвращенные в партии из пункта уже в пункт и далее в пункт назначения . В результате величина суммарного потока была увеличена на 2 партии.

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

Рис. 9.

Мощность построенного потока .

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

Лемма. Если с помощью алгоритма пометок невозможно поостроить повышающую цепь, то поток - максимальный и его мощность равна пропускной способности некоторого минимального разреза.

Доказательство. Построим такой разрез (он окажется минимальным), что . Отметим на новом рисунке все помеченные вершины звездочкой и отделим (входное)

* *

*

Рис. 9. *

множество помеченных вершин от (выходного) множества непомеченных вершин «линией» разреза (разумеется такая линия существует, хотя и может быть изображена по разному). Покажем, что все разрезанные дуги - насыщенные. Действительно, если дуга ненасыщенная, то выполняется условие , причем вершина - помеченная. Но тогда с помощью алгоритма пометок из мы должны были пометить вершину , которая по предположению непомечена. Полученное противоречие доказывает, что .

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

По следствию теоремы 2 поток является максимальным, а разрез - минимальным. Что и требовалось доказать.

Замечание 3. В нашем случае в равенстве легко убедиться и непосредственно, поскольку и .

Теорема (Форд-Фалкерсон). Для любой сети с целыми пропускными способностями с помощью алгоритма Форда-Фалкерсона за конечное число шагов можно построить поток максимальной мощности, равной пропускной способности минимального разреза.

Замечание 4. Фактически эта теорема нами доказана лишь для частного рассматриваемого выше примера. Однако, все рассуждения нетрудно провести по аналогии и в общем случае, поскольку используемый алгоритм пометок очевидным образом применим к любой сети. На каждом шаге он либо приводит к пометке выхода и, следовательно, к построению повышающей цепи и соответствующему повышению мощности потока на , либо оказывается, что выход невозможно пометить, и в этом случае, в силу доказанного выше утверждения поток оказывается максимальным и его мощность равна пропускной способности построенного (минимального) разреза. Если все пропускные способности дуг сети целые числа, то и величина также целая, и, следовательно, . Так как мощность потока ограничена (конечной) пропускной способностью произвольного разреза, то алгоритм закончится за конечное число шагов. Ч.т.д.

Замечание 5. Теорема Форда-Фалкерсона остается в силе и для произвольных соизмеримых (рациональных) пропускных способностей. Действительно,

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

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

Замечание 7. Для иррациональных пропускных способностей алгоритм Форда-Фалкерсона также применим, но не обязательно приводит к результату за конечное число шагов. Поскольку на -ом шаге , то последовательность возрастает. В силу ограниченности она сходится, причем, нетрудно показать, что в пределе получаем максимальный поток:

при .

Дата добавления: 2014-01-20