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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определения)
Строка 2: Строка 2:
  
 
== Определения ==
 
== Определения ==
 +
{{Определение
 +
|definition=
 +
'''Предпотоком''' ('''preflow''') будем называть функцию <tex> f: V \times V \rightarrow R </tex>, удовлетворяющую следующим свойствам:
 +
1) <tex> f(uv) = -f(vu) </tex>
 +
 +
2) <tex> f(uv) \leqslant c(uv) </tex>
 +
 +
3) <tex>\forall u \in V \setminus \{s, t\} \quad \sum\limits_{v \in V} f(vu) \geqslant 0 </tex>
 +
}}
 +
 +
Как можно заметить, по своим свойствам предпоток очень похож на [[Определение сети, потока#Определение потока|поток]] и отличается лишь тем, что для него не выполняется закон сохранения потока.
 +
 
== Идея ==
 
== Идея ==
 
== Операции ==
 
== Операции ==

Версия 19:45, 6 декабря 2012

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

Определения

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

1) [math] f(uv) = -f(vu) [/math]

2) [math] f(uv) \leqslant c(uv) [/math]

3) [math]\forall u \in V \setminus \{s, t\} \quad \sum\limits_{v \in V} f(vu) \geqslant 0 [/math]


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

Идея

Операции

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

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

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

Источники