Adaptace Matematických ALGoritmů

Ford-Fulkersonův algoritmus slouží k vyhledání maximálního toku v síti (Síť je orientovaný graf, kde ohodnocení každé hrany znamená maximální množství energie, které skrze hranu může procházet). Pracujeme tedy se sítí $G = (V, E)$, kde $V$ je množina vrcholů včetně zdroje $S$ a stoku $T$, $E$ je množina orientovaných hran. Návěští každé hrany zapisujeme ve formátu $F/C$, kde $C$ značí její kapacitu a $F$ tok, tj. množství energie, které v ní proudí.

1. Na počátku algoritmu nastavíme u všech hran nulový tok.
2. Opakovaně hledáme nenasycenou cestu od zdroje ke stoku. Jakmile ji nalezneme, zjistíme minimální rezervu kapacity všech jejích hran, o kterou následně navýšíme tok v síti.

Při běžném provedení algoritmu pracujeme s vizuální reprezentací sítě, u níž měníme návěští hran. Na Obrázku 1 je znázorněna síť $N$ o sedmi vrcholech s aktuálním tokem 1 (viz cesta $S → A → C → T$). Je zvýrazněna nenasycená cesta $S → B → D → T$, u níž je minimální rezerva kapacity hran rovna 1. Můžeme tedy v dalším kroku zvýšit tok v síti a upravit návěští hran nenasycené cesty, tj. modifikovat $0/1$ na $1/1$ v případě hran $S → B, B → D$ a $0/3$ na $1/3$ u hrany $D → T$.

Příklad 1: síť $N$

Obrázek 1: Síť $N$ s tokem 1 a vyznačenou nenasycenou cestou $S → B → D → T$

Pro názornost uvádíme i konkrétní příklad sítě a Animaci 1 naznačující výpočet maximálního toku pomocí Ford-Fulkersonova algoritmu.

1. Práce se sítí v jednom listu tabulkového procesoru:

Síť je opět nabízena ve formě tabulky a organizována podobným způsobem jako v případě 1. metody adaptace Dijkstrova algoritmu. V prvním sloupci jsou vypsány uzly sítě, do dalších buněk na stejném řádku pro daný uzel $X$ zapisujeme všechny hrany, které začínají v uzlu $X$. Uvádíme je ve formátu  $Y$–$F/C$, kde $Y$ je uzel, ve kterém orientovaná hrana z $X$ končí, $F$ je aktuální tok skrze hranu a $C$ je její kapacita. Uvažujme tutéž síť $N$, jakou jsme znázornili na Obrázku 1. Následující Tabulka 1 zachycuje fázi algoritmu, při níž jsme již nalezli jednu nenasycenou cestu $S → A → C → T$.

Nevidomý student nejprve najde nenasycenou cestu od zdroje $S$ ke stoku $T$. Prochází postupně tabulkou a pamatuje si posloupnost uzlů, kterými cesta vede, i aktuální minimální rezervu jejích hran. Ve druhém průchodu již upravuje tok a nasycené hrany označuje hvězdičkou.

2. Organizace hran pod sebou na jednotlivých řádcích v běžném textovém editoru:

Každou hranu zapisujeme na samostatném řádku ve formátu $X$–$F/C$–$Y$, kde $X$ je počáteční uzel hrany, $Y$ koncový uzel hrany, $F$ aktuální tok skrze hranu a $C$ její kapacita. Hrany řadíme abecedně dle uzlu, ze kterého vycházejí. Pracujeme s nimi obdobným způsobem jako u první metody, tj. procházíme hrany vždy dvakrát, poprvé, abychom nalezli nenasycenou cestu od zdroje ke stoku, podruhé, abychom upravili tok na této cestě.

V tomto případě u nevidomých studentů zvítězila 1. metoda. Nebylo příliš složité se orientovat v tabulce a hledat nenasycenou cestu (Poznamenejme, že problém nastává ve chvíli, kdy je k nalezení maximálního toku nutné některé hrany procházet proti směru toku.). Nevýhodou druhé metody je fakt, že při hledání nenasycené cesty musí nevidomý často projít mnoha řádky s údaji, které jsou pro něj v tu chvíli nepodstatné. U obou nabízených adaptací se jeví jako vhodné poznamenat si zpracovávanou nenasycenou cestu např. do textového editoru (stačí vypsat posloupnost vrcholů od zdroje ke stoku).