Добавил:

ukusezha Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

МИРЭА - Российский технологический университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Дискретная математика

.pdf

Скачиваний:

Добавлен:

10.02.2023

Размер:

2.32 Mб

Скачать

☆

<<< < Предыдущая 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2526 / 2726 27 > Следующая >>>

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

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

4 @s

v1 -

-3

@s-5

@@ v4

si@--

v2s@-

1@@s

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

V1 = {v0},

V2 = {v1, v2, v3, v4, v5, v6}. Вершину v пометим символом i;0 вершины, принадлежащие множеству V2 - символом .

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

@s-3-3

@s-

v0 s@-

sv5

v2s

vs4

-4

Решение.

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

2.Строим граф перестроек G′1, включая в него все вершины исходной транспортной сети G и заменяя каждую дугу на две;

|φ| = 0.

	v1			-		v3
-	6	s0		0	3	s0-
-					-			sv5
0				3			6
0				-2
v0 s0-				-2		-	4
				-		-
				-		vs4
	v2s			0	4	vs4
	5		0			0
			0			0
4.					G1′
4.		s0			0	s3-
	3	s0		3	0	s3-
	v1			-		v3
-					-			sv5
3				3			3
3				-2
v0 s0-				-2		-	4
				-		-
				-		vs4
	v2s			0	4	vs4
	5		0			0
			0			0

G′2

Путь L1:

6	3	6
v0 7→v1	7→v3 7→v5.
Поток	φ,	прошедший

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

φ = min( 6, 3, 6) = 3; |φ| = 0 + 3 = 3.

Путь L2:

5	4	4	;
v0 7→v2	7→v4	7→v5	;

φ = min( 5, 4, 4) = 4; |φ| = 3 + 4 = 7.

252

	3	s0		3 0	s3-
	v1			-	v3
-				-
				-
s4-				-2		0
3				3		3
				-	-
				-	vs4
	v2s			4 0	vs4
	1		0		4
			0		4

G′3

sv5

Путь L3:

1	2	3	;
v0 7→v2	7→v3	7→v5	;

φ = min( 1, 2, 3) = 1; |φ| = 7 + 1 = 8.

		v1			-	v3
		3	s0		3 0	s4-	s	Путь L4:	4	1 2
	s5-				-1	0	s	3	4	1 2
v0	-				-	v5		3	3	4
v0	3				-	v5		v0 7→v1	7→v4	7→
					3	2
	0				-	-			7→v2 7→v3 7→v5.
		v2s		1	4 0	vs4
				1		4

G′4

Путь содержит дугу (v4, v2). Пропускная способность дуги (v2, v4) в исходной транспортной сети равна 4. При вычислении потока, проходящего по пути L4, учитываем реверсную способность дуги, так как именно ребро l′′ (то есть, ребро, направленное в сторону, противоположную дуге (v2, v4)), направлено параллельно этому пути.

φ = min( 3, 3, 4, 1, 2) = 1; |φ| = 8 + 1 = 9.

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

пути,

уменьшают

про-

пускные

способности

