338
правок
Изменения
м
→Корректность алгоритма
##Если <tex>u</tex> подверглась подъему, то вершин предшествующих <tex>u'</tex> на следующей итерации, кроме <tex>u</tex>, нет или если высота <tex>u</tex> не изменилась, то там остались те же вершины, что и ранее. Так как <tex>u</tex> подверглась разгрузке, то она не содержит избытка потока. Значит, если <tex>u</tex> подверглась подъему в процессе разгрузки, то ни одна вершина, предшествующая <tex>u'</tex>, не содержит избытка потока.
##Если высота <tex>u</tex> не поменялась, в процессе разгрузки, то вершины, стоящие в списке <tex>L</tex> перед ней, не получили избыток потока, так как <tex>L</tex> топологически упорядочен все время в процессе разгрузки, поэтому каждая операция проталкивания продвигает поток только по вершинам дальше по списку. В этом случае ни одна вершина, предшествующая <tex>u'</tex>, также не имеет избытка потока.
#После завершения цикла <tex>u = null</tex>, поэтому избыток всех вершин равен <tex>0</tex>, так как при каждом выполнении проверки условия при заходе в цикл '''while''' список <tex>L</tex> является топологическим упорядочением вершин допустимой сети <tex>G_{f, h} = (V, E_{f, h}инвариант цикла)</tex>. Значит, ни одна основная операция неприменима.
== Анализ ==
