Основы дискретной математики

				§ 3.10. Задача о максимальном потоке в сети
		Сеть. Поток в сети. Величина потока. Максимальный поток. Дополняющая
		цепь. Разрез в сети. Минимальный разрез. Алгоритм Форда - Фалкерсона.
							Базовые понятия и утверждения
В этом параграфе будут рассматриваться сети G = (V ,U,ρ) , имеющие единственную
вершину s				с нулевой полустепенью захода и единственную вершину t						с нулевой
полустепенью исхода. Вершину s будем называть источником, а вершину t - стоком,
вес ρ(u) дуги u - пропускной способностью дуги u .
Для удобства изложения введем следующие обозначения. Через v + обозначим
множество дуг, для которых вершина v								является началом, а через v − обозначим
множество дуг, для которых вершина v								является концом.
Определение. Потоком в сети G = (V ,U ,ρ) называется функция f :U → [0,∞) ,
удовлетворяющая условиям:
1) u U f (u) ≤ ρ(u) ;
2)	f (v −) = f (v +)					для всех вершин v , v ¹ s , v ¹ t , где f (v −) = å f (u)				и
									u v−
f (v +) = å f (u) .
		u v+
Значение			f (v −)			можно интерпретировать как поток, втекающий в вершину v , а
значение			f (v +)		- как поток, вытекающий из вершины v . Тогда второе условие можно
переформулировать так: поток, втекающий в любую вершину, за исключением
источника и стока, должен быть равен потоку, вытекающему из этой вершины.
Условие 1) называется условием ограничения по пропускной способности, а условие 2)
- условием сохранения потока в вершинах.
	a		7,3	d		4,2	Пример 1. На рис. 3.83 дан пример сети и потока f в ней.
6,6
		3,3		8,1			t
	7,1
s		b	5,5	q	12,7		Около каждой дуги u указаны через запятую ее пропускная
	2,1
							способность ρ(u) и текущий по ней поток f (u) .
5,2			6,1
	c
							Определение. Положим		f = f (s +) . Число	f	называется
		Рис. 3.83.					величиной потока.

PDF created with pdfFactory Pro trial version www.pdffactory.com

Определение. Поток f * называется максимальным, если для любого потока f

справедливо неравенство f ≤ f * .

Задача о максимальном потоке формулируется следующим образом: в заданной сети

G найти поток максимальной величины.

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

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

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

При решении задачи об отыскании максимального потока в сети приходится рассматривать неориентированные простые цепи, т.е. такие последовательности попарно различных вершин и дуг v0u1v1...vk −1uk vk , в которой любые два соседних элемента инцидентны. Поскольку цепи других видов нас при этом интересовать не будут, то далее в этом параграфе неориентированные простые цепи будем называть просто цепями.

Если в цепи v0u1v1...vk −1uk vk дуга ui выходит из вершины vi−1 и заходит в вершину vi , то

она называется прямой дугой цепи. Если же дуга ui выходит из вершины vi	и заходит в
вершину vi−1 , то она называется обратной дугой цепи.
Пусть f - поток в сети G и P - цепь из v в w . Для каждой дуги u цепи	P будем
вычислять остаточную пропускную способность h(u) при данном потоке f	по

следующему правилу: если дуга u прямая, то h(u) = ρ(u) − f (u) , а если обратная, то h(u) = f (u) . В свою очередь остаточную пропускную способность h(P) цепи P при

данном потоке f будем определять по формуле h (P) = min{h (u)} .

u P

Определение. Цепь P из v в w называется дополняющей для f , если h (P) > 0 .

Пример 2. В сети, изображенной на рис. 3.83, цепь, включающая последовательно вершины s,b, c, q,t , является дополняющей для потока, рассмотренного в примере 1.

PDF created with pdfFactory Pro trial version www.pdffactory.com

Одним из алгоритмов, позволяющих построить максимальный поток, является алгоритм Форда - Фалкерсона.

