Изменения

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

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

7 байт добавлено, 08:19, 18 декабря 2011
Определение
<wikitex>{{Определение
|definition=
'''Циркуляцией''' называется поток в [[Определение сети, потока|сети]] $G(V, E)$ нулевой величины ноль.
}}
[[Файл:Циркул2.png|frame|справа|Пример графа и циркуляции в нем (поток/пропуск.способность)]]
То есть закон сохранения потока <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' без исключения вершин графа. Фактически, нет нужды в истоке и стоке.
</wikitex>
 
==Постановка задачи==
<wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ {{---}} минимальная пропускная способность и $c_i$ {{---}} максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности.
Анонимный участник

Навигация