Загрузка...

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


Для любой сети G=(J, U) с одним источником S и одним стоком t величина максимального потока из S в t равна пропускной способности минимального разреза, отделяющего S от t.

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

Дуга (i, j) насыщена потоком, если Xij=Cij.

Доказательство:

Пусть V* величина максим. потока в даной сети. Необходимо доказать, что можно построить такой разрез clip_image002, для которого Cclip_image002[1]=V. Определим множество вершин R* по следующему правилу:

Вершины, принадлежащие множеству R* согласно правилу (1) определяется одна за другой. Вершина j включает в в множество R* , если дуга (i, j) не насыщена потоком, или если поток по обратной дуге (j, i) явл. положительным. Покажем что применяя правило (1) вершина t не будет принадлежать R* , т. е. clip_image005 .

Пусть clip_image005[1] , тогда существует некоторая цепь (i1, i2 … im), для которой i1=S, im=t и прямые дуги этой цепи (iк, iк+1) не насыщены потоком т. е. Xik ik+1<Cik ik+1 , а поток на обратных дугах положителен т. е. Xik+1,ik>0. Найдем минимальное значение потока на всех прямых дугах.

min(Xik+1ik)=E1

и минимальное значение потока на обратных дугах:

min(Xik+1ik)=E2

и обозначим min (E1, E2)=E

Тогда поток в сети (на рассмотренной цепи) можно увеличить на Е и поток в сети будет: V*+E . Получим противоречие тому что V* — максимальный поток. А следовательно clip_image005[2] , т. е. построен разрез clip_image009.

Загрузка...