Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона
1. Теоретическая часть: 2. Что называется сетью? 3. Определение «сток» и «исток» на сети. 4. Поток на сети. 5. Мощность потока на сети. 6. Пропускная способность дуг. 7. Разрез на сети. 8. Пропускная способность разреза. 9. Теорема Форда-Фалкерсона. 10. Прямая и обратная дуга. 11. Алгоритм Форда-Фалкерсона. 12. Алгоритм построения потока с двойным ограничением потока по дугам. 13. Алгоритм построения потока в сети с несколькими источниками-стоками. 14. Алгоритм построения потока в сети с неориентированными ребрами. 15. Алгоритм построения потоков в сети с пропускными способностями узлов.
Практическая часть: В соответствии с вариантом для данной сети: - определить максимальный поток на сети; - построить разрез на сети; - определить пропускную способность разреза
Вариант №1 Вариант №2 Вариант №3 Вариант №4 Вариант №5 Вариант №6 Вариант №7 Вариант №8 Вариант №9 Вариант №10 Вариант №11 Вариант №12 Вариант №13 Вариант №14 Вариант №15 Вариант №16 Вариант №17 Вариант №18 Вариант №19 Вариант №20 Вариант №21 Вариант №22
Вариант №23 Вариант №24 Вариант №25 Вариант №26 Вариант №27 Вариант №28 Вариант №29 Вариант №30
|