Изменения

Перейти к: навигация, поиск

Циркуляция потока

211 байт добавлено, 05:20, 17 декабря 2011
Нет описания правки
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков по каждому ребру изначальной сети в случае, если циркуляция есть, достаточно просто прибавить к потокам в ребрах $e'_i$ величины $l_i$.
</wikitex>
 
==Источники==
* [http://e-maxx.ru/algo/flow_with_limits e-maxx]
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']
355
правок

Навигация