From f9265800bdb208e58d890a7b032ea13522bd7d33 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 15 Jan 2024 14:47:45 +0100 Subject: [PATCH] =?utf8?q?Planarita:=20Drobn=C3=A9=20chyby?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 11-planar/11-planar.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 7401c66..97d4e00 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -148,7 +148,7 @@ Jinými slovy platí, že vrchol $w$ je externí při zpracování vrcholu~$v$, nebo pokud pro některého ze~synů $x$ ležícího v~jiném bloku je $\(x) < \(v)$. Druhá podmínka funguje díky tomu, že kořen bloku má v~tomto bloku právě jednoho syna (jinak by existovala příčná hrana, což víme, že není pravda), takže minimum z~\ů -všech vrcholů ležících uvnitř bloku je přesně \ tohoto syna. +všech vrcholů ležících uvnitř bloku a v~podřízených blocích je přesně \ tohoto syna. Ve~statickém grafu by se všechny testy redukovaly na~$\(w)$, nám se ovšem bloková struktura průběžně mění, takže musíme uvažovat bloky v~současném okamžiku. Proto si zavedeme: @@ -363,7 +363,7 @@ $x$ i~$y$. Dokážeme nyní, že uvnitř bloku existuje {\I plot} -- cesta mezi~ a~$y$, jejíž zbývající vrcholy neleží na hranici bloku. Předpokládejme pro spor, že plot neexistuje. Před nakreslením zpětných hran -vedoucích do~$v$ ještě blok~$B$ neexistoval a jeho vrcholy patřily do několika +vedoucích do~$v$ ještě blok~$B$ neexistoval a jeho hrany patřily do několika menších bloků. Speciálně víme, že $w$~byla artikulace oddělující $x$ od~$y$, takže každá cesta mezi~$x$ a~$y$ musela procházet přes~$w$. Proto v~pořadí podle DFS musí ležet~$w$ před aspoň jedním z~vrcholů $x$ a~$y$. Buď~$x$ nebo~$y$ tedy předtím musel @@ -409,7 +409,7 @@ takže je nyní externí. \:Díky {\bf C:} žádný vrchol na dolní cestě není externí. \endlist -Při vstupu~$r_1$ tedy plot vede k~externími vrcholu, zatímco dolní cesta +Při vstupu do~$r_1$ tedy plot vede k~externími vrcholu, zatímco dolní cesta k~internímu. Podle pravidla \#2 si algoritmus musí vybrat dolní cestu, kde ho nic nezastaví, takže dojde až do~$w$ a~nakreslí zpětnou hranu $wv$. To je opět spor. \qed -- 2.39.2