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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определения)
м (Определения)
Строка 12: Строка 12:
 
}}
 
}}
 
Как можно заметить, по своим свойствам предпоток очень похож на [[Определение сети, потока#Определение потока|поток]] и отличается лишь тем, что для него не выполняется закон сохранения потока.
 
Как можно заметить, по своим свойствам предпоток очень похож на [[Определение сети, потока#Определение потока|поток]] и отличается лишь тем, что для него не выполняется закон сохранения потока.
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=

Версия 23:21, 6 декабря 2012

Метод проталкивая предпотока — обобщенный алгоритм нахождения максимального потока в транспортной сети. В отличии от алгоритма Эдмондса-Карпа и алгоритма Диница не является частным случаем метода Форда-Фалкерсона.

Определения

Определение:
Предпотоком (preflow) будем называть функцию [math] f: V \times V \rightarrow R [/math], удовлетворяющую следующим свойствам:

1) [math] f(u, v) = -f(v, u) [/math] (антисимметричность)

2) [math] f(u, v) \leqslant c(u, v) [/math] (ограничение пропускной способностью)

3) [math]\forall u \in V \setminus \{s, t\} \quad \sum\limits_{v \in V} f(v, u) \geqslant 0 [/math] (ослабленное условие сохранения потока)

Как можно заметить, по своим свойствам предпоток очень похож на поток и отличается лишь тем, что для него не выполняется закон сохранения потока.


Определение:
Избыточным потоком (excess flow), входящим в вершину [math] u [/math], назовем величину [math] e(u) = \sum \limits_{v \in V} f(v, u) [/math].
Тогда вершина [math] u \in V \setminus \{s, t\} [/math] будет называться переполненной(overflowing), если [math] e(u) \gt 0 [/math].


Определение:
Функция [math] h: V \rightarrow N \cup \{0\}[/math] называется высотой вершины(vertex label), если она удовлетворяет условиям:

1) [math] h(s) = \left\vert V \right\vert [/math]

2) [math] h(t) = 0 [/math]

3) [math] \forall (u, v) \in E_f \quad h(u) \leqslant h(v) + 1[/math]


Идея

Операции

Схема алгоритм

Корректность алгоритма

Оценка быстродействия

Источники