Алгоритм Форда - Фалкерсона. 0-й шаг. Пускаем по сети нулевой поток f0 , т.е.

полагаем f0 (u) = 0 для всех дуг u U .

k -й шаг. Пусть к началу шага в сети течет поток fk −1 . Для этого потока fk −1 ищем дополняющую цепь из s в t .

Если такой цепи нет, то fk −1 - искомый максимальный поток.

В противном случае, если для потока fk −1 дополняющая цепь из s в t имеется, даем ей

имя Pk и определяем на множестве U функцию fk			по следующему правилу:
ì f	k−1	(u) + h(P ), если u Î P , u - прямая дуга,
ï		k	k
fk (u) = í fk−1		(u) - h(Pk ), если u Î Pk , u - обратная дуга,
ï f	k−1	(u), если u Ï P .
î		k

Построенная таким образом функция fk является потоком, и величина этого потока

определяется равенством

fk = fk −1 + h(Pk ) .

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

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

Доказательство алгоритма Форда - Фалкерсона приведено во второй части параграфа.

Пример 3. Построим максимальный поток для сети, изображенной на рис. 3.84,а.

◄ Шаг 0. Для любой дуги u положим f0 (u) = 0 (на рисунке этот поток отмечать не

будем, более того, договоримся и далее нулевой поток на дугах не отмечать), f0 = 0 .

Шаг 1. P1 : s ® a ® d ®t			- дополняющая цепь для потока f0 (стрелки заменяют имена
6	7	4
дуг, под каждой стрелкой записана остаточная пропускная способность h(u)
соответствующей дуги u ),			h (P1 ) = min{h(u)} = 4 , поток f1 указан на рис. 3.84,б,
			u P1

f1 = f0 + h(P1 ) = 4 .

PDF created with pdfFactory Pro trial version www.pdffactory.com

Шаг 2. P2 :	s → a →b → q →t					- дополняющая цепь для потока f1 , h (P2 ) = 2 , поток									f2
	2	3		5	12
указан на рис. 3.84,в,				f2 = f1		+ h(P2 ) = 6 .
Шаг 3. P3 :	s →b → q →t				- дополняющая цепь для потока f2 ,						h (P3 ) = 3 , поток			f3
	7	3		10
указан на рис. 3.84,г,				f3 = f2		+ h(P3 ) = 9 .
Шаг 4. P4 :	s →c→q →t				- дополняющая цепь для потока f3 ,						h(P4 ) = 5, поток			f4
	5	6		7
указан на рис. 3.84,д,				f4 = f3		+ h(P4 ) =14 .
Шаг 5. P5 :	s →b→a →d →q →t						- дополняющая цепь для потока f3 ,						h (P5 ) = 2 , поток
	4	2		3	8	2
f5 указан на рис. 3.84,е,					f5 =	f4	+ h(P5 ) =16 .
		a		7	d	4			a	7,4		d	4,4
	6								6,4
			3		8		t			3		8	t
	s	7		5				s	7		5
			b		q	12				b		q	12
		2							2
	5			6					5	6
		c							c
				а							б
		a		7,4	d	4,4			a	7,4		d	4,4
	6,6		3,2		8				6,6	3,2		8
							t				5,5		t
	s	7	b	5,2	q	12,2		s	7,3	b		q	12,5
		2							2
	5			6					5	6
		c							c
				в							г
		a		7,4	d	4,4			a	7,6		d	4,4
	6,6		3,2		8				6,6	3,0		8,2
							t				5,5		t
	s	7,3		5,5		12,10		s	7,5				12,12
		2	b		q				2	b		q
	5,5			6,5					5,5	6,5
		c							c
				д							е
							Рис. 3.84.
Для потока f5 нет ни одной дополняющей цепи из s									в t . Следовательно, поток f5
является максимальным. ►

Определение. Разрезом (Vs ,Vt ) в сети G называется пара множеств Vs и Vt ,

удовлетворяющих условиям:

PDF created with pdfFactory Pro trial version www.pdffactory.com

