Grafové algoritmy

V zimním semestru 2017/2018 přednáším o grafových algoritmech. Přednáška bude pokrývat pokročilejší algoritmy pro nejkratší cesty, toky v sítích, minimální kostry a další grafové problémy a také v ní zmíníme některé datové struktury pro dynamickou reprezentaci grafů.

Přednáška se koná každé pondělí od 17:20 v S4.

datum co se přednášelo
9. 10. Toky v sítích: základní definice a věty, Fordův-Fulkersonův algoritmus, symetrická formulace toku, dualita toků a řezů. 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.
16. 10. Toky v sítích: Dinicův algoritmus a důkladná analýza jeho všelijakých variant. Zpřesňovací algoritmus pro celočíselné kapacity.
23. 10. Nejmenší řezy a separátory v neorientovaných grafech pomocí toků. Pravděpodobnostní algoritmus Kargera a Steina.
30. 10. Ú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.
6. 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.
13. 11. Minimální kostry: Jarníkův algoritmus s Fibonacciho haldou, Fredmanův-Tarjanův algoritmus (iterovaná verze Jarníkova algoritmu). Nejkratší cesty: definice, problémy se zápornými cykly, prefixová vlastnost a stromy nejkratších cest.
20. 11. Nejkratší cesty: Obecný relaxační algoritmus a důkaz jeho korektnosti. Bellmanův-Fordův a Dijkstrův algoritmus coby speciální případy relaxace.
27. 11. Plán: Datové struktury pro Dijkstrův algoritmus: různé druhy hald, přihrádky, víceúrovňové přihrádky, zmínka o HOT queues. Dinicův trik pro neceločíselné délky hran. Potenciálová redukce a eliminace záporných hran. Heuristiky na hledání cest mezi zadanou dvojicí vrcholů (algoritmus A*).

Literatura

Stránku spravuje Martin Mareš