Grafové algoritmy II

V letním semestru 2025/2026 učím Grafové algoritmy II [NDMI088]. Navazují na Grafové algoritmy ze zimního semestru. Podíváme se na některá pokročilejší témata, jako je například kreslení grafů do roviny, algoritmy pro celočíselně ohodnocené grafy, grafové datové struktury a Pettieho optimální algoritmus na minimální kostry.

Přednášky se odehrávají ve středy od 15:40 v S8.

Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares@kam.mff.cuni.cz a domluvíme se.

Syllabus

datum témata [zdroje] záznam
18. 2. Testování rovinnosti a kreslení do roviny (algoritmus Boyer-Myrvoldová). Předehra: bloková struktura grafů. Kreslení grafů v reverzním DFS pořadí. Detaily potřebné pro lineární čas: externalita, reprezentace bloků. [G11] [BM]
25. 2. Pokračování rovinného kreslení (slidy): označení živého podgrafu, procházecí pravidla, sestavení celého algoritmu, důkaz správnosti [G11] [BM]. video
4. 3. Verifikace minimality kostry: redukce hloubky pomocí Borůvkových stromů, Komlósův algoritmus [S3.3]. video
11. 3. Analýza Komlósova algoritmu [S3.3]. Kargerův-Kleinův-Tarjanův algoritmus: randomizovaný algoritmus, který najde minimální kostru v průměrně lineárním čase [S3.5]. video
18. 3. Přednáška odpadá.
25. 3. Připomenutí modelů výpočtu: Random Access Machine, Pointer Machine a mnoho jejich variant [S2.1]. Vektorové výpočty na RAMu [S2.4]. Implementace Komlósova algoritmu v lineárním čase na RAMu: reprezentace dat [S3.4]. video
1. 4. Implementace Komlósova algoritmu v lineárním čase na RAMu: dokončení [S3.4]. Přihrádkové třídění na PM: eliminace násobných hran, izomorfismus stromů [S2.2]. video
8. 4. Přihrádkové třídění na PM: centrum stromů, unifikace řetězců [S2.2]. Topologické výpočty na grafech a kanonické kódy grafů [S2.2]. Zoo Ackermannových funkcí a jejich inverzí [SA.3]. video
15. 4. Offline algoritmus na stromové předchůdce (LCA) na Pointer Machine [B1–4] (oddíly 4.1–4.3 v článku jsou ekvivalentní s naší mašinerií topologických grafových výpočtů). Aplikace téhož přístupu na verifikaci minimálních koster: problém Link-Eval, generování rozhodovacích stromů pomocí Komlósova algoritmu [B5]. video
22. 4. Přednáška se nekoná.
29. 4. Datová struktura pro Link-Eval [T] ve třech verzích: obecná, s levými inverzemi, pro maximum. Úvod do Soft hald: rozhraní, příklad s hledáním pseudomediánů. video
6. 5. Soft haldy podle Hagerupa (tahák) [H] video
13. 5. Přednáška se nekoná – rektorský sportovní den.
20. 5. Zpět k minimálním kostrám (tahák): Zobecněná kontrakce [S4.2], robustní kontrakce a algoritmus pro rozklad na oddíly [S4.2], rozhodovací stromy [S4.3], Pettieho optimální algoritmus [S4.4]. video

Zkoušky

Zkouškové termíny jsou vypsané v SISu. Přihlašte se prosím tam. Kdyby vám žádný termín nevyhovoval, ozvěte se a domluvíme se.

Očekává se znalost a porozumění materiálu z přednášky a schopnost upravovat algoritmy, aby řešily podobné problémy.

Důkazy technických lemmat okolo optimálního algoritmu na minimální kostru nezkouším.

Můžete si přinést tahák na jedné straně formátu A4, který jste si sami vyrobili.

Materiály

Předchozí běhy přednášky:

Literatura:

Stránku spravuje Martin Mareš