Lemma 8 (Tuncelův odhad): Počet nenasycujících protlačení během maximum distance push-relabel algoritmu je nejvýše $\OO(n^2 \sqrt{m})$.

Důkaz: Připomeňme, že $d(v)$ nazýváme výškou vrcholu $v$. V průběhu algoritmu $H$ označuje maximální výšku aktivního vrcholu.

Výpočet algoritmu rozdělíme do fází mezi změnami hodnoty $H$. Změna fáze nastane když dojde ke zvýšení vrcholu, který ležel ve výšce $H$, a nebo když se přebytky všech vrcholů ležících ve výšce $H$ sníží na nulu.

Nyní ukážeme, že celkem proběhne nejvýše $4n^2$ fází. $H\geq 0$, roste pouze při zvýšení vrcholu a to o jedna. Celkový počet zvýšení $H$ je nejvýše počet zvýšení vrcholů a to je nejvýše $2n^2$ (lemma [ref]lemma_zvysovani[/ref]). Počet poklesů $H$ je nejvýše tolik, kolik celkem proběhne zvýšení $H$. Celkový počet změn $H$ (zvýšení nebo poklesů) a tedy i počet fází je nejvýše $4n^2$.

Počet nenasycených protlačení spočítáme pomocí potenciálu. Pevně si zvolíme parametr $K\in \NN$. Později ukážeme, že optimální volba je $K:=\sqrt{m}$. Zvolme potenciál

$$\Psi := \sum_{f(v)\gt 0} \frac{\vartheta(v)}{K},$$

kde $\vartheta(v):=|\{ w\in V\,|\, d(w)\leq d(v)\}|$ je počet vrcholů ve výškách nejvýše $d(v)$. Fázi nazveme levnou, pokud během ní proběhne nejvýše $K$ nenasycených protlačení, a drahou jinak.

Levných fází je nejvýše tolik, kolik je všech fází a to je nejvýše $4n^2$. Celkem během levných fází proběhne nejvýše $4Kn^2$ nenasycených protlačení.

Teď odhadneme počet nenasycujících protlačení během drahých fází. Podívejme se, co se děje s potenciálem $\Psi$ při následujících operacích.

  • Zvýšení vrcholu. Při zvýšení vrcholu $v$ se $\vartheta(v)$ zvýší nejvýše o $n$. $\vartheta(w)$ ostatních vrcholů $w$ může jen klesnout (vždy zvyšujeme vrchol $v$ s maximálním $d(v)$). Proto se $\Psi$ zvýší nejvýše o $n/K$.
  • Nasycující protlačení po hraně $uv$. Protože neměníme výšky vrcholů, tak můžeme $\Psi$ ovlivnit pouze tím, že přibude nebo ubude aktivní vrchol. Můžeme ubrat sčítanec $\vartheta(u)/K$ a přidat $\vartheta(v)/K \leq n/K$. Nasycující protlačení tedy zvýší $\Psi$ nejvýše o $n/K$. Podle lemma 6 je počet nasycujících protlačení během celého algoritmu nejvýše $2mn$.
  • Nenasycující protlačení po hraně $uv$. Po protlačení bude $f(u)=0$ a tedy z $\Psi$ ubyde $\vartheta(u)/K$. Dále může přibýt $\vartheta(v)/K$. Celkový úbytek $\Psi$ bude nejvýše $(\vartheta(u) – \vartheta(v))/K$. Protože $H=d(u)=d(v)+1$ ($uv$ je přípustná hrana), tak $(\vartheta(u) – \vartheta(v))$ odpovídá počtu vrcholů ve výšce $H$. Počet vrcholů ve výšce $H$ se během fáze nemění. Nemůže klesnout, protože pouze zvyšujeme vrcholy a povýšením některého vrcholu na výšku $H+1$ ukončíme fázi. V průběhu fáze dojde nejvýše k tolika nenasycujícím protlačení, kolik je aktivních vrcholů ve výšce $H$. V drahé fázi proběhne alespoň $K$ nenasycujících protlačení. Matematicky vyjádřeno $K \leq \# \mbox{nenasycujících protlačení} \leq \# \mbox{vrcholů ve výšce } H = \vartheta(u) – \vartheta(v)$. Proto je $(\vartheta(u) – \vartheta(v))/K \geq 1$. Tedy nenasycující protlačení sníží $\Psi$ alespoň o $1$.

Celkový součet přírůstků $\Psi$ je nejvýše $(2n^2 + 2nm)n/K$. Po inicializaci algoritmu bylo $\Psi$ nejvýše $n^2/K$. Protože $\Psi$ je stále kladné a každé nenasycující protlačení sníží $\Psi$ alespoň o $1$, je počet nenasycujících protlačení v drahých fázích nejvýše

$$ n^2/K + (2n^2 + 2nm)n/K \leq 5n^2 m /K. $$

Při odhadu jsme použili nerovnost $n\leq m$. Dohromady je počet nenasycujících protlačení v levných i drahých fázích nejvýše

$$ 4n^2 K + 5n^2 m/K \leq 5n^2 (K + m/K) \leq 10n^2 \sqrt{m}$$

pro volbu $K = \sqrt{m}$.

Podsekce: