Смекни!
smekni.com

Графы (стр. 3 из 3)

Определение. Увеличивающей цепью, соединяющей вход и выход сети, называется простая цепь, все дуги которой являются допустимыми.

Пример 1. Построим увеличивающую цепь для сети S=(N, U), представленной на рисунке 15.


Над каждой дугой указана ее пропускная способность, в скобках – поток по этой дуге.

Цепь (s, 1, 2, 4, t) является увеличивающей, так как все дуги – допустимые:

· дуга (s, 1) – увеличивающая, так как она проходит по направлению потока, и поток по ней меньше ее пропускной способности: 6 < 9;

· дуга (1,2) – также увеличивающая дуга: 3 < 6;

· дуга (2,4) – уменьшающая, так как она проходит против потока и поток по ней 2 > 0;

· дуга (4, t) – увеличивающая: 4 < 7.

Пример 2. Построим максимальный поток для сети, представленной на рис. 4.16.

Рис. 16


Начальное значение потока равно нулю V=0.

Увеличивающие цепи:

1) (s, 1, 2, t), Dj = min (8, 4, 10) = 4;

2) (s, 1, 3, 4, t), Dj = min (8–4, 3, 2, 9) = 2.

Больше увеличивающих цепей построить нельзя.

Vmax = 6.

Построим теперь максимальный поток для неориентированной сети с той же структурой рис. 17.

Рис. 17

Увеличивающие цепи:

1) (s, 1, 2, t), Dj = 4;

2) (s, 1, 3, 5, t), Dj = 3;

3) (s, 3, 2, t), Dj = 2;

4) (s, 3, 4, t), Dj = 2.

Больше увеличивающих цепей не существует. Максимальный поток Vmax = 7+4 = 9+2 = 11. Оптимальная ориентация показана на рис. 18.

Рис. 18


Литература

1. Гончарова Г.А., Молчалин А.А. «Элементы дискретной математики»: Учебное пособие. М.: ФОРУМ: ИНФРА-М, 2005. (Серия «профессиональное образование»).

2. Фомин Г.П. «Математические методы и модели в коммерческой деятельности»: Учебник. – М.: Финансы и статистика, 2007.