Уч.пособие-по-ОДМ-2012

Для всех вершин транспортной сети свойства потока выполнены.

13.Помещаем вершины, в которые есть путь из источника, во множество вершин V1 (рассматриваем исходную транспортную сеть G).

v3

Так как все дуги, смежные

4 @s

@

с источником, насыщенны,

@

то ни в одну вершину, за ис-

v1 -

-3

3

@

ключением самого источни-

@s-5

@

@@ v4

@@

ка, пути нет. .

-

3

@

5

@

v0

is@--

s

-

s

v6

V1 = {v0},

2

-

V2 = {.v1, Пv2, v3, v4, v5, v6}.

@

2

@

@

Вершину

v

пометим сим-

v2s@-

- 6

волом

0

А

@@

i; вершины,.при-

Барашев

надлежащиеВ

множеству V2 -

1

@

vs5

.

символом .

G

С

14. Минимальный разрез содержит ребра, соединяющие вершины, принадлежащие разным подмножествам. В нашем примере это

3 ребра:	Унучек
	E1 = {((v0, v1), 3), ((v0, v4), 3), ((v0, v2), 2)}.
	МИРЭА
∑(E1) = c(v0, v1) + c(v0, v4) + c(v0, v2) = 3 + 3 + 2 = 8;
	(E1) = 8 = φ .
Мы убедились, что пропускная∑		способность| |	разреза равна вели-

чине максимального потока.

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

Пример 13.4. Найти максимальный поток в транспортной сети G.

251

v1

v3

6

@s-3-3

2

@s-

@@

@@

-

-

6

@

@

v0 s@-

@

-

sv5

5

@

4

@

v2s

vs4

-4

@

@

@

@

G

Решение.

П

1. Источником в данной транспортной сети является.вершина v0, а

стоком - вершина v5.

.

2. Строим граф перестроек G1′ , включая в него все вершины исход-

ной транспортной сети G и заменяя каждую дугу на две;

Барашев

А

.

3.

|φ|

= 0.В

.

v1

-

v3

Путь L1:

-

6

s0

0 3

s0-

v0

6 v1

3 v3

6 v5.

Унучек3- 3

С7→ 7→ 7→

v0

3

7→v2

7→v4

7→v5;

0

3-

6

sv5

Поток

φ, прошедший

v0 s0-

-2

4

по дугам этого пути, равен

v2s

0 4

vsМИРЭА4

5

0

-

-

φ = min( 6, 3, 6) = 3;

v2s

0 4

vs4

|φ| = 0 + 3 = 3.

4.

G1′

v1

-

v3

-

3

s0

3 0

s3-

Путь L2:

5

4

4

v0 s0-

-2

sv5

4

φ = min( 5, 4, 4) = 4;

5

0

-

-0

|φ| = 3 + 4 = 7.

G′2

5.

252

		v1			-	v3
	-	3	s0		3 0	s3-		Путь L3:
	3				3-	3		1	2	3
							sv5	v0 7→v2 7→v3 7→v5;
v0 s4-					-2	0		φ = min( 1, 2, 3) = 1;
	1			0	-	-4		|φ| = 7 + 1 = 8.
		v2s			4 0	vs4
6.					G3′
								Путь L4: .
		v1			-	v3
		3	s0		3 0	s4-
					-		s	.П4 1			2
	s5-				-1	0
v0	-				3	2	v5	3	3	4
	3							v0 7→v1	7→v4	7→
	0				-	-		В	7→v2	7→v3	7→v5.
		v2s		1	4 0	vs4				.
						4			А
					G4′
									.
Путь содержит дугу (v4, v2). Пропускная способность дуги (v2, v4)

в исходной транспортной сети равна 4. При вычислении потока,

проходящего по пути L4, учитываем реверсную способность дуги,

так как именно ребро l′′ (то есть, ребро, направленное в сторону,

Унучек

противоположную дуге

(v2, v4)), направленоСпараллельно этому

пути.

G′

МИРЭА

φ = min( 3, 3, 4, 1, 2) = 1;

|φ|

= 8 + 1 = 9.

7.

Барашевv - v

Все

дуги, сонаправленные

пути,

уменьшают

про-

пускные

способности

(в

1

3

2

s1

3 0

s5-

том

числе и

дуга

(v4, v2):

v0

-

2-

1

c(v4, v2) = 4 − 1 = 3);

4

-

v5

все

ориентированные

s5-

-2

0 s

ребра,

направленные

в

0

-

4

противоположную

пути

0

vs4

v2s

3 1

сторону,

увеличивают

5

пропускные

способности

(c(v2, v4) = 0 + 1 = 1).

8. Больше пути по дугам с ненулевыми пропускными способностями

253

нет. Строим итоговый поток.

v1

v3

Проверяем, выполнены ли

4

@s-1-3

2

@s-

свойства

потока

во всех

@

@

@

вершинах:

@

a) поток, исходящий из ис-

-

@-

5

@

v0 s@-

@

sv5

точника 4 + 5 =

|

φ

|

= 9;

@@ @@ 4

5

-

-

б) поток, входящий в сток

@

@

v2

s

3

v

s4

5 + 4 = |φ| = 9;

G

.

в) поток в промежуточных вершинах

v1 : 4 = 3 + 1;

v2 : 5 = 2 + 3;

v3 : 3 + 2 = 5;

v4 :

1 + 3 = 4.

.

В

Во всех вершинах свойства потока выполняются.П

i верши-

9. Находим минимальный

разрез,

помечая символом

Барашев

А

V1).

