5.2 Матрица стоимости строительства

				X1			X2			X3			X4			X5			X6			X7			X8			X9
	X1			0		25			12			0			18			0			0			0			0
	X2		25				0		19			25			0			0			0			0			0
	X3		12			19				0		22			19			18			0			0			0
	X4		0			25			22				0		0			0			0			20			0
	X5		18			0			19			0				0		0			19			0			0
	X6		0			0			18			0			0				0		16			0			17
	X7		0			0			0			0			19			16				0		0			20
	X8		0			0			0			20			0			0			0				0		21
	X9		0			0			0			0			0			17			20			21				0

12

5.3 Минимальный поток и максимальная пропускная способность направления

Минимальное сечение графа для узлов Х1 и Х6: C(S) =	(Х3, Х6) С(Х7, Х6)
С(Х9 , Х6) = 15 + 5 + 4 = 54 (отмечено красным цветом)С.

Минимальный поток – ( 1, 3) ( 3, 6);

стоимость потока – 30 единиц (отмечено зеленым цветом).

Максимальная пропускная( 1, 2) способность( 2, 4) – 20( 4(отмечено, 3) ( желтым3, 6) цветом); имеет маршрут -

13

Список литературы

1.Википедия, www.wikipedia.ru

2.Kenneth H. Rosen - Discrete mathematics and its applications (7th edition)

14