Kursovaja_po_MOTS_19

6/1

7/6

3

5/4

7/5

10

S

3/5

5/2

4/3

6

8/3

8/5

2

4/5

5/5

6/7

5

9

9/6

Определить максимальный поток φ _max между х ₁ и х _10.

Составим матрицу пропускной способности:

		7
	0		5		6
				9		3	6
			0				1	2
		0				4			9
			0		0				5	4
			0	0				5		7
				0			0			9
					0	0				8
						0	0	0	0

					6
	4			9		3	6
			0				1	2
		0				4			9
			0		0				5	4
			0	0				5		7
				0			0			9
					0	0				8
						0	0	0	0

					6
	4			9						0
	0		0				1	2
		0				4			9
					0				5
			0	0				5		7
				0			0			9
					0	0				8
			5

			1
	4	4		9		0	6			0
	0		0				1	2
									9
			3						5
			0	0				5		7
				0			0			9
					0	0				8
			5