From a058b2f934be8234a8368c58ff73576ccd0f8ab3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 30 May 2007 13:18:48 +0200 Subject: [PATCH] Odstraneno pozorovani o mostech, ktere neplatilo. --- 8-grafy/8-grafy.tex | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) diff --git a/8-grafy/8-grafy.tex b/8-grafy/8-grafy.tex index 4432002..0d01a50 100644 --- a/8-grafy/8-grafy.tex +++ b/8-grafy/8-grafy.tex @@ -189,18 +189,16 @@ meta-algoritmu, tedy $O(n + m)$. Tuto aplikaci si teï rozebereme tro¹ku podrobnìji. Nejprve v¹ak nìkolik definic. -\s{Definice:} Artikulace je vrchol v grafu, jeho¾ odebráním se graf rozpadne na alespoò +\s{Definice:} {\I Artikulace} je vrchol v grafu, jeho¾ odebráním se graf rozpadne na alespoò dvì komponenty souvislosti. -\s{Definice:} Most je hrana v grafu, jejím¾ odebráním se graf rozpadne na dvì +\s{Definice:} {\I Most} je hrana v grafu, jejím¾ odebráním se graf rozpadne na dvì komponenty souvislosti. -\s{Pozorování}: Most je taková hrana, její¾ oba koncové vrcholy jsou artikulacemi. - -\s{Definice:} Graf je 2-souvislý, jestli¾e po odstranìní libovolného vrcholu +\s{Definice:} Graf je {\I 2-souvislý,} jestli¾e po odstranìní libovolného vrcholu zùstane souvislý. -\s{Definice:} 2-souvislá komponenta je maximální 2-souvislý podgraf. +\s{Definice:} {\I 2-souvislá komponenta} je maximální 2-souvislý podgraf. Jak bychom tedy pøi hledání artikulací v grafu mohli postupovat? Jako první se nabízí tento algoritmus: -- 2.39.2