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

VlastnostDijkstraBellman-Ford
Záporné hrany
Detekce záp. cyklu
Složitost (s fib. haldou)
Strategická volba vrcholumin. (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 .