Prohledávání do šířky BFS
Složitost: BFS doběhne v čase a spotřebuje paměti.
Prohledávání hloubky DFS
Složitost: BFS doběhne v čase a spotřebuje paměti.
Topologické třídění orientovaných grafů
Definice: Mějme orientovaný graf . Řekneme, že topologické uspořádání grafu je lineární uspořádání na množině takové, že:
Tzn. každý vrchol musí být ve výstupním pořadí dříve než jeho následníci.
Poznámky:
- Takové uspořádání existuje právě tehdy, když graf neobsahuje orientovaný cyklus, tj. je acyklický (DAG).
- Topologické uspořádání obecně není jediné a může jich být více.
Konstrukce topologického uspořádání
1. Odtrhávání zdrojů
Zdrojem nazveme vrchol, jehož vstupní stupeň (počet hran do něj) je .
2. Pomocí hloubkového prohledávání (DFS)
Při zpětném návratu z DFS (post-order) přidáme vrcholy do zásobníku. Výstupem je zásobník v opačném pořadí, tedy topologické uspořádání.
Příklad
Mějme graf s vrcholy a hranami:
- Vrcholy:
- Hrany: Topologická uspořádání mohou být:
Využití
- Plánování úloh (např. s předchůdci)
- Sestavování rozvrhů a kompilace programů (závislosti mezi jednotkami)
- Detekce cyklů v orientovaných grafech Poznámka: Oba algoritmy mají časovou složitost .
Hledání cest v ohodnocených grafech
Definujeme funkcí pro každou hranu a tomu řekneme délka.
Dijkstrův algoritmus
Pro kladné délky hran dává algoritmus dobré výsledky a udělá to v čase , avšak na-implementujeme-li algoritmus s haldou, tak můžeme časovou složitost zlepšit na a s binární haldou to vychází .
Bellman-Fordův algoritmus
Relaxační algoritmy jsou obecnou třídou algoritmů pro hledání nejkratších cest. Dijkstrův algoritmus je speciálním případem relaxačního algoritmu, který funguje pro nezáporné hrany. Chceme-li pracovat i se zápornými hranami (ale bez záporných cyklů), použijeme Bellman-Fordův algoritmus.
Přiřadíme každému vrcholu ohodnocení – odhad vzdálenosti z počátečního vrcholu . Na začátku:
- pro všechna ostatní
- (předchůdci) Poté relaxujeme hrany – hledáme, zda by přes nějakou hranu nevedla kratší cesta do cílového vrcholu.
Správnost a analýza
- Fáze výpočtu: Fáze otevře pouze , každá další fáze relaxuje vrcholy otevřené během .
- Invariant F (fáze): Po -té fázi platí: délka nejkratší cesty z do s nejvýše hranami.
- Zastavení: Pokud graf neobsahuje záporné cykly, algoritmus se zastaví po fázích.
- Složitost: Každou hranu relaxujeme nejvýše krát → časová složitost , kde .
Výhody a použití
- Funguje i pro záporné hrany.
- Detekuje záporné cykly.
Porovnání s Dijkstrovým algoritmem
Vlastnost | Dijkstra | Bellman-Ford |
---|---|---|
Záporné hrany | ❌ | ✅ |
Detekce záp. cyklu | ❌ | ✅ |
Složitost | (s fib. haldou) | |
Strategická volba vrcholu | min. (pomocí haldy) | FIFO fronta |
Minimální kostry grafu
Jako vážené grafu bereme takové, které mají nějakou funkci, která umí ohodnotit jejich hrany.
Jarníkův algoritmus
Takže vlastně je typický hladový algoritmus. Jarníkův algoritmus se po nejvýše iteracích zastaví a vydá nějakou kostru zadaného grafu a taková kostra je z výběru vrcholů minimální. Časová složitost je protože -krát musíme překontrolovat hran.
Borůvkův algoritmus
Jedná se o “paralelní verzi Jarníkova algoritmu”, kdy pěstujeme minimální kostřičky a ty spojujeme dohromady.
Tvrzení: Borůvkův algoritmus skončí po nejvýše iteracích a najde minimální kostru. Minimální kostra to jistě je, protože máme-li nějaký řez s nejlehčí hranou , tak pak je součástí minimální kostry a taková my vlastně vždy vybíráme. Borůvka tedy běží v čase
Toky v sítích a Ford-Fulkerson algoritmus
Toky v sítích Chceme najít maximální tok ze zdroje do stoku v orientované síti s kapacitami na hranách. Začneme nulovým tokem a postupně ho zlepšujeme, dokud už dál zlepšit nejde. Každý takový “zlepšovák” využívá tzv. zlepšující (augmentační) cestu, po které lze tok ještě zvětšit.
Klíčový nápad: povolíme tok nejen po směru hrany, ale i proti jejímu směru — v tom případě tok odčítáme.
Pro každou hranu definujeme rezervu jako:
To odpovídá:
- kolik můžeme přidat po směru :
- kolik můžeme ubrat proti směru : Hrana s je nenasycená, jinak nasycená.
Po každém kroku se velikost toku zvětší o ε – tedy o kladnou hodnotu. Pokud jsou kapacity celočíselné, tok poroste alespoň o 1, takže algoritmus musí skončit (nejvýše tolik kroků, kolik je součet kapacit všech hran do stoku).
Po zastavení víme:
- žádná nenasycená cesta neexistuje nelze dál zlepšovat
- definujeme množiny:
- vrcholy dosažitelné ze zdroje přes nenasycené cesty
Pak množina hran z do tvoří řez, který je:
- minimální, protože žádná hrana nemá rezervu (všechny nasycené)
- odpovídá toku – po řezu proudí tok rovný jeho kapacitě
Z toho plyne:
- žádný jiný tok nemůže být větší
- náš tok je maximální
Správnost a zastavení
- Pro celočíselné kapacity: algoritmus se jistě zastaví a tok je celočíselný.
- Pro racionální kapacity: přeškálujeme kapacity na celá čísla a aplikujeme algoritmus stejně.
- Pro iracionální kapacity: algoritmus nemusí skončit ani konvergovat. Poznámka:
- Pokud vybíráme vždy nejkratší nenasycenou cestu, získáme tzv. Edmonds-Karpův algoritmus, který je efektivnější: .
Komponenty silné souvislosti v orientovaných grafech
Definice: Silně souvislá komponenta (SSC) je maximální množina vrcholů, ve které existuje cesta mezi každou dvojicí vrcholů v obou směrech.
Složitost: – dvě DFS a přetočení hran.
Dinicův algoritmus pro maximální tok
Síť je orientovaný graf s kapacitami a určeným zdrojem a stokem:
- je orientovaný graf.
- je zdroj.
- je stok.
- je funkce udávající kapacitu každé hrany.
- je tok, pokud:
- Velikost toku je definována jako:
Rezerva udává, o kolik lze zvýšit tok přes hranu (nebo snížit v protisměru):
- Hrana je nasycená, pokud .
- Cesta je nenasycená, pokud má všechny rezervy kladné.
Intuice Dinicova algoritmu
- Vylepšujeme tok, dokud existují nenasycené cesty.
- Místo náhodných cest používáme jen nejkratší cesty — to omezuje počet fází.
- V každé fázi hledáme blokující tok: tok, který „zasytí“ alespoň jednu hranu každé cesty.
- Postupně tak zvyšujeme minimální délku zlepšujících cest → algoritmus skončí.
Hledání blokujícího toku
Intuice a důkazy korektnosti
Lemma K: Korektnost
Pokud algoritmus skončí, neexistuje cesta ze do v síti rezerv žádné další zlepšení toku není možné výstupní tok je maximální.
Lemma C: Délka se prodlužuje
Po každé fázi se nejkratší cesta prodlouží alespoň o 1 (protože jsme nasytili všechny dosavadní nejkratší).
Lemma S: Čas jedné fáze
Každá fáze trvá , protože konstrukce vrstvené sítě a blokujícího toku lze provést v lineárním čase vzhledem k počtu hran a vrcholů.
Věta: Složitost Dinicova algoritmu
- Nejvýše fází (protože délka nejkratší cesty se nejvýše -krát prodlouží)
- Každá fáze trvá
Goldbergův algoritmus pro hledání maximálního toku
Definice
Síť: Orientovaný graf s kapacitní funkcí , zdrojovým vrcholem a stokem .
Vlna: Funkce je vlna, pokud platí:
- (nepřekračuje kapacitu hran),
- , kde je přebytek toku ve vrcholu .
Každý tok je vlnou, ale ne každá vlna je tok – přebytky mohou být nenulové.
Rezerva: Pro hranu je:
Převedení přebytku: Můžeme převést přebytek po hraně , pokud:
Pak pošleme tok ve výši:
a aktualizujeme:
Intuice
Místo hledání cest postupně přesouváme přebytky ze zdroje k stoku nebo zpět. Abychom zabránili “cestování v kruhu”, zavádíme výšky a dovolujeme přesun pouze dolů (tj. ).
Když přebytek uvízne (není kam přelévat dolů), zvedneme výšku vrcholu.
Invariant A (základní):
- je vždy vlna.
- Výšky nikdy neklesají.
- , .
- pro .
Invariant S (spád):
Neexistuje hrana s kladnou rezervou a spádem .
Invariant C (cesta do zdroje):
Z každého vrcholu s existuje nenasycená cesta do .
Invariant V (výšky):
Důkaz korektnosti (Lemma K)
Když algoritmus skončí:
- Přebytek zůstává jen ve a .
- Tedy Kirchhoffovy zákony platí → je tok.
- Pokud by nebyl maximální, existuje nenasycená cesta z do .
- Ta by překonávala výšku , ale měla by nejvýš hran.
- Musela by mít hranu se spádem alespoň → spor s invariantem S.
Lemma Z (počet zvednutí):
Idea důkazu:
- Zvedáme výšku pouze tehdy, když je přebytek a nelze ho odvést žádnou hranou “dolů”.
- Díky invariantu C víme, že když je přebytek, existuje cesta do zdroje.
- Tato cesta překonává výšku nejvýše , takže pokud by výška překročila , musela by obsahovat hranu se spádem – to odporuje invariantu S.
Lemma S (nasycená převedení):
Idea důkazu:
- Mezi dvěma nasycenými převedeními po hraně musí být vrchol zvednut o alespoň 2 (kvůli spádu).
- Výška je omezena lemmatem Z (), takže mezi každými dvěma nasycenými převedeními je minimálně 2 zvednutí.
- Tedy pro každou hranu maximálně takových akcí.
Lemma N (nenasycená převedení):
Idea důkazu – potenciálová metoda: Zavádíme potenciál:
Pozorování:
- Potenciál se nikdy nezvýší příliš:
- Zvednutí: (max ×)
- Nasycené převedení: maximálně (celkem max )
- Ale každé nenasycené převedení ho sníží minimálně o 1 (odebereme a přidáme max ). Z toho plyne, že nenasycených převedení nemůže být více než celkové zvýšení potenciálu, tedy .
Věta (složitost Goldbergova algoritmu):
Idea důkazu:
- Sečteme počet jednotlivých operací a jejich čas:
- Zvednutí: × (každé v čase ) →
- Nasycené převedení: × (každé v čase ) →
- Nenasycené převedení: × (každé v čase ) →
- Největší složitost dominuje, tedy výsledná složitost je:
Změny v analýze algoritmů pro toky
1. Pokud jsou všechny kapacity hran celočíselné:
Pokud jsou všechny kapacity hran kladná celá čísla, pak Ford-Fulkersonův algoritmus skončí po konečném počtu kroků. Důkaz (intuice): Každá augmentační cesta zvýší tok o alespoň 1 jednotku (protože nejmenší nenulová rezerva je alespoň 1). Maximální možný tok je nejvýše součet kapacit hran ze zdroje — tj. nějaké konečné číslo .
- Po každé augmentaci se hodnota toku zvětší alespoň o 1.
- Proto algoritmus skončí nejvýše po krocích.
- Pokud je maximální tok , pak složitost je , kde je počet hran a celkový maximální tok.
Slabina: může být exponenciálně velké vzhledem k velikosti vstupu (např. pokud kapacity jsou velká čísla), proto algoritmus není polynomiální.
2. Pokud se Ford-Fulkerson používá s BFS (Edmonds-Karp algoritmus):
Ford-Fulkerson s výběrem augmentační cesty přes BFS (Edmonds-Karp) má časovou složitost:
Každá augmentační cesta je nejkratší (v počtu hran). Po každé augmentaci se délka nejkratší augmentační cesty nikdy nezmenší. Navíc:
- Délka augmentační cesty se může zvýšit nejvýše -krát.
- Každá hrana může být “kritická” (tj. její kapacita se stane nulovou na augmentační cestě) nejvýše -krát.
- Jelikož je hran , vznikne nejvýše augmentačních kroků. A každý BFS běží v , takže složitost je .
Párování v bipartitních grafech jako problém maximálního toku
Definice párování
- Párování je množina hran , kde žádné dvě hrany nesdílejí vrchol.
- Velikost párování je .
Převod bipartitního grafu na síť
Z bipartitního grafu vytvoříme síť :
- Najdeme levou partitu a pravou partitu .
- Hrany orientujeme z do .
- Přidáme:
- zdroj a hrany pro každé ,
- stok a hrany pro každé .
- Všechny hrany mají kapacitu 1: pro každé .
Korektnost: párování odpovídá toku
Tvrdíme: Po výpočtu maximálního toku odpovídá každá hrana s tokem 1 hraně v párování. Důkaz:
- Každý vrchol má z maximálně jeden tok → může být spojen s nejvýše jedním .
- Každý vrchol má do maximálně jeden tok → může být spojen s nejvýše jedním .
- Proto žádné dvě hrany netvoří konflikt na vrcholu: opravdu jde o párování.
Úplnost: každé párování je tok
Tvrdíme: Každému párování odpovídá celočíselný tok. Důkaz:
- Hranu nahradíme třemi hranami: , , , každou s tokem 1.
- Celkový tok odpovídá velikosti párování.
Tím vzniká bijekce mezi množinou párování a množinou celočíselných toků velikosti .
Časová složitost
Věta: Ford-Fulkerson na síti s jednotkovými kapacitami najde maximální tok v čase . Důkaz:
- BFS najde augmentační cestu v .
- V každém kroku se tok zvětší o 1.
- Maximální tok je nejvýše (víc než hrany nemůžeme vybrat).
- Celkem tedy kroků celkem .
Důsledek: Algoritmus pro párování
Tvrzení: Největší párování v bipartitním grafu lze najít v čase . Důkaz:
- Převod na síť: .
- Maximální tok: .
- Převod zpět na párování: .
- Celkově tedy .