Příklad 3.9

Máme za úkol najít minimální hranový řez pro graf na obr. 3.40.

Obr. 3.40 Zadaný graf k příkladu 3.9

Řešení:

Nejdříve upravíme graf tak, aby uzly zdroje u a spotřebiče v byly na okraji grafu, přidáme pomocnou hranu s ohodnocením nula a pak postupujeme podle algoritmu dolní cesty.

Obr. 3.41 Výsledný graf k příkladu 3.9

C(k) = 1 + 1 + 1 +1 + 2 = 6 jednotek.

Minimální hranový řez je C(k_min) = 6 jednotek (viz obr. 3.41).