(в

s5-

том числе и

дуга

(v4, v2):

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

все

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

v0 s5-

-2

sv5

ребра,

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

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

пути

v2s

vs4

сторону,

увеличивают

G5′

пропускные

способности

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

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

253

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

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

@s-1-3

@s-

свойства

потока

во всех

вершинах:

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

v0 s@-

sv5

точника 4 + 5 =

= 9;

@@ @@ 4

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

5 + 4 = |φ| = 9;

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

v1 : 4 = 3 + 1;

v2 : 5 = 2 + 3;

v3 : 3 + 2 = 5;

v4 :

1 + 3 = 4.

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

i верши-

9. Находим минимальный разрез,

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

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

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

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

шину v2

можно

попасть

@si-3-3

@s-

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

дугам

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

Вершина

v2 принадлежит

множеству V1.

v0 si@-

sv5

vsi4

Дуги (v1, v3), (v2, v3) и

v2si

-4

вершинам

v3 и

v5 пути

(v4, v5) -

насыщенны, к

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

ненулевыми пропускными

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

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.Изобразим транспортную сеть, заданную списком дуг, графически:

@s-10

@s-618

s@-

10 vs4-7

s@-8-

sv7

2. Строим граф перестроек G′1; |φ| = 0.

					v3
		-			8		s0-
		-		- 10
	v1		0	- 10								v
			0						6			v
			s0-0						6			s0-6
-	22		s0-0							7		s0-6
-	- 10					-			- 18
0	- 10							0	- 18
0			8					0				10 24
s0-0			8		10 vs40-0							10 24
23		-		-							-
			0				10			7		0
	v2s0-0						10			5		sv7
						-
							s
					8			0
								0

G′1 v5

sv8

L1 :

22	8	10	18	;
v0 7→v1	7→v3	7→v6	7→v8	;

φ = min(22, 8, 10, 18);φ = 8;

|φ| = 0 + 8 = 8.

255

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

					v3
		-			0		s8-
		-		-
	v1			-
			8					6	2		v
			8								v
			s0-0								s8-6
-	14		s0-0						7		s8-6
-	- 10					-		- 10
8	- 10						0	- 10
8			8				0				10
s0-0			8		10 vs40-0						10	24
23		-		-						-
			0				10		7		0
	v2s0-0						10		5		sv7
						-
					vs5
					8		0
							0
			G2′
					v3
		-			0		s8-
		-		-
	v1			-
			8					0	2		v
			8								v
			s0-6								14s -6
-	8		s0-6						7		14s -6
-	- 10					-		-
14			8				0				10	4
s0-0			8		10 vs40-0						10	24
23		-		-						-
			0				10		7		0
	v2s0-0						10		5		sv7
						-
					vs5
					8		0
							0

G′3

sv8

14	6	10	;
L2 : v0 7→v1	7→v6	7→v8	;

φ = min( 14, 6, 10) = 6; |φ| = 8 + 6 = 14.

L3 :

8	10	7	4	;
v0 7→v1	7→v4	7→v6	7→v8	;

φ = min( 8, 10, 7, 4) = 4; |φ| = 14 + 4 = 18.

256

					v3
		-			0		s8-
		-		-
	v1			-
			8					0	2		v
			8								v
			s4-6								18s -6
-	4		s4-6						3		18s -6
-	-					-		-
18			8		6		4				10	0
s0-0			8		10 vs40-0						10	24
23		-		-						-
			0				10		7		0
	v2s0-0						10		5		sv7
						-
					vs5
					8		0
							0
			G4′
					v3
		-			0		s8-
		-		-
	v1			-
			8					0	2		v
			8								v
			s4-6								18s -6
-	4		s4-6						3		18s -6
-	-					-		-
18			0		6		4				2	0
s0-8			0		10 vs40-8						2	24
23		-		-						-
			0				10		7		0
	v2s0-0						10		5		sv7
						-
					vs5
					8		0
							0
			G5′
					v3
		-			0		s8-
		-		-
	v1			-
			8					0	2		v
			8								v
			s4-6								18s -6
-	4		s4-6						3		18s -6
-	-					-		-
18			0		6		4				2	0
10s -8			0		10 vs40-8						2	14
13		-		-						-
			0				0		7		10
	v2s0-10						0		5		sv7
						-
					vs5
					8		0
							0

G′6

sv8

8	10	;
L4 : v0 7→v4	7→v8	;

φ = min( 8, 10) = 8; |φ| = 18 + 8 = 26.

23	10	24	;
L5 : v0 7→v2	7→v7	7→v8	;

φ = min(23, 10, 24) = 10; |φ| = 26 + 10 = 36.

L6 :

13 8 5 14

v0 7→v2 7→v5 7→v7 7→v8;

φ = min(13, 8, 5, 14) = 5; |φ| = 36 + 5 = 41.

257

10.

					v3
		-			0		s8-
		-		-
	v1			-
			8					0	2		v
			8								v
			s4-6								18s -6
-	4		s4-6						3		18s -6
-	-					-		-
18			0		6		4				2	0
15s -8			0		10 vs40-8						2	9
		-		-						-
	8		0				0		7		15
	v2s5-10						0		0		sv7
						-
					vs5
					3		5
							5
			G7′
					v3
		-			0		s8-
		-		-
	v1			-
			8					0	2		v
			8								v
			s4-6								18s -6
-	4		s4-6						3		18s -6
-	-					-		-
18			0		6		4				0	0
17s -8			0		8 vs40-10						0	9
		-		-						-
	6		2				0		7		15
	v2s5-10						0		0		sv7
						-
					vs5
					3		5
							5

G′8

sv8

8	10	2	;
L7 : v0 7→v2	7→v4	7→v8	;

φ = min( 8, 10, 2) = 2; |φ| = 41 + 2 = 43.

L8 :

6 8 7 9

v0 7→v2 7→v4 7→v7 7→v8;

φ = min( 6, 8, 7, 9) = 6; |φ| = 43 + 6 = 49.

258

								v3
					-			0		s8-
					-		-
				v1			-
						8					0		2		v
						8									v
					s4-6										18s -6
	-		4		s4-6								3		18s -6
	-	-							-		-								sv8
	18					0		6		4					0			0
v0	23s -8					0		2 vs46-10							0			3
					-		-							-
							-								s
			0			8				0			1			21
				v2s5-10						0			0			v7
									-
								vs5
								3		5
										5
11.						G9′
11.
								v3
					-			0		s8-
					-		-
				v1			-
						8					0		2		v
						8									v
					s5-6										18s -6
	-		3		s5-6								3		18s -6
	-	-							-		-								sv8
	19					0		5		4					0			0
v0	23s -8					0		2 vs47-10							0			2
					-		-							-
							-								s
			0			8				0			0			22
				v2s5-10						0			0			v7
									-
								vs5
								3		5
										5
12.					G10′
12.
								v3
							8	@s-8
				v1						@@
						-			6				@ v
								-					@ v
	19			@s-5									@s-618
						@						4				@
					8		@						10				@
	-				8					-			10					@ v8
v0			-					@					-					@ v8
	s@-									@									s
	s@-					-	8 vs4-7								-				s
	23					-		10							-
	@									@
		@										@						22
				@									@
				v2s@-5-									sv7
						@				-		5
								@s
							@

L9 :

4	6	1	3	;
v0 7→v1	7→v4	7→v7	7→v8	;

φ = min( 4, 6, 1, 3) = 1; |φ| = 49 + 1 = 50.

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

Проверим, выполняются ли свойства потока:

a) в источнике

