Krajinou grafových algoritmů: Nalezené chyby

Navzdory autorově snažení se i do skriptíček o grafových algoritmech vloudila hrstka nestoudných chyb. V online verzi textu je průběžně opravuji, z tištěné verze je už bohužel nikdo nesmaže. Takže si, prosím, své knížky opravte podle nasledujících řádků.

Pokud víte o jakékoliv další chybě, rád o ní uslyším. Zde jsou uvedeny pouze ty chyby, které ovlivňují smysl textu; chyby povahy jazykové samozřejmě také opravuji, ale jelikož snad nikoho nenachytají, tak je nevyjmenovávám.

Podstatnější chyby

• 3. kapitola, algoritmus na hledání maximálního párování v bipartitních grafech: štěpení stupňů nestačí definovat pro sudě-regulární grafy, nýbrž pro všechny grafy se sudými stupni vrcholů. Samotná úprava algoritmu Degree Split je triviální.
• 10. kapitola: V Ukkonenově algoritmu na konstrukci suffixového stromu je podmínka v krocích 10 a 15 opačně.
• 10. kapitola: V Kärkkäinenově-Sandersově algoritmu na konstrukci suffixového pole je několik drobných chyb. Jelikož byl algoritmus navíc popsán zbytečně složitě, celou sekci o něm pojednávající jsem přepsal.
• 11. kapitola: Rozbor případů v důkazu korektnosti algoritmu na rovinné kreslení je neúplný. Výrazně jsem ho předělal, nakonec je podobnější původnímu článku Boyera a Myrvoldové.

Drobné chybičky

• 1. kapitola, definice sítě: kapacity mohou být i nulové.
• 2. kapitola, část "Jednotkové kapacity": párům opačných hran odpovídají cykly délky 2, nikoliv 1.
• 2. kapitola, algoritmus Tří Indů: poslední krok má posílat do t, nikoliv do s.
• 3. kapitola, algoritmus Nagamochi-Ibaraki: v lemmatu o legálních uspořádání má být "nebo je u_i-1=v_i" namísto "nebo je u_i=v_j, j>i".
• 5. kapitola: V důkazu Lemmatu o swapování se píše, že kružnice nemůže být celá obsažena v T, zatímco správně má být "v T'".
• 5. kapitola: V důkazu Lemmatu o monotónním swapování je zmíněna kružnice T[e']+e namísto správné T[e']+e'.
• 6. kapitola: V analýze 4. verze Jarníkova algoritmu je vhodné explicitně zmínit, že do hran incidentních s podkostrami počítáme i vnitřní hrany mezi vrcholy těchto podkoster (jinak nevyjde analýza o pár řádků níže).
• 6. kapitola, přehled výsledků na konci kapitoly: jsou-li hrany setříděné, přečíslováváme je na 1 až m, nikoliv 1 až n.
• 7. kapitola: v definici VEBT má proměnná k značit log U, nikoliv log log U.
• 8. kapitola, pozorování o tvaru trie: zde jsou trochu zmatené indexy – správně je x₁,…,x_r a c₁,…,c_r-1. Zdůvodnění, proč je třeba používat reprezentaci rozdělenou na B a C, kulhá, ve skutečnosti nemusí být log w=O(k).
• 8. kapitola, Q-haldy: vektory je lepší udržovat s položkami šíře log k namísto log r, protože jinak bychom je museli při operacích s haldou přeformátovávat.
• 8. kapitola, Q-haldy: popis operace Insert by měl explicitně zmiňovat, že po vložení do vektoru B se některé jeho položky posunou, takže je potřeba aktualizovat odkazy na ně z pole C.
• 9. kapitola: Poznámka pod čarou 25 na straně 46 tvrdí, že stejné časové složitosti je možné dosáhnout i v nejhorším případě. To není pravda. Současná verze skriptíček už zmiňuje i příslušný dolní odhad.
• 11. kapitola: Na několika místech argumentujeme tím, že čas potřebný na průchod částí grafu lze naúčtovat vrcholům, které zmizely z vnější stěny. Tento argument nefunguje, přecházíme-li přes artikulaci. Pomůže účtovat čas mizejícím hranám.