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

<wikitex>==Определение==

Определение:

Циркуляцией называется поток в сети $G(V, E)$ величины ноль.

Пример графа и циркуляции в нем (поток/пропуск.способность)

То есть закон сохранения потока [math]\sum\limits_v f(u,v)=0[/math] должен выполняться для всех без исключения вершин графа. Фактически, нет нужды в истоке и стоке. </wikitex>

Постановка задачи

<wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ — минимальная пропускная способность и $c_i$ — максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям на пропускные способности.

Если рассматривать тривиальный случай, когда все $l_i = 0$, то достаточно пустить поток величины ноль из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью. </wikitex>

Решение

<wikitex>фывафываф </wikitex>