ны, в которые существует путь из источника (множество.

Несмотря на то, что дуга

(v0, v2) насыщенна, в вер-

шину

v2

.можно

попасть

v1

v3

по ненасыщенным

дугам

(v0, v1)С, (v1, v4) и (v4, v2).

6 @si-3-3

2

@s

-

-

@

-

6

Вершина

v2

принадлежит

@

@

множеству V1.

@

@

v0 si@-

@

sv5

(v2, v3)

и

@

@

4

Дуги

(v1, v3),

@

@

(v4, v5)

-

насыщенны,

к

5

-

-

@

@

v2

si

4

v

si4

вершинам

v3

и

v5 пути

G

из источника по дугам с

ненулевыми

пропускными

способностями нет.

V1

= {v0, v1

, v2, v4};

V2 = {v3, v5}.

МинимальныйУнучекразрез включает 3 ребра:

E1 = {(v1

, v3), (v2, v3), (v4, v5)}.

Проверим выполнениеМИРЭАтеоремы Форда-Фалкерсона:

(E1) = c(v1, v3) + c(v2, v3) + c(v4, v5) = 3 + 2 + 4 = 9 = |φ|.

254

Пример 13.5. Найти максимальный поток в транспортной сети, заданной списком дуг

{((v0, v1), 22) , ((v0, v4), 8) , ((v0, v2), 23) , ((v1, v3), 8) , ((v1, v6), 6) , ((v1, v4), 10) , ((v2, v4), 10) , ((v2, v7), 10) , ((v2, v5), 8) , ((v3, v6), 10) , ((v4, v6), 7) , ((v4, v8), 10) , ((v4, v7), 7) , ((v5, v7), 5) , ((v6, v8), 18) , ((v7, v8), 24)}.

Решение.

1. Изобразим транспортную сеть, заданную списком дуг, графиче-
ски:																								.
										v1					v3				.
														8 @s-10
																						П
																	@@
												-			6			@ v
															-
							22				@s-10							@s-618
													@					7		@
Барашев1																		В10			@ .
							-				8				@	-
					v0					-					@			-				@ v8
							s@-								@								s
													10 vs4-7						-
									23			-			10		@					.А
								@
										@								@			24
											@							@
										v2s@-8-								sv7
													@			-		5		С
															vs5
v0 s0-0 8															@
			Унучек10 vs40-0 10 24 sv8 φ = min(22, 8, 10, 18);
															@
				-								G
									МИРЭА
2. Строим граф перестроек G1′ ;															|φ|	= 0.
			v3
	-		8		s0-
v	0	- 10							v
						6			s0-6
22	s0-0						7										L1 :				8			10	18
-0 - 10				-0 - 18														22								;
																	v0 7→v1				7→v3			7→v6	7→v8
23	-	-						-													φ = 8;
									s
	0		0		10		7			v7									|φ| = 0 + 8 = 8.
										0
v2s0-							5
			vs5
			8		0

G′1

255

3.Изменяем пропускные способности дуг, вошедших в путь L1. Получаем новый граф перестроек G′2.

4.

5.

v0

v0

					v3
		-			0		s8-
				-
	v1
			8					2	v
								6
		s0-0							s8-6
	14						7						14	6		10
-8 - 10						-0		- 10		sv8	L2 :	v0 7→v1 7→v6				7→v8	;
s0-0			8		10 vs40-0 10 24						φ = min( 14, 6, 10) = 6;
23		-0		- 7					-0				|φ| = 8 + 6 = 14.
	v2s0-0						10 5		sv7				П
														.
						-						.
			G2		8		0
			′		vs5						В				.
					v3			0
														А
					0		s8-
Барашев											L3 : .
		-		-
	v1
			8					2	v
	8	s0-6 7							14s -6
-	- 10					-		-		v8	8		10	7		4
14	0		8				0	0	10		v0 7→vС1 7→v4			7→v6 7→v8;
s0-									4
					Унучек
					10 vs40- 24					s	φ = min( 8, 10, 7, 4) = 4;
23		-0		- 7					-0				|φ| = 14 + 4 = 18.
	v2s0-0						10 5		МИРЭА
									sv7
						-
					vs5
					8		0

G′3

256

6.

7.

v0

v0

v0

				v3
		-		0		s8-
				-
	v1
			8				2	v
							0
		s4-6						18s -6
-18	4					3					8	10
	- 6				-4		- 0		sv8	L4 : v0 7→v4		7→v8		;
s0-0			8 10 vs40-0 10 24							φ = min( 8, 10) = 8;
23		-0		- 7				-0		|φ| = 18 + 8 = 26.
	v2s0-0					10 5		sv7
					-						.
				vs5
				8		0					П
			G4′	v3
							0			.
										В
		-		0		s8-							.
				-
	v1
Барашев0 s8-
			8				2	v
-18	4	s4-6 3						18s -6			23	10		24
	- 6				-4 - 0				sv8	L5 : v0 7→v2А7→v7				7→v8	;
s0-8			0 10 vs40-8 2 24							φ = min.(23, 10, 24) = 10;
23		-0		- 7				-0		|φ| = 26 + 10 = 36.
18	8		0 Унучек4 8 2 v8 v0 7→v2								7→v5 7→v7 7→v8;
	v2s0-0					10 5		sv7		С
					-
				vs5
				8		0 5		sМИРЭАv7
	v2s0-10
						0
			G5′
				v3
		-		-
	v1
			8				2	v
							0
								18s -6
	4	s4-6 3								L6 :
-	-				-		-		s	13	8	5		14
				6				0
10s - 10 vs40- 14										φ = min(13, 8, 5, 14) = 5;
13		-0		- 7				-10			|φ| = 36 + 5 = 41.
					-
				vs5
				8		0

G′6

257

8.

9.

10.

v0

v0

					v3
		-			0		s8-
				-
	v1
			8					2	v
								0
		s4-6							18s -6
-18	4						3							8	10		2
	- 6					-4		- 0		sv8	L7 :	v0 7→v2			7→v4		7→v8	;
15s -8			0		10 vs40-8 2 9						φ = min( 8, 10, 2) = 2;
8		-0		- 7					-		|φ| = 41 + 2 = 43.
									15					.
	v2s5-10						5		sv7
							0 0
						-							П
					vs5
					3							.
			G7′
											В
		-			0		s8-									.
					v3									А
Барашев
	v1			-										.
			8					2	v
		s4-6						0	18s -6
-	4						3				L8 :
	-					-		-			6		8		7		9
18							4			v8	v0 7→v2 7→v4 7→v7 7→v8;
	8			0	6			10	0
17s -					8 vs40- 9					s	φ = min( 6, 8, 7, 9) = 6;
					Унучек
6		-2 - 7							-15		|φ| С= 43 + 6 = 49.
	v2s5-10						0 0		sv7
						-			МИРЭА
					vs5
					3		5

G′8

258

								v3
				-			0			s8-
						-
			v1
					8						0	2		v
				s4-6										18s -6
	-	4										3							L9 :
		-							-		-									4			6 1			3
v0	18									4								v8	v0 7→v1 7→v4 7→v7 7→v8;
		8			0		6					10			0		0
	23s -						2 vs46-										3	s	φ = min( 4, 6, 1, 3) = 1;
	0			-8		- 1							-21								|φ| = 49 + 1 = 50.
			v2s5-10							0		0		sv7
									-															.
								vs5
							3			5													П
					G9′			v3
11.																					.
																				В
											0
				-			0			s8-															.
						-
			v1
	Барашев@																							А
					8							2		v
	-	3		s5-6								3		18s -6					Больше пути из источни-
		- 5							-		- 0								ка в сток по дугам с нену-
	19				0					4				0				sv8	левой пропускной.						способно-
v0	23s -8						2 vs47-10										2
				-		-							-						стью нет. Строим итоговый
		0			8							0		22					поток.
	-			8
							Уну- 10 чекl M														(v0)
			v2s5-10							0		0		sv7								С
									-
								vs5
							3					sМИРЭАv7 φ(l) = 18 + 8 + 22 =
			v2s@-5-
										5
12.				G10′
								v3
					-	8 @s-8													Проверим, выполняются ли
			v1				-				@								свойства потока:
												@ v							a) в источнике
	19		@s-5									@s-618
	@@ 4													@@						+			φ(l) = 19 + 8 + 23 =
