Контрольная работа: Графы
Рис. 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.
Комментарии:
| |||||
|
Работы, похожие на Контрольная работа: Графы
