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
- Skriptíčka Krajinou grafových algoritmů (mají i v knihovně na MS; podívejte se ale na seznam známých chyb)
- Stránka loňské přednášky (letošní bude podobná)
- The Saga of Minimum Spanning Trees (má disertační práce, všechno možné i nemožné o minimálních kostrách a výpočetních modelech)
- Jiří Demel: Grafy a jejich aplikace (základní algoritmy, Kleeneho algebry)
- Alexander Schrijver: Combinatorial Optimization