Содержание
- 2. Одной из наиболее важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины
- 3. Потоком в сети G = (Х,U) от входа s к выходу t называется неотрицательная функция U,
- 4. Условие (10.4) является уравнением сохранения потока, согласно которому поток, втекающий в вершину, равен потоку, вытекающему из
- 5. Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Величина максимального потока из s в
- 6. Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Минимальный разрез( ) — это разрез
- 7. Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Рис. 10.32 Разрез , состоящий из
- 8. Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Разрезом орграфа G2 (рис. 10.33) является
- 9. Пример 10.2. Задача о максимальном потоке Построить максимальный поток для ориентированной сети с источником S и
- 10. Пример 10.2. Задача о максимальном потоке Решение Составляем матрицу пропускных способностей дуг C = {cik} для
- 11. Пример 10.2. Задача о максимальном потоке 2. Выбираем произвольно один из путей от вершины S к
- 12. Пример 10.2. Задача о максимальном потоке (10.8) (10.8) 3. Выбираем следующий путь из S в t,
- 13. Пример 10.2. Задача о максимальном потоке (10.9) 4. Выбираем новый путь из S в t, т.е.
- 14. Пример 10.2. Задача о максимальном потоке Р3 = {s, x1, x3, x4, t} и определяем его
- 15. Пример 10.2. Задача о максимальном потоке (10.11) 6. Укажем путь Р5 = {s, x2, t} и
- 16. Пример 10.2. Задача о максимальном потоке (10.12) В столбце t имеются только нули. Следовательно, простроить новый
- 17. Пример 10.2. Задача о максимальном потоке Построим итоговую матрицу: С6 = С - С5. (10.13) На
- 18. Пример 10.2. Задача о максимальном потоке Рис. 10.35 Построенный граф G удовлетворяют условию потока, т.е. соблюдается
- 19. Пример 10.2. Задача о максимальном потоке 3. Увеличение потока вдоль построенного пути на максимально возможную величину,
- 20. Пример 10.2. Задача о максимальном потоке Уменьшающей дугой называется дуга, направление которой противоположное направлению потока, а
- 21. Пример 10.2. Задача о максимальном потоке Рассмотрим пример 10.2. Определить максимальный поток для сети (рис. 10.34).
- 22. Пример 10.2. Задача о максимальном потоке Решение. Начальное значение потока полагаем равным нулю Vo = 0.
- 23. Пример 10.2. Задача о максимальном потоке Рис. 10.36
- 24. Пример 10.2. Задача о максимальном потоке Р2 = {s, х4, t}, φ2 = min (4; 13-5)
- 26. Скачать презентацию