Grafové algoritmy

V zimním semestru 2014/2015 přednáším Grafové algoritmy. Přednášky se konají ve čtvrtky od 17:20 v S3. Začínáme 9. října opakováním toků v sítích.

Zatím se můžete podívat na obsah loňské přednášky, letošní bude podobná.

datum co se přednášelo
9. 10. Toky v sítích: základní definice a věty, Fordův-Fulkersonův algoritmus, Dinicův algoritmus, symetrická formulace toku.
16. 10. Toky v sítích: Dinicův algoritmus a důkladná analýza jeho všelijakých variant. Převod párování v bipartitních grafech a k-souvislosti na toky v sítích, Mengerova věta a související algoritmické úlohy. Zpřesňovací algoritmus pro celočíselné kapacity. Zmínka o algoritmus Tří Indů. Perfektní párování v regulárním bipartitním grafu pomocí redukce stupňů, souvislost s hranovým barvením.
23. 10. Pravděpodobnostní algoritmus na nejmenší řez v neorientovaném grafu (Karger-Stein).
30. 10. Nejkratší cesty: definice, problémy se zápornými cykly, prefixová vlastnost a stromy nejkratších cest. Obecný relaxační algoritmus a důkaz jeho korektnosti. Bellmanův-Fordův a Dijkstrův algoritmus coby speciální případy. Datové struktury pro Dijkstrův algoritmus: různé druhy hald.
6. 11. Nejkratší cesty: další datové struktury pro Dijkstru – přihrádky, víceúrovňové přihrádky, zmínka o HOT queues. Dinicův trik. Potenciálová redukce a eliminace záporných hran. Heuristiky na hledání cest mezi zadanou dvojicí vrcholů (algoritmus A*).
13. 11. Výpočet matice vzdáleností: Floydův-Warshallův algoritmus a jeho zobecnění na konstrukci sledových výrazů. Využití maticového násobení. Sledy očima algebraikovýma. Transitivní uzávěr metodou Rozděl a panuj.
20. 11. Seidelův algoritmus pro vzdálenosti v neohodnocených neorientovaných grafech. Úvod do minimálních koster: základní věty o struktuře (výměny, jednoznačnost, charakterizace pomocí lehkých hran). Červeno-modrý algoritmus a jeho dualita. Červeno-modrý pohled na Jarníkův, Borůvkův a Kruskalův algoritmus.
27. 11. Minimální kostry v rovinných grafech a minorově uzavřených třídách grafů (Borůvkův algoritmus s kontrakcemi a filtrováním). Hustota minorově uzavřených tříd: Maderova věta s důkazem, Kostočkova-Thomasonova bez důkazu.
4. 12. Minimální kostry ještě jednou: Fredmanův-Tarjanův algoritmus (iterovaná verze Jarníkova algoritmu). Stromoví předchůdci (LCA), intervalová minima (RMQ) a dekompozice na bloky.
11. 12. Testování rovinnosti grafů a kreslení grafů do roviny. Předehra: hledání mostů a artikulací prohledáváním do hloubky.
18. 12. Přednáška pro nemoc odpadla.
8. 1. Pokračování rovinného kreslení (slidy): doplnění detailů potřebných pro lineární čas, důkaz korektnosti.

Literatura

Stránku spravuje Martin Mareš