Алгоритм нахождения максимального потока

Дана сеть (G,a), a – источник, b – сток сети, a:E®N.

Шаг 1. Если не существует пути из источника в сток, то положить j=0 и перейти к шагу 4, иначе выбрать непустое множество T непересекающихся по дугам путей из a в b. Если e₁,e₂,…,e_k – путь из T, т.е. последовательность дуг, то положить j(e₁)= j(e₂)=…= j(e_k)=min{a(e₁),…,a(e_k)}. Для дуг e, через которые не проходят пути из T, положитьj(e)=0. В результате получаем ненулевой поток j через сеть (G,a).

Шаг 2. Исходя из сети (G,a) и потока j построить сеть (G′,a′) следующим образом. Граф G^’ будет иметь те же вершины, что и граф G. Если e – дуга графа G и a(e) - j(e)¹0, то e – дуга графа G′ и a′(e)=a(e) - j(e). Если e – дуга графа G и j(e)¹0, то вводим дугу обратной ориентации, нежели e, и полагаем a′() = j(e). В случае, когда возникают кратные дуги e₁ и e₂, то вводим вместо них одну дугу e и полагаем a′(e)=a′(e₁) + a′(e₂).

Шаг 3. Если в сети (G′,a′) не существует пути из a в b, то перейти к шагу 4, иначе в сети (G’,a’) построить ненулевой поток j’ так, как это предписано шагом 1. Для сети (G,a) положить j=j+j’ и перейти к шагу 2.

Шаг 4. Выдать j. Конец работы алгоритма.

На примере сети, изображенной на рис 6.22, проиллюстрируем работу алгоритма. В качестве множества T на первом шаге алгоритма выбрано множество из двух путей: a,v₁,v₄,b и a,v₂,v₅,b.

Рис. 6.22

Рис. 6.23

На рис. 6.23 представлена сеть (G′,a′) полученная после выполнения шага 2 из сети на рис. 6.22 с указанным (в скобках) потоком j′. В качестве множества T для построения потока j′ взято множество, состоящее из одного пути: a,v₃,v₅,v₂,v₆,b. Поток j+j′ для сети (G,a) изображен на рис. 6.24. Этим завершен один проход алгоритма. Обратим внимание на то, что для e=(v₂,v₅) (j+j′)(e)=j(e)–j′()=1.

Рис. 6.24

Рис. 6.25

Сеть построенная на шаге 2 второго прохода алгоритма, уже не имеет (a,b) – путей (см.рис. 6.25). Следовательно, на рис. 6.24 изображен максимальный поток.

Задачи

1. Задача о максимальном паросочетании. На вход дается N — количество мальчиков, M — количество девочек и список, какой мальчик с какой из девочек хочет танцевать (таких может быть несколько). Надо определить максимальное количество одновременно танцующих пар.

Решение

Для решения этой задачи можно использовать алгоритм Куна, но раз уж мы взялись сводить все к потоку — давайте это сделаем. Для этого не хватает истока и стока. Давайте их добавим! «Слева» добавим фиктивную вершину и проведем ребра ко всем мальчикам весом в 1. От мальчиков к девочкам уже есть ребра проставим им тоже цену 1. И от девочек ребра к стоку тоже ценой 1. Ответом к задаче является величина максимального потока между истоком и стоком.

2. Испорченный паркет. У паркета NxM, некоторые клетки могут быть испорчены. Их необходимо закрыть новыми плитками. Плитки бывают размером 2х1 (можно поворачивать, но нельзя разрезать) ценой А, и 1х1 ценой B. Спрашивается, какую минимальную сумму нужно потратить, что бы заложить испорченные плитки паркета. Естественно, новые плитки не должны перекрывать никакие другие плитки.