∑

φ(l) = 19 + 8 + 23 =

l M+(v0)

= 50 = |φ|

б)в стоке

∑

φ(l) = 18 + 8 + 22 =

l M−(v8)

= 50 = |φ|

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 :		∑		∑
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)						φ(l);
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.

@si-10

@si-618

@ v

si@-

vsi4-7

v2si@-8-

@si

В вершину v1 можно попасть из источника по ненасыщенной дуге (v0, v1), из вершины v1 - в вершины v4 и v6. В вершину v3 можно добраться из v6 по дуге (v6, v3) с пропускной способностью 2.

Аналогично, в вершину v2 есть путь из источника по дугам (v0, v4) и (v4, v2), из вершины v2 есть путь в вершину v5.

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

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

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

V2 = {v7, v8 }.

260

<<< < Предыдущая 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2526 / 2726 27 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
10.02.202380.26 Кб0Osnovnye_teoremy_differencialnogo_ischislenija_lekcija_7.docx
#
10.02.202336.15 Кб1Tochki_razryva__teorija_i_primery__.docx
#
09.02.2023397.04 Кб2впд 2.xlsx
#
09.02.20232.72 Mб4впд.xlsx
#
10.02.20231.44 Mб59Дзержинский. Дискретная математика.pdf
#
10.02.20232.32 Mб12Дискретная математика.pdf
#
09.02.20231.56 Mб1зад 2.docx