Графы (стр. 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.