v0 @ -								@ - v8
																			∑
								@									@	s
	s-					8		vs4-7																= 50 =		φ	|
	@				-					@				-												|
	23							10			@						22		б)в стоке
		@
						@				-		5								∑
			@									@
					@			vs5											l	M−(v8)
																								= 50 = |φ|
								@

G

259

в) во всех промежуточных вершинах

v1 :

φ(l) = 19 = 8 + 6 + 5 =

φ(l);

l M−(v1)

l M

+(v1)

v2 :

∑

φ(l) = 23 = 8 + 10 + 5 = ∑

φ(l);

∑

∑

l M−(v2)

∑

l M+(v2)

v3 :

∑

φ(l) = 8 = 8 =

φ(l);

l M−(v3)

l M+(v3)

v4 :

φ(l) = 5 + 8 + 8 = 4 + 10 + 7 =

φ(l);

l M−(v4)

l M+(v4)

v5 :

∑

φ(l) = 5 = 5 =

∑

φ(l);

∑

∑

.

l M−(v5)

l M+(v5)

∑

v6 :

∑

φ(l) = 8 + 6 + 4 = 18 =

φ(l);

l M−(v6)

l M

+(v6)

v7 :

∑

∑

φ(l) = 7 + 10 + 5 = 22 =

φ(l).

l M−(v7)

l M+(v7)

В

13. Находим минимальный разрез, отмечая.символомП iвершины,

принадлежащие множеству V1

и символом

- вершины, принад-

лежащие множеству V2.

вершины v2

.

Барашевvsi5

есть путь в вер-

v3

В

вершину

v1 можно по-

@si-10

пасть из источника по нена-

8

сыщенной

.дугеА(v0, v1), из

v1 -

6

@@

вершины v1 - в вершины v4

-

@

v

СВ вершину v3 мож-

22

@si-10

@si-618

и v6.

Унучек

@@

7

@@

но добраться из v6 по дуге

-

8

-

10

v0

-

@

-

@

v8

(v6

, v3) с пропускной спо-

@

МИРЭА

si@-

10 vsi4-7

-

s

собностью 2.

23

-

10

@

@

@

@

24

@

@

Аналогично, в вершину v2

v2

si@-8-

s

v7

есть путь из источника по

@

@

5

дугам (v0, v4) и (v4, v2), из

-

@

G

шину v5.

Эти вершины образуют множество V1:

V1 = {v0, v1, v2, v3, v4, v5, v6 }.

Две оставшиеся вершины включаем во множество V2:

V2 = {v7, v8 }.

260