1)s ÎVs , t ÎVt ;

2)Vs ÈVt = V ;

3)Vs ÇVt = Æ .

Через Vs ® Vt	обозначим множество всех дуг, начала которых лежат в Vs , а концы - в
Vt , а через Vt	®Vs - множество всех дуг, начала которых лежат в Vt , а концы - в Vs .

Определение. Положим r(Vs ®Vt ) = å r(u) . Число r(Vs ®Vt ) называется

u Vs →Vt

пропускной способностью разреза (Vs ,Vt ) .

Определение. Разрез (Vs *,Vt *) называется минимальным, если для любого разреза

(Vs ,Vt ) справедливо неравенство r(Vs * ®Vt *) £ r(Vs ®Vt ) .

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

Если для сети найден максимальный поток, то минимальный разрез можно найти следующим образом: включить в множество Vs вершину s и все вершины v V , для каждой из которых существует цепь P из s в v с остаточной пропускной способностью h (P) > 0 ; положить Vt = V \ Vs . Полученный таким образом разрез (Vs ,Vt )

будет минимальным.

Пример 4. Вернемся к примеру 3. Используя найденный максимальный поток, несложно определить, что единственной вершиной, в которую можно добраться по цепи с положительной остаточной пропускной способностью, является вершина b .

Следовательно, пара множеств Vs = {s,b} и Vt = {a,c, d, q,t} образует минимальный разрез.

Упражнение 3.37. Найти максимальный поток и минимальный разрез для сети, изображенной:

а) на рис. 3.85; б) на рис. 3.86.

	8	a	3		q	4	t
		3	2		2
s	6			3		9	7
	5	4 b		5	p	4	r
		c			3

		a		4	q	10
		6	4	6
					5	7
	s	7	c				t
				3	4
		3				r
		12		5		9
		b			p

Рис. 3.85.

Рис. 3.86.

PDF created with pdfFactory Pro trial version www.pdffactory.com

Теоретические обоснования

Перейдем к обоснованию алгоритма Форда - Фалкерсона. Для произвольных разреза

(Vs ,Vt ) и потока f введем две числовые характеристики:

f (Vs ®Vt ) =	å	f (u)	- величина потока из Vs	в Vt ,
	u Vs →Vt
f (Vt ®Vs ) =	å	f (u)	- величина потока из Vt	в Vs .
	u Vt →Vs
Пример 5. Для потока			f , текущего по сети в примере 1, и разреза (Vs ,Vt ) , где

Vs = {s, a,c} и Vt = {b, d, q,t} , имеем f (Vs ®Vt ) = 9 , f (Vt ®Vs ) = 0 .

Лемма 1. Для любого потока f и любого разреза (Vs ,Vt ) справедливо равенство f = f (Vs ®Vt ) - f (Vt ®Vs ).

Доказательство. Согласно условию сохранения потока в вершинах, для произвольной вершины vÎVs \ {s} имеем:

f (v -) = f (v +) или f (v +) - f (v -) = 0 .

Следовательно, å ( f (v +) - f (v -)) = 0 . Сложив это равенство почленно с

v Vs \{s}

равенством f (s +) = f , получим:

å ( f (v +)

v Vs

	æ	ö
	å ç å	÷	-
	ç	f (u)÷
	v Vs èu v+	ø
	å	f (u) -
	u: u=(a,b),
	a Vs
å f (u) + å		f (u) -
u: u=(a,b),	u: u=(a,b),
a Vs , b Vs	a Vs , b Vs

- f (v -)) =

f

,

æ

ö

å ç å

÷

=

f

,

ç

f (u)÷

v Vs èu v−

ø

å

f (u) =

f

,

u: u=(a,b),

b Vs

å

f (u) - å f (u) =

f

.

u: u=(a,b),

u: u=(a,b),

a Vs , b Vs

a Vs , b Vs

Первое и третье слагаемые последнего равенства взаимно уничтожаются, следовательно,

PDF created with pdfFactory Pro trial version www.pdffactory.com

