From 9fd5e74a25827153e953cd6f3451eafd660d7e10 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 16 Jan 2007 17:26:53 +0100 Subject: [PATCH] Doplnena orientace DFS stromu. --- 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 71b2f4c..120d0d3 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -29,9 +29,9 @@ k~hled \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, -èili do~takového, který se právì nachází na~zásobníku), {\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). +è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é -- 2.39.2