Pokročilé grafové algoritmy

[zapotocnylubos]

1. Minimální kostra (MST)

Prerequisita pro TSP aproximaci i některé planární algoritmy.

• Kostra grafu – definice
• Kruskalův algoritmus – union-find
• Primův algoritmus – greedy rozrůstání
• 🔢 Příklad: konkrétní ohodnocený graf, krok za krokem oběma algoritmy

2. Síťové toky – základy

Základ pro vše v sekci toků i bipartitní matching.

• Tok v síti – definice, kapacity, zdroj a stok
• Maximální tok – co hledáme
• Řez sítě – definice
• Max-flow min-cut věta – intuice a důkaz
• 🔢 Příklad: jednoduchá síť, ruční výpočet maximálního toku

3. Ford-Fulkerson a Edmonds-Karp

Konkrétní algoritmy pro max-flow.

• Ford-Fulkerson – augmentující cesty, residuální graf
• Proč Ford-Fulkerson může cyklit (irracionální kapacity)
• Edmonds-Karp – BFS pro výběr augmentující cesty, složitost O(VE²)
• 🔢 Příklad: krok za krokem na konkrétní síti

4. Aplikace síťových toků

Ukázka síly toků – zdánlivě nesouvisející problémy se redukují na max-flow.

• Bipartitní matching přes flow – redukce
• Circulation with demands
• Project selection problem
• 🔢 Příklad: redukce bipartitního matchingu na max-flow krok za krokem

5. Bipartitní matching

Přímé algoritmy – efektivnější než obecný flow pro bipartitní grafy.

• Definice matchingu, maximální vs perfektní matching
• Alternující a augmentující cesty
• Hopcroft-Karp algoritmus – složitost O(E√V)
• Königova věta – min vertex cover = max matching v bipartitním grafu
• 🔢 Příklad: konkrétní bipartitní graf, krok za krokem

6. Obecný matching

Nejtěžší část – vyžaduje zvládnutí bipartitního matchingu.

• Proč bipartitní algoritmy nestačí – liché cykly (blossoms)
• Edmondsův blossom algoritmus – idea kontrakce lichých cyklů
• Složitost O(V³) – proč je to těžké
• 🔢 Příklad: graf s lichým cyklem, ukázka kontrakce blossomu

7. Planární grafy – základy

Nové téma, nezávislé na tocích a matchingu.

• Definice planárního grafu
• Eulerova formule V - E + F = 2
• Důsledky – maximální počet hran planárního grafu
• Kuratowského věta – K₅ a K₃,₃ jako překážky planarity
• 🔢 Příklad: ověření planarity konkrétního grafu, výpočet Eulerovy formule

8. Testování planarity a algoritmy na planárních grafech

Praktické využití planárních grafů.

• Testování planarity – lineární algoritmus (idea)
• Čtyřbarvový teorém – historie, co říká
• Algoritmy těžící z planarity – rychlejší BFS/DFS, SSSP
• Separator theorem – rekurzivní dělení planárního grafu
• 🔢 Příklad: planární embedding konkrétního grafu