å	f (u) - å		f (u) =				f				,
u: u=(a,b),		u: u=(a,b),
a Vs , b Vs		a Vs , b Vs

f (Vs ®Vt ) - f (Vt ®Vs ) = f .■

Следствие 1. f = f (t -).

Доказательство. Пусть Vt = {t} , Vs =V \ {t} . Тогда f (Vs ®Vt ) = f (t -) , f (Vt ®Vs ) = 0 и

равенство из леммы 1 запишется следующим образом: f = f (t -).■

Следствие 2. Для любого потока f и любого разреза (Vs ,Vt ) справедливо неравенство f £ r(Vs ®Vt ) .

Доказательство. Из условия ограничения по пропускной способности

å f (u) £ å r(u) , т.е. f (Vs ®Vt ) £ r(Vs ®Vt ) .

u Vs →Vt u Vs →Vt

Тогда с учетом равенства из леммы 1 имеем:

f = f (Vs ®Vt ) - f (Vt ®Vs ) £ f (Vs ®Vt ) £ r(Vs ®Vt ). ■

Лемма 2. Если для некоторого потока f

и некоторого разреза (Vs ,Vt ) выполняется

равенство

f

= r(Vs ®Vt ) , то поток f

максимален, а разрез

(Vs ,Vt ) минимален.

Доказательство. Пусть f * - максимальный поток, а (Vs *,Vt *)

- минимальный разрез.

Тогда справедлива следующая цепочка неравенств:

сл. 2 леммы 1

f

£

f *

£ r(Vs* ®Vt *) £ r(Vs ®Vt ) .

Поскольку крайние члены в этой цепочке неравенств совпадают, то она превращается в цепочку равенств, а это означает, что поток f максимален, а разрез (Vs ,Vt ) минимален.

■

Лемма 3. Пусть f - поток в сети G и P является для						f		дополняющей цепью из s в t .
Тогда в сети G существует поток f% такой, что			f%		=		f				+ h(P) .
Доказательство. Определим в сети G функцию f% :U ® R по формуле
ì f (u) + h(P),	если u Î P,	u - прямая дуга,
f%(u) = íï f (u) - h(P),	если u Î P,		u - обратная дуга,
îï f (u), если u Ï P.

PDF created with pdfFactory Pro trial version www.pdffactory.com

Докажем, что функция f% является потоком.

Вначале покажем, что функция f% принимает только неотрицательные значения и удовлетворяет условию 1) определения потока.

Пусть u - прямая дуга цепи P . Тогда

0 £ f%(u) = f (u) + h(P) £ f (u) + h(u) = f (u) + (r(u) - f (u)) = r(u) .

Пусть u - обратная дуга цепи P . Тогда

f%(u) = f (u) - h(P) ³ f (u) - h(u) = f (u) - f (u) = 0 и f%(u) = f (u) - h(P) £ f (u) £ r(u) .

Таким образом, для любой дуги u цепи P выполнено 0 £ f%(u) £ r(u) . Если u P , то

0 £ f%(u) = f (u) £ r(u) .

Теперь убедимся в выполнении для функции f% условия 2) определения потока.

Понятно, что это условие следует проверить лишь для вершин v , входящих в цепь P . Пусть u1 - дуга, по которой пришли в вершину v , а u2 - дуга, по которой ушли из v .

Каждая из этих дуг может быть как прямой, так и обратной в цепи P . Следовательно, возможны четыре различных случая.

1. Пусть обе дуги u1 и u2 - прямые. В этом случае

f%(u1) = f (u1 ) + h(P) и f%(u2 ) = f (u2 ) + h(P) ,

так что

f%(v+) = f (v+) + h(P) и f%(v-) = f (v-) + h(P) .

Но для потока f выполнено условие f (v+) = f (v−) , следовательно, и для потока f% имеем f%(v+) = f%(v-) .

2. Пусть дуга u1 - прямая и u2 - обратная, т.е. обе дуги входят в вершину v . В этом

случае

