403
правки
Изменения
→Определения
|definition=
'''Предпотоком''' ('''preflow''') будем называть функцию <tex> f: V \times V \rightarrow R </tex>, удовлетворяющую следующим свойствам:
1) <tex> f(uvu, v) = -f(vuv, u) </tex> (антисимметричность)
2) <tex> f(uvu, v) \leqslant c(uvu, v) </tex> (ограничение пропускной способностью)
3) <tex>\forall u \in V \setminus \{s, t\} \quad \sum\limits_{v \in V} f(vuv, u) \geqslant 0 </tex> (ослабленное условие сохранения потока)
}}
Как можно заметить, по своим свойствам предпоток очень похож на [[Определение сети, потока#Определение потока|поток]] и отличается лишь тем, что для него не выполняется закон сохранения потока.
{{Определение
|definition=
'''Избыточным потоком''' ('''excess flow'''), входящим в вершину <tex> u </tex>, назовем величину <tex> e(u) = \sum \limits_{v \in V} f(vuv, u) </tex>.<br>
Тогда вершина <tex> u \in V \setminus \{s, t\} </tex> будет называться '''переполненной'''('''overflowing'''), если <tex> e(u) > 0 </tex>.
}}
{{Определение
|definition=
Функция <tex> h: V \rightarrow N \cup \{0\}</tex> называется '''высотой вершины'''('''vertex label'''), если она удовлетворяет условиям:
1) <tex> h(s) = \left\vert V \right\vert </tex>
2) <tex> h(t) = 0 </tex>
3) <tex> \forall (u, v) \in E_f \quad h(u) \leqslant h(v) + 1</tex>
}}
