Изменения

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

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

15 байт убрано, 08:22, 18 декабря 2011
Постановка задачи
<wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ {{---}} минимальная пропускная способность и $c_i$ {{---}} максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности.
Если рассматривать Рассмотрим тривиальный случай, когда все $l_i = 0$, то достаточно пустить поток величины ноль из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.
</wikitex>
355
правок

Навигация