76
правок
Изменения
м
|about=Следствие из теоремы
Нет описания правки
==Алгоритм==
Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода(на вход подается транспортная сеть <tex>G = (V, E)</tex>):
===Псевдокод===
'''simpleDecomposition(s)'''
<tex> P \leftarrow \varnothing </tex>
<tex>v \leftarrow s</tex>
'''while''' <tex> v \neq t </tex> и <tex> v \notin Q P </tex>
находим <tex> (vu): f(vu)>0 </tex>
'''if''' <tex>\neg \exists (vu): f(vu)>0 </tex>
'''if''' <tex> v = t </tex> '''break''' '''else''' '''return''' NULL
<tex> Q \leftarrow Q \cup (vu) </tex>
<tex> P \leftarrow P \cup v </tex>
'''while '''<tex> p = </tex> simpleDecomposition(s) <tex> \neq </tex> NULL
<tex> d \leftarrow d \cup p </tex>
'''for''' <tex> u \in V </tex>
'''while '''<tex> p = </tex> simpleDecomposition(u) <tex> \neq </tex> NULL
<tex> d \leftarrow d \cup p </tex>
'''return''' d
===Анализ работы алгоритма===
{{Утверждение
|statement=
Время работы алгоритма поиска декомпозиции потока, описанного выше, равно <tex>O(VE)</tex>.
