Изменения

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

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

41 байт убрано, 21:19, 10 декабря 2020
убрал багнутый тег
<wikitex>
{{Определение
|definition=
Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать рёбра с положительной нижней пропускной способностью.
</wikitex>
==Решение==
<wikitex>Для решения этой задачи заменим исходную сеть $G$ на $G'$ следующим образом. Сначала добавим в граф вершины $s$ {{---}} исток и $t$ {{---}} сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим рёбра $s \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} t$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$ (см. рисунок 2).
[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований рёбер.]]
Значит, этот поток и есть циркуляция.
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все рёбра их из истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль рёбер в сети $G'$ соответствующие значения минимальной пропускной способности.</wikitex>
==Псевдокод==
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/60187...75258»

Навигация