f%(u1) = f (u1 ) + h(P) и f%(u2 ) = f (u2 ) - h(P) ,

так что

f%(v-) = f (v-) + h(P) - h(P) = f (v-) и f%(v+) = f (v+) .

PDF created with pdfFactory Pro trial version www.pdffactory.com

Так как для потока f выполнено условие f (v+) = f (v−) , то и для потока f% имеем f%(v+) = f%(v−) .

Аналогично рассматриваются случай 3 (обе дуги u1 и u2 - обратные) и случай 4 (дуга u1 - обратная и u2 - прямая).

Таким образом, мы показали, что функция f% - поток в цепи P .

Определим теперь величину потока f% . Напомним, что f% = f%(s+) . Из вершины s дуги

только выходят, поэтому та единственная дуга u с началом в вершине s , которая входит в цепь P , является прямой дугой цепи P . Следовательно, для нее выполнено равенство f%(u) = f (u) + h(P) . На остальных дугах, выходящих из s , поток не менялся,

так что имеем:

f% = f%(s+) = f + h(P) . ■

Объединяет приведенные выше результаты следующая теорема.

Теорема 3.11 (Форда - Фалкерсона). Для потока f в сети G следующие условия эквивалентны:

1) поток f максимален;

2) для f не существует дополняющей цепи из s в t ;

3) существует разрез (Vs ,Vt ), для которого f = ρ(Vs →Vt ) .

Доказательство. Доказательство проведем по следующей схеме: 1Þ 2 Þ 3 Þ1.

1Þ 2 . Будем рассуждать от противного. Предположим, что для максимального потока

f найдется дополняющая цепь P

из s в t . Тогда по лемме 3 существует поток f%

такой, что

f%

=

f

+ h(P) , т.е.

f%

>

f

. Полученное неравенство противоречит тому,

что поток f

максимален.

2 Þ 3. Определим Vs как множество всех вершин v ÎV , для каждой из которых существует цепь P из s в v такая, что h (P) > 0 . Добавим в Vs вершину s и положим

Vt = V \ Vs . Докажем, что для полученного разреза (Vs ,Vt ) выполняется равенство

f = ρ(Vs →Vt ) .

PDF created with pdfFactory Pro trial version www.pdffactory.com

Вначале покажем, что для любой дуги u Vs →Vt выполнено равенство f (u) = ρ(u) .

Будем рассуждать от противного. Предположим, найдется дуга u Vs →Vt , для которой f (u) < ρ(u) . Пусть v - начало, w - конец этой дуги, v Vs , w Vt . Множество Vs

определено нами так, что можно говорить о существовании цепи P из s в v , для которой h (P) > 0 . Дополним эту цепь дугой u и вершиной w до цепи Q из s в w .

Тогда

h (Q) = min (h (P), h (u)) = min (h (P),ρ(u) − f (u)) > 0

(здесь учтено, что u - прямая дуга в цепи Q и, значит, h (u) = ρ(u) − f (u) ). Но выполнение неравенства h (Q) > 0 означает, что вершина w Vs . Пришли к противоречию. Таким образом, предположение было неверным и для любой дуги

u Vs →Vt выполнено равенство f (u) = ρ(u) . Следовательно, f (Vs →Vt ) = ρ(Vs →Vt ) .

Аналогично показывается, что для всех дуг u Vt →Vs имеет место равенство f (u) = 0

и, следовательно, f (Vt →Vs ) = 0 . Поскольку (в силу леммы 1) для любого разреза справедливо равенство f = f (Vs →Vt ) − f (Vt →Vs ), для построенного разреза

получаем равенство

f = ρ(Vs ,Vt ) .

3 Þ1. Это утверждение полностью совпадает с утверждением доказанной ранее леммы

2. ■

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

Замечание. В ходе доказательства теоремы при обосновании справедливости перехода 2 Þ 3 был, по существу, предложен алгоритм нахождения минимального разреза.

PDF created with pdfFactory Pro trial version www.pdffactory.com