Циркуляция потока — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Постановка задачи)
(Решение=)
Строка 14: Строка 14:
 
</wikitex>
 
</wikitex>
  
==Решение===
+
==Решение==
 
<wikitex>фывафываф
 
<wikitex>фывафываф
 
</wikitex>
 
</wikitex>

Версия 04:15, 17 декабря 2011

<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>