Содержание
- 2. Сеть: - подсистема, транспортирующая некий продукт из одной точки в другую. Пример – нефтепровод, электропровод. -
- 3. Сеть. Наличие петель у графа недопустимо. Если существует ребро из vi и vj , то нет
- 4. Определение. Сеть – это ориентированный граф (G, V, E) вместе с весовой функцией C: E →
- 5. Поток. Для каждого ребра e имеется значение f(e) , которое является потоком через конкретное ребро (трубу).
- 6. Определение. Поток в сети – это функция f : E → N ∪ {0} такая, что
- 7. Принцип сохранения потока. Поток из а равен потоку в z , т.е. поток (а) = поток
- 8. Пример.
- 9. Пример (продолжение).
- 10. Пример (продолжение) .
- 11. Теорема. Для любого фиксированного потока f Следствие. Пусть S - подмножество множества V, содержащее а ,
- 12. Определения. Величина потока f , обозначаемая val(f) , равна поток(а) = поток(z) . Пусть S -
- 13. Определения. Поток f * в сети называется максимальным потоком, если val(f *) ≥ val(f) для любого
- 14. Следствия. Если val(f) = C(S, T) для некоторого потока f , а a – z сечения
- 15. Способ определения максимального потока сети. Рассмотрим сеть Максимальный поток (не обязательно единственный) легко найти способом
- 16. Пример. Сеть Кажется, что у этой сети максимальный поток, т.к. не существует ориентированного пути, по которому
- 17. Пример. Если поток из источника равен сумме пропускных способностей ребер, выходящих из источника, или поток, втекающий
- 18. Как находить максимальные в смысле потока сети? Сформируем пути из a в z , не обращая
- 19. Как находить максимальные в смысле потока сети? Нет возможности увеличить поток по этому пути, т.к. ребро
- 20. Возникли вопросы. 1) Почему выбираем 2? Очевидно – поток желательно увеличить как можно больше. Но не
- 21. Возникли вопросы. 2) Как это влияет на сохранение потока? Рассмотрим изменение на Поток, выходящий из вершины
- 22. Продолжене. Рассмотрим изменение на Поток из d в e уменьшен на ту же величину, на которую
- 23. C какого потока начать?
- 24. Нахождение максимального потока.
- 25. Пример. Найти максимальный поток для сети Шаг 1
- 26. Пример (продолжение). Шаг 2 – проверяем, не пусто ли множество S и выбираем вершину а. Шаг
- 27. Пример (продолжение).
- 28. Пример (продолжение).
- 29. Пример (продолжение).
- 30. Теорема. Алгоритм максимального потока строит максимальный поток для сети. Теорема. Поток f на заданной сети N
- 32. Скачать презентацию