Дана сеть, cij – пропускные способности маршрутов в каждом направлении

B 0

23

100

[ ;]S

17 10

2

A

5

0

F

0

11

Найти максимальный поток от источника S к стоку F на этом графе.

Дана сеть, cij – пропускные способности маршрутов в каждом направлении

B

0 5

23

	100		0	Cij
S			F
[ ; ]	17	10	0	C ji

2 11 A

fij

C ij

C ji

Сводим задачу к <аналогичной> предыдущей :

Cijij :: Cijij ffijij

Cjiji :: Cjiji ffijij

Найти максимальный поток от источника S к стоку F на этом графе.

Дана сеть, cij – пропускные способности маршрутов в каждом направлении

B

11

12

89

[ ;]S

17 21

2

A

5

0

F

11

0

Найти максимальный поток от источника S к стоку F на этом графе.

Дана сеть, cij – пропускные способности маршрутов в каждом направлении

B

11

12

89

[ ;]S

17 21

2

A

5

0

F

11

0

Найти максимальный поток от источника S к стоку F на этом графе.

[ ;]S

Дана сеть, cij – пропускные способности маршрутов в каждом направлении

89

17

B

11

21

2 1

2

A

5

0

F

11

0

Найти максимальный поток от источника S к стоку F на этом графе.

Дана сеть, cij – пропускные способности маршрутов в каждом направлении

B

11

02

89

[ ;]S

17 21

2

A

5

0

F

11

0

Найти максимальный поток от источника S к стоку F на этом графе.

Дана сеть, cij – пропускные способности маршрутов в каждом направлении

B

11

12

89

[ ;]S

17 21

2

A

5

0

F

11

0

Найти максимальный поток от источника S к стоку F на этом графе.

Дана сеть, cij – пропускные способности маршрутов в каждом направлении

		B
Путей нет		16	0
		12
[ ;]S	84		5
			F
	17	21	11

20

A

Найти максимальный поток от источника S к стоку F на этом графе.

	a
	5
	4
S
1
7
	(
	a
	+
	c
	+
	d
	)

0

			b
	+
0
1
		0
2
1

C

K				c
5					+a+b		+
b								d
+
	15
	D			b
						b 8
		a
	2				)
				c
			+
		b
	(
1
1

Старый		B
Граф Сij		0
	0	23
0
1
[ ;]S		10
1
7
		2
		A

b				Cij									fij
a		F		Cji
5
	Дана сеть, cij – пропускные способности														Старый
	маршрутов в каждом направлении
															Граф Сij
												B
5											6
									1				0
											2
			0			4					1				5
				F [ ;]S		8					1				F
						1
			0												1
											2
1						7									1
1									2				0
											A

Ответ:				Матрица потоков
		S		B	A		F		Граф
S		x		100 84	0
f B			0	x	23 12	5 0
A			0	0	x	11	0		0
F				0	0	x

Максимальная пропускная [ ;]S

способность сети

Fmax=16

		4
	8
-
0
0
1
0

0

потоков B

	5
2		-
			0
1
-
3
2
0			0
		-
	1
A	1

Найти максимальный поток от источника S к стоку F на этом графе.

FMax i fi		FMax X fSX .. Y fYF
0	F
0

Дана сеть, cij – пропускные способности маршрутов в каждом направлении

B

16

02

84

[ ;]S

17 21

2

A

0

5

F

11

0

Найти максимальный поток от источника S к стоку F на этом графе.

	Дана сеть, cij – пропускные способности маршрутов в
	каждом направлении			Вариант2:
		B
				Cij : Cij fij
		16	0
				Cji : Cji fij
		12
[ ;]S	84		5
			F
	17	21	11
	2		0
fSB=16= 11+5		A
Fsa=0			F.=f1+f2=5+11=16 =поток
fBS=11+0

fBF=5 +0 fAF=11 +0

Cij

C ji

				Прямая
				пропускнаяC ij
fij				способность
				Обратная
				пропускная C ji
				способность

Сводим задачу к <аналогичной> предыдущей :

Cij : Cij fij Cji : Cji fij