From 199e49e4bf21200aa2ba37620694866c0a33328b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 30 Jan 2007 16:49:36 +0100 Subject: [PATCH] Drobne opravy okolo DFS a artikulaci. --- 11-planar/11-planar.tex | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-) diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 8e6f962..1bff6cc 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -26,16 +26,18 @@ Tak s~chut Pøipomeòme si nejprve nìkteré vlastnosti prohledávání do~hloubky (DFS) a jeho pou¾ití k~hledání komponent vrcholové 2-souvislosti {\I (blokù).} -\s{Definice:} Prohledávání do~hloubky rozdìlí $E$ na~ètyøi druhy hran: {\I stromové} (po~nich¾ -DFS pro¹lo a rekurzivnì se zavolalo; tyto hrany vytváøejí {\I DFS strom} orientovaný z~koøene), -{\I zpìtné} (vedou do~vrcholu na~cestì mezi prohledávaným vrcholem a koøenem, +\s{Definice:} Prohledávání grafu (orientovaného nebo neorientovaného) do~hloubky rozdìlí $E$ +na~ètyøi druhy hran: {\I stromové} (po~nich¾ DFS pro¹lo a rekurzivnì se zavolalo; tyto hrany +vytváøejí {\I DFS strom} orientovaný z~koøene), {\I zpìtné} (vedou do~vrcholu na~cestì mezi prohledávaným vrcholem a koøenem, èili do~takového, který se právì nachází na~zásobníku, a~v~tomto smìru si je zorientujeme), {\I dopøedné} (vedou do~ji¾ zpracovaného vrcholu le¾ícího v~DFS stromu pod aktuálním vrcholem) a zbývající {\I pøíèné} (z~tohoto vrcholu do~jiného podstromu). \s{Lemma:} Prohledáváme-li do~hloubky neorientovaný graf, nevzniknou ¾ádné dopøedné ani -pøíèné hrany.\foot{Pro úplnost: v~orientovaném grafu mohou existovat dopøedné -a také pøíèné vedoucí \uv{zprava doleva}, tedy do~døíve nav¹tíveného podstromu.} +pøíèné hrany. V~orientovaném grafu mohou existovat dopøedné +a také pøíèné vedoucí \uv{zprava doleva}, tedy do~døíve nav¹tíveného podstromu. + +Nyní u¾ se zamìøíme pouze na~neorientované grafy~\dots \s{Lemma:} Relace \uv{Hrany $e$ a $f$ le¾í na~spoleèné kru¾nici} (znaèíme $e\sim f$) je ekvivalence. Její tøídy tvoøí maximální 2-souvislé podgrafy (bloky). Vrchol $v$ je artikulace právì tehdy, @@ -60,7 +62,8 @@ Nyn \s{Definice:} Je-li $v$ vrchol grafu, pak: \itemize\ibull \:$\(v)$ udává poøadí, v~nìm¾ DFS do~vrcholu~$v$ vstoupilo. -\:$\(v)$ je nejmen¹í z~\ù vrcholù, do~nich¾ vede z~$v$ zpìtná hrana. +\:$\(v)$ je nejmen¹í z~\ù vrcholù, do~nich¾ vede z~$v$ zpìtná hrana, +nebo $+\infty$, pokud z~$v$ ¾ádná zpìtná hrana nevede. \:$\(v)$ je minimum z~\ù vrcholù le¾ících v~podstromu pod~$v$, vèetnì $v$ samého. \endlist @@ -69,10 +72,11 @@ b Rozpoznávání blokù a artikulací mù¾eme shrnout do~následujícího lemmatu: -\s{Lemma:} -Stromové hrany $uv$ a $vw$ le¾í v~tomté¾ bloku ($uv\sim vw$) právì -tehdy, kdy¾ $\(w) < \(v)$. Vrchol~$v$ je artikulace právì -tehdy, kdy¾ nìkterý z~jeho synù $w$ má $\(w) \ge \(v)$. +\s{Lemma:} Pokud $v$ je vrchol grafu, $u$ jeho otec a $w$ jeho syn v~DFS stromu, +pak stromové hrany $uv$ a $vw$ le¾í v~tomté¾ bloku ($uv\sim vw$) právì +tehdy, kdy¾ $\(w) < \(v)$, a~$v$ je artikulace právì kdy¾ +nìkterý z~jeho synù $w$ má $\(w) \ge \(v)$. +Koøen DFS stromu je artikulace právì kdy¾ má více ne¾ jednoho syna. \h{Postup kreslení} -- 2.39.2