Пример нахождения максимального потока

Дана транспортная сеть (рисунок 4.8). Найти для нее максимальный поток.

x₂ (9) x₃

3 4

(6) 2 (9)

x_{0 (}4) z

(7) (5)

4 x₁ (3) x₄ 3

Рисунок 4.8 – Транспортная сеть

Таблица 4.5 – Первый этап решения задачи

xi
	(0+,¥)
	(0+,3)
	(0+,3)
	(2+,3)
	(3+,3)
	(3+,3)

x₂ (9) x₃

6 7

(6) 2 (9)

x_{0 (}4) z

(7) 2 (5)

4 x₁ (3) x₄ 3

Рисунок 4.9 – Транспортная сеть после первого этапа

Таблица 4.6 – Второй этап решения задачи

xi
	(0^+,¥)
	(0^+,3)
	---
	(1^+,2)
	(1^+,1)
	(4^+,1)

x₂ (9) x₃

7

2 (9)

x_{0 (}4) z

(7) (5)

5 x₁ (3) x₄ 4

Рисунок 4.10 – Транспортная сеть после второго этапа

Таблица 4.7 – Третий этап решения задачи

xi
	(0+,¥)
	(0+,2)
	---
	(1+,2)
	(3+,2)
	(3+,2)

x₂ (9) x₃

9

4 (9)

x_{0 (}4) z

(7) (5)

7 x₁ x₄ 4

Рисунок 4.11 – Транспортная сеть после третьего этапа

Максимальный поток: 3+1+2=6.

Дата добавления: 2014-01-06