Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона
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
|
