4   Stromy a les
Jedn ím ze zakladn ich, a patrne nejjednodušš ím, typem grafu jsou takzvane stromy. Jedna se o souvisle grafy bez kruZnic. Pres svou (zdanlivou) jednoduchost maj í stromy bohatou strukturu a predevsím mnozstv í vlastn ich aplikac í, napríklad v datových strukturach.
Patrne nejstarsí motivac í pojmu stromu jsou rodokmeny („po meci"), jejichz puvod saha daleko pred vznik teorie grafu.
Stručný přehled lekce
• Definice a základní vlastnosti stromů.
• Korenove a ůsporádane stromy, isomorfismus.
• Kostry grafů a jejich poCet.
Petr Hliněný,  FI MU Brno_1_
-I: MA010: Stromý a les
4.1   Základní vlastnosti stromů
Definice 4.1. Strom je jednoduchý souvislý graf T bez kružníc.
Lema 4.2. Strom s více než jedním vrcholem obsahuje vrchol stupně 1. □
Důkaz: Souvislý graf s více než jedním vrcholem nemUže mít vrchol stupne 0. Proto vezmeme strom T a v nem libovolný vrchol v. Sestrojíme nýní co nejdelsí sled S v T začínající ve v:
S zacne libovolnou hranou výchazející z v. V každem dalsím vrchole u, do ktereho se dostaneme a ma stupen vetsí nez 1, lze pak pokračovat sled S dalsí novou hranou. Uvedomme si, ze pokud bý se ve sledu S poprve zopakoval nekterý vrchol, získali býchom kruznici, coz ve strome nelze. Proto sled S musí jednou skoncit v nejakem vrcholu stupne 1 v T. □ □
Veta 4.3. Strom na n vrcholech ma presne n — 1 hran pro n > 1. □
Důkaz: Toto tvrzení dokazeme indukcí podle n. Strom s jedním vrcholem ma n — 1 = 0 hran.
Necht T je strom na n > 1 vrcholech. Podle Lematu 4.2 ma T vrchol v stupne 1. Oznacme T' = T — v graf vzniklý z T odebraním vrcholu v. Pak T' je take souvislý bez kruznic, tudíz strom na n — 1 vrcholech. Dle indukcního predpokladu T' ma n — 1 — 1 hran, a proto T ma n — 1 — 1 + 1 = n — 1 hran. □
Petr Hliněný,  FI MU Brno_2_FI: MA010: Stromy a les
Věta 4.4. Mezi každými dvěma vrcholy stromu vede právě jediná cesta, □
Důkaz: Jelikož strom T je souvislý dle definice, mezi libovolnými dvema vrcholy u, v vede nejaka cesta. Pokud by existovaly dve rUzne cesty Pi,P2 mezi u, v, tak bychom vzali jejich symetricky rozd íl, podgraf H = P\ AP2 s neprázdnou množinou hran, kde H zrejme ma vsechny stupne sude. Na druhou stranu se vsak podgraf stromu musí opet skladat z komponent stromu, a tudíz obsahovat vrchol stupne 1 podle Lematu 4.2, spor. Proto cesta mezi u a v existuje jen jedna. □ □
Důslěděk 4.5. Přidáním jedné nove hrany do stromu vznikne právě jedna kružnice.
Důkaz: Nechť mezi vrcholy u, v ve stromu T není hrana. Pridaním hrany e = uv vznikne prave jedna kruznice z e a jedine cesty mezi u, v v T podle Vety 4.4. □ □
Věta 4.6. Strom je minimalnísouvislý graf (na daných vrcholech). □
Důkaz: Strom je souvisly podle definice. Pokud by ale vypustením hrany e = uv ze stromu T vznikl opet souvisly graf, pak by mezi u, v v T existovaly dve cesty (dohromady kruznice) - hrana e a jina cesta v T—e. To je ve sporu s Vetou 4.4. Naopak, pokud by souvisly graf mel kruznici, zustal by souvisly i po vypustení nektere hrany te kruznice. Proto kazdy minimaln í souvisly graf (na danych vrcholech) je stromem. Tud íz strom je prave minimaln ím souvislym grafem na danych vrcholech. □
V
Petr Hliněný,  FI MU Brno
: MA010: Stromy a les
Příklad 4.7. Kolik nejvýše kružnic vznikne v grafu, který vytvoříme ze stromu přidáním dvou hran?L
Přidáním jedne hrany do stromu T vznikne jedna kružnice dle Důsledku 4.5. Druha hrana vytvoří nejmene jeSte jednu kružnici ze stejných duvodu, ale muže vytvořit i dve dalSí kružnice, jako třeba v nasledujícím grafu, kde strom T je vyznaCen plnými Čarami a dve pridane hrany cárkovaně.
Kazda z pridanych dvou hran vytvoří vlastní trojuhelník a navíc jeste vznikne kružnice delky 4 prochazející obema z přidanych hran.
Na druhou stranu chceme ukazat, že více než 3 kružnice vzniknout nemohou po přidaní dvou hran e, f do stromu T: Podle Dusledku 4.5 vznikne jen jedna kružnice prochazející hranou e a neobsahuj íc í f, stejne tak jedna kružnice prochazej íc í f a neobsahuj íc í e. Nakonec stařc í nahlednout, řze je nejvyřse jedna mořzna kruřznice prochazej íc í obřema hranami e, f: Pokud by takove byly dve ruzne Ci,C2, pod ívali bychom se na jejich
symetricky rozd íl, podgraf H = CiAC2, ktery ma vsechny stupne sude, neprazdnou
množinu hran a je navíc pografem stromu T. Takže stejne jako ve Vete 4.4 dostavame
spor s faktem, že podgrafy stromu s hranami musí obsahovat vrchol stupne 1.
□
V
Petr Hliněný,  FI MU Brno
: MA010: Stromý a les
4.2   Kořenové stromy
Při mnoha aplikacích stromových struktur se ke stromu jako grafu samotnému ještě váží dodatečné informace, jako treba výžnacený jeden vrchol, tžv. kořen stromu, že kterého celý strom „výrusta". Typickým příkladem jsou mžne (acýklicke) datove struktury, ve kterých je výžnacený vrchol - koren, referovan jako „žacatek" uložených dat. c
Kořenove stromý mají take tradicní motivaci v rodokmenech a ž toho výchaží jejich bežní terminologie.
Definice 4.8. Kořenovým stromem je strom T
spolu s výžnaceným kořenem r G V (T), žkracene dvojice T, r. c
Příklad kořenového stromu je na následujícím obrázku:
Zajímavostí je, že v informatice stromy většinou rostou od kořene směrem dolů. (Však také nejsme v biologii. . .)
Petr Hliněný,  FI MU Brno
-I: MA010: Stromý a les
r
Definice: Mějme kořenový strom T, r a v něm vrchol v. Označme u souseda v na cestě směrem ke kořeni r. Pak je u nazýván rodičem v a v je nazýván potomkem u. c
Koren nema žádného rodiče.
kořen
"prarodič"
potomci *
Často se také setkáte v kořenových stromech s označováním „otec-syn" místo rodič-potomek. My jsme takove ožnacení nepoužili proto, že by (hlavne v žemích na žapad od nas) mohlo být považovano ža sexisticke. c
Definice: Vrchol stupne 1 v libovolnem stromu nazývame listem.
Požor, i koren stromu muže být listem, pokud ma stupeň 1, ale obvykle se to tak neríka. List korenoveho stromu, ktery není korenem, nema potomky.
Petr Hliněný,  FI MU Brno
-I: MA010: Stromy a les
Definice: Centrem stromu T rozumíme buď vrchol nebo hranu nalezenou v T následujícím postupem:
• Pokud má strom T jeden vrchol, je to jeho centrum. Pokud má strom T dva vrcholy, je jeho centrem hrana spojuj íc í tyto dva vrcholy. c
• Jinak vytvoříme mensí strom T' C T vypustením vsech listu T najednou. Je zrejme, Ze T' je neprazdny, a vracíme se na předchozí bod. Získane (rekurzivne) centrum T' je zaroven centrem T. c
Příklad 4.9. Ilustrací definice centra jsou následující dva postupy nalezení
□
Fakt. Pokud chceme danemu (abstraktnímu) stromu přiřadit jednoznacne kořen, je nejlepsí jej přiřadit centru stromu. Specialne, pokud je centrem hrana, bude kořenem novy vrchol „rozdelující" tuto hranu na dve.
Petr Hliněný,  FI MU Brno_7_FI: MA010: Stromy a les
t
Definice: Kořenový strom T, r je uspořádaný, pokud je pro každý jeho vrchol jednoznačně dáno pořadí jeho potomkU (zleva doprava). Uspořádaný kořenový strom se take nazýva pěstovaný střom. c
Uspořádaný kořenový strom si jinak take můžeme představit jako strom s vyznačeným kořenem a pevne zvoleným nakreslen ím v rovine bez křížen í hran. Nakreslen í hran potomků vzhledem k hrane rodiče pak ůdava (ve zvolene orientaci) pořad í potomků.
kořen
potomci:   12 3 4
Uspořadan í potomků vrcholů ve stromů je přirozene pozadovano v mnoha praktických sitůac ích. Například ve stromových datových strůktůrach jsoů casto potomci explicitne seřazeni podle daneho kl íce, jako třeba ve výhledavac ích binarn ích stromech. I v případech, kdý ůspořadan í potomků ve strome nen í dano, je mozne jej jednoznacne definovat, jak ůvid íme v nasledůj íc í casti.
Petr Hliněný,  FI MU Brno
-I: MA010: Stromý a les
4.3   Isomorfismus stromů
Jelikož stromy jsou speciálním případem grafu, je isomorfismus stromu totéž co isomorfismus grafu. Avsak na roždíl od obecných grafu, kdy je urcení isomorfismu težky problem, pro isomorfismus stromu existuje efektivní postup, který si ukažeme dale. c
Definice: Dva kořenove stromy T, r a T', r' jsou isomorfní pokud existuje isomorfismus meži stromy T a T', který koren r žobražuje na koren r'.
r'
Definice: Dva usporadane kořenove stromy jsou isomorfní pokud je meži nimi isomorfismus kořenovych stromu, ktery navíc žachovava pořadí potomku vsech vrcholu.
9*
r'
Petr Hliněný,  FI MU Brno
I: MA010: Stromý a les
r
r
Kódování uspořádaných kořenových stromu („zavorkování" stromu) Defnice:
( ((()()())()) (()(())) )
( (()()()) () )
( ()()() )
()    () ()
()
()
Kód uspořadaneho korenoveho stromu se spočítá rekurzivne z kodU vsech podstromu kořene, serazených v danem pořadí a uzavrených do páru zavorek. c
Poznámka: Místo žnaku '(' a ')' lže použít i jine symboly, treba '0' a '1'.
Lema 4.10. Dva uspořádané kořenové (pestovane) stromy jsou isomorfní právě kdyZ jejich kody získane podle předchozího popisu jsou shodne řetězce.
Petr Hliněný,  FI MU Brr
I: MA010: Stromý a les
Fakt. J e-1 i dán kód s uspořádaného kořenového stromu, příslušný strom nakresl íme následuj ícím postupem:
- Při přečten í znaku '(' na zaCátku spust íme pero na pap ír, do kořene. c
- Při kaZdem dalsím preCten í znaku '(' nakresl íme hranu do nasleduj íc ího potomka souCasneho vrcholu. c
- Při kaZdem preCten í znaku ')' se perem vrat íme do rodiCe souCasneho vrcholu, prípadne zvedneme pero, pokud uz jsme v koreni. c
Příklad 4.11. Nakreslete jako pěstovaný strom ten odpovídající závorkovému kodu
((()(()()()()))(()())) -
•
□
V
Petr Hliněný,  FI MU Brr
I: MA010: Stromy a les
Při určovaní isomorfismu obecných stromU použijeme zavorkový kod, pro který kořen volíme v centru a potomký seradíme podle jejich kodU vzestupne abecedne.
Algoritmus 4.12. UrCení isomorfismu dvou stromu.
input: střomý T a U;
if (|V(T)|!=|V(U)|) return 'Nejsou isomorfní.';
(T,r) = korenove_centrum(T);      (U,s) = korenove_centrum(U);
if (k==m jako řetězce) return 'Jsou isomorfní.'; else return 'Nejsou isomorfní.'; c
Funkce minimální Jkod(strom X, vrchol r) { if (|V(X)|==1) return "O";
d = poCět komponent grafu X-r, tj. podstromU kořene r; for (i = 1,...,d) {
Y[i] =  i-ta souvisla komponenta grafu X-r;
s[i] =  i-tý soused r, tj. kořen podstromu Y[i];
k[i] = minimálniJkod(Y [i] ,s[i]);
sort k[1]<=k[2]<=...<=k[d] lexikografický (abecedne); return "("+k[1]+...+k[d]+")";
k = minimálniJkod(T,r);
m = minimálniJkod(U,s);
}
}
Petr Hliněný,  FI MU Brr
I: MA010: Stromý a les
Dukaz spravnosti Algoritmu 4.12 je podan v nasledujícím tvrzení.
Veta 4.13. Mejme dva stromy T, U o stejném poctu vrcholu a necht: (Tr) a (Us) jsou po řadě jejich kořenove stromy získane v první casti Algoritmu 4.12 (kde r, s jsou centra T, U). Pak platí:
a) T a U jsou isomorfní, prave kdyZ (T',r) je isomorfní (Us).
b) (T',r) je isomorfní(Us), prave kdyZ minimálniJkod(T', r) = minimálniJkod(U', s).
Důkaz (naznak): Tvrzení (a) ihned plyne z jednoznačnosti definice centra stromu.
Za druhe (b) dokazujeme indukcí podle hloubky nasich kořenových stromu Tr a Us. (Zrejme pokud mají mzne hloubky, isomorfní nejsou.) Dva kořenove stromy hloubky 0 jsou vzdy isomorfn í a maj í shodny kod „()". Dale vezmeme Tr a Us hloubky l > 0. Pokud jejich kody vyjdou shodne, jsou isomorfn í.
Naopak pro isomorfn í Tr a Us existuje bijekce mezi vzajemne isomorfn ími podstromy jejich korenu, tudíz podle indukcního předpokladu kody techto podstromu jsou po dvojicích shodne. Jelikoz se v obou případech setřídí kody podstromu stejne, vyjde
minimalniJkod(T', r) = minimalniJkod(U', s). □
Petr Hliněný,  FI MU Brr
I: MA010: Stromy a les
4.4   Kostry grafů
Definice 4.14. Kostrou souvislého grafu G
je podgraf v G, který jé sam stromem a obsahuje vSechny vrcholy grafu G. c Příklad 4.15. Kolik různých koster ma tento graf?
Podívejme se na kostru grafu takto - jake hrany z grafu vymažeme, aby zbyl strom? Zajiste musíme vymazat některou hranu z první kružnice (5 možností) a nekterou hranu z druhe kruznice (6 mozností). Na druhou stranu to v tomto jednoduchem příklade uz stací, vzdy pak zbude strom. Vyber vymazane hrany z první kruznice je nezavisly na druhe kruznici (jsou disjunktní), a proto dle principu nezavislych vyberu mame 5-6 = 30 mozností vybrat dve hrany k vymazaní. Celkem tedy vyjde 30 koster. □
•
V
Petr Hliněný,  FI MU Brr
I: MA010: Stromy a les
Následující výsledek patří ke „krásným drahokamům" teorie grafů. Věta 4.16. (Cayley) Úplný graf Kn pro n > 0 ma přesně nn-2 koster. Definice. Laplaceova matice Q = (qijYnj=\ grafu G o n vrcholech je definována:
- qii = dG(i) (stupen vrcholu),
- qij = 0 pro vrcholy i = j nespojene hranou,
- qij = —1 Pro vrcholy i = j spojene hranou. c
Věta 4.17. Necht. Q je Laplaceova matice grafu G a matice Q' vznikne výěkrtnutím jejího prvního ěádku a sloupce. Pak pocet koster grafu G je roven determinantu |Q'|.
Důkaz teto překvapivé vety je mimo dosah nasi přednášky (využívá silné nástroje lineární algebry).
Uvedomte si, proc samotná matice Q je singulární (determinantů 0) - nebol: součet prvků v každem rádku je 0.
Je take možno vyskrtávat jine rádky a sloupce, ale může se tám zmenit znamenko determinantů.
Petr Hliněný,  FI MU Brr
I: MA010: Stromy a les