4
Stromy a les
Jedn´ım ze z´ akladn´ıch, a patrnˇe nejjednoduˇsˇs´ım, typem graf˚ u jsou takzvan´e stromy. Jedn´ a se o souvisl´e grafy bez kruˇznic. Pˇres svou (zd´ anlivou) jednoduchost maj´ı stromy bohatou strukturu a pˇredevˇs´ım mnoˇzstv´ı vlastn´ıch aplikac´ı, napˇr´ıklad v datov´ ych struktur´ ach.
s s s s s
s
s
s
s
s s
2
Patrnˇe nejstarˇs´ı motivac´ı pojmu stromu jsou rodokmeny ( po meˇci“), jejichˇz p˚ uvod sah´ a ” daleko pˇred vznik teorie graf˚ u.
Struˇ cn´ y pˇrehled lekce • Definice a z´akladn´ı vlastnosti strom˚ u. • Koˇrenov´e a uspoˇr´adan´e stromy, isomorfismus. • Kostry graf˚ u a jejich poˇcet. Petr Hlinˇen´ y, FI MU Brno
1
FI: MA010: Stromy a les
4.1
Z´ akladn´ı vlastnosti strom˚ u
Definice 4.1. Strom je jednoduch´y souvisl´y graf T bez kruˇznic. Lema 4.2. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1.
2
D˚ ukaz: Souvisl´y graf s v´ıce neˇz jedn´ım vrcholem nem˚ uˇze m´ıt vrchol stupnˇe 0. Proto vezmeme strom T a v nˇem libovoln´y vrchol v. Sestroj´ıme nyn´ı co nejdelˇs´ı sled S v T zaˇc´ınaj´ıc´ı ve v: S zaˇcne libovolnou hranou vych´azej´ıc´ı z v. V kaˇzd´em dalˇs´ım vrchole u, do kter´eho se dostaneme a m´a stupeˇn vˇetˇs´ı neˇz 1, lze pak pokraˇcovat sled S dalˇs´ı novou hranou. Uvˇedomme si, ˇze pokud by se ve sledu S poprv´e zopakoval nˇekter´y vrchol, z´ıskali bychom kruˇznici, coˇz ve stromˇe nelze. Proto sled S mus´ı jednou skonˇcit v nˇejak´em vrcholu stupnˇe 1 v T . 2 2 Vˇ eta 4.3. Strom na n vrcholech m´a pˇresnˇe n − 1 hran pro n ≥ 1.
2
D˚ ukaz: Toto tvrzen´ı dok´aˇzeme indukc´ı podle n. Strom s jedn´ım vrcholem m´a n − 1 = 0 hran. Necht’ T je strom na n > 1 vrcholech. Podle Lematu 4.2 m´a T vrchol v stupnˇe 1. Oznaˇcme T ′ = T − v graf vznikl´y z T odebr´an´ım vrcholu v. Pak T ′ je tak´e souvisl´y bez kruˇznic, tud´ıˇz strom na n − 1 vrcholech. Dle indukˇcn´ıho pˇredpokladu T ′ m´a n − 1 − 1 hran, a proto T m´a n − 1 − 1 + 1 = n − 1 hran. 2 Petr Hlinˇen´ y, FI MU Brno
2
FI: MA010: Stromy a les
Vˇ eta 4.4. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta.
2
D˚ ukaz: Jelikoˇz strom T je souvisl´y dle definice, mezi libovoln´ymi dvˇema vrcholy u, v vede nˇejak´a cesta. Pokud by existovaly dvˇe r˚ uzn´e cesty P1 , P2 mezi u, v, tak bychom vzali jejich symetrick´y rozd´ıl, podgraf H = P1 ∆P2 s nepr´azdnou mnoˇzinou hran, kde H zˇrejmˇe m´a vˇsechny stupnˇe sud´e. Na druhou stranu se vˇsak podgraf stromu mus´ı opˇet skl´adat z komponent strom˚ u, a tud´ıˇz obsahovat vrchol stupnˇe 1 podle Lematu 4.2, 2 spor. Proto cesta mezi u a v existuje jen jedna. 2 D˚ usledek 4.5. Pˇrid´an´ım jedn´e nov´e hrany do stromu vznikne pr´avˇe jedna kruˇznice. D˚ ukaz: Necht’ mezi vrcholy u, v ve stromu T nen´ı hrana. Pˇrid´an´ım hrany e = uv vznikne pr´avˇe jedna kruˇznice z e a jedin´e cesty mezi u, v v T podle Vˇety 4.4. 2 2 Vˇ eta 4.6. Strom je minim´aln´ı souvisl´y graf (na dan´ych vrcholech).
2
D˚ ukaz: Strom je souvisl´y podle definice. Pokud by ale vypuˇstˇen´ım hrany e = uv ze stromu T vznikl opˇet souvisl´y graf, pak by mezi u, v v T existovaly dvˇe cesty (dohromady kruˇznice) – hrana e a jin´a cesta v T −e. To je ve sporu s Vˇetou 4.4. Naopak, pokud by souvisl´y graf mˇel kruˇznici, z˚ ustal by souvisl´y i po vypuˇstˇen´ı nˇekter´e hrany t´e kruˇznice. Proto kaˇzd´y minim´aln´ı souvisl´y graf (na dan´ych vrcholech) je stromem. Tud´ıˇz strom je pr´avˇe minim´aln´ım souvisl´ym grafem na dan´ych vrcholech. 2 Petr Hlinˇen´ y, FI MU Brno
3
FI: MA010: Stromy a les
Pˇr´ıklad 4.7. Kolik nejv´yˇse kruˇznic vznikne v grafu, kter´y vytvoˇr´ıme ze stromu pˇrid´an´ım dvou hran?2 Pˇrid´an´ım jedn´e hrany do stromu T vznikne jedna kruˇznice dle D˚ usledku 4.5. Druh´a hrana vytvoˇr´ı nejm´enˇe jeˇstˇe jednu kruˇznici ze stejn´ych d˚ uvod˚ u, ale m˚ uˇze vytvoˇrit i dvˇe dalˇs´ı kruˇznice, jako tˇreba v n´asleduj´ıc´ım grafu, kde strom T je vyznaˇcen pln´ymi ˇcarami a dvˇe pˇridan´e hrany ˇc´arkovanˇe. s s
s s
Kaˇzd´a z pˇridan´ych dvou hran vytvoˇr´ı vlastn´ı troj´ uheln´ık a nav´ıc jeˇstˇe vznikne kruˇznice d´elky 4 proch´azej´ıc´ı obˇema z pˇridan´ych hran. Na druhou stranu chceme uk´azat, ˇze v´ıce neˇz 3 kruˇznice vzniknout nemohou po pˇrid´an´ı dvou hran e, f do stromu T : Podle D˚ usledku 4.5 vznikne jen jedna kruˇznice proch´azej´ıc´ı hranou e a neobsahuj´ıc´ı f , stejnˇe tak jedna kruˇznice proch´azej´ıc´ı f a neobsahuj´ıc´ı e. Nakonec staˇc´ı nahl´ednout, ˇze je nejv´yˇse jedna moˇzn´a kruˇznice proch´azej´ıc´ı obˇema hranami e, f : Pokud by takov´e byly dvˇe r˚ uzn´e C1 , C2 , pod´ıvali bychom se na jejich symetrick´y rozd´ıl, podgraf H = C1 ∆C2 , kter´y m´a vˇsechny stupnˇe sud´e, nepr´azdnou mnoˇzinu hran a je nav´ıc pografem stromu T . Takˇze stejnˇe jako ve Vˇetˇe 4.4 dost´av´ame spor s faktem, ˇze podgrafy strom˚ u s hranami mus´ı obsahovat vrchol stupnˇe 1. 2 Petr Hlinˇen´ y, FI MU Brno
4
FI: MA010: Stromy a les
4.2
Koˇrenov´ e stromy
Pˇri mnoha aplikac´ıch stromov´ych struktur se ke stromu jako grafu samotn´emu jeˇstˇe v´aˇz´ı dodateˇcn´e informace, jako tˇreba vyznaˇcen´y jeden vrchol, tzv. koˇren stromu, ze kter´eho cel´y strom vyr˚ ust´a“. Typick´ym pˇr´ıkladem jsou r˚ uzn´e (acyklick´e) datov´e struktury, ve ” kter´ych je vyznaˇcen´y vrchol – koˇren, referov´an jako zaˇc´atek“ uloˇzen´ych dat. 2 ” Koˇrenov´e stromy maj´ı tak´e tradiˇcn´ı motivaci v rodokmenech a z toho vych´az´ı jejich bˇeˇzn´a terminologie. Definice 4.8. Koˇrenov´ ym stromem je strom T spolu s vyznaˇcen´ym koˇrenem r ∈ V (T ), zkr´acenˇe dvojice T, r.
2
Pˇr´ıklad koˇrenov´eho stromu je na n´ asleduj´ıc´ım obr´ azku: r
s f s s
s s
s s
s
s
s
s
s
Zaj´ımavost´ı je, ˇze v informatice stromy vˇetˇsinou rostou od koˇrene smˇerem dol˚ u. (Vˇsak tak´e nejsme v biologii. . . ) Petr Hlinˇen´ y, FI MU Brno
5
FI: MA010: Stromy a les
Definice: Mˇejme koˇrenov´y strom T, r a v nˇem vrchol v. Oznaˇcme u souseda v na cestˇe smˇerem ke koˇreni r. Pak je u naz´yv´an rodiˇcem v a v je naz´yv´an potomkem u. 2 Koˇren nem´ a ˇz´ adn´eho rodiˇce.
sfkoˇren “prarodiˇc” s rodiˇc s
s s
s s
potomci s
s
s
s
s
ˇ Casto se tak´e setk´ ate v koˇrenov´ ych stromech s oznaˇcov´ an´ım otec–syn“ m´ısto rodiˇc–potomek. ” My jsme takov´e oznaˇcen´ı nepouˇzili proto, ˇze by (hlavnˇe v zem´ıch na z´ apad od n´ as) mohlo b´ yt povaˇzov´ ano za sexistick´e. 2
Definice: Vrchol stupnˇe 1 v libovoln´em stromu naz´yv´ame listem. Pozor, i koˇren stromu m˚ uˇze b´ yt listem, pokud m´ a stupeˇ n 1, ale obvykle se to tak neˇr´ık´ a. List koˇrenov´eho stromu, kter´ y nen´ı koˇrenem, nem´ a potomky. Petr Hlinˇen´ y, FI MU Brno
6
FI: MA010: Stromy a les
Definice: Centrem stromu T rozum´ıme bud’ vrchol nebo hranu nalezenou v T n´asleduj´ıc´ım postupem: • Pokud m´a strom T jeden vrchol, je to jeho centrum. Pokud m´a strom T dva vrcholy, je jeho centrem hrana spojuj´ıc´ı tyto dva vrcholy. 2 • Jinak vytvoˇr´ıme menˇs´ı strom T ′ ⊂ T vypuˇstˇen´ım vˇsech list˚ u T najednou. Je zˇrejm´e, ˇze T ′ je nepr´azdn´y, a vrac´ıme se na pˇredchoz´ı bod. Z´ıskan´e (rekurzivnˇe) centrum T ′ je z´aroveˇ n centrem T . 2 Pˇr´ıklad 4.9. Ilustrac´ı definice centra jsou n´asleduj´ıc´ı dva postupy nalezen´ı: s
s s s s
s
s s
s
s s
s
s
s
s f
s s
s s
s
s
s
sf
s s
s
s
s
s
s
s
s
s
s
s f
s
s
2
2
Fakt. Pokud chceme dan´emu (abstraktn´ımu) stromu pˇriˇradit jednoznaˇcnˇe koˇren, je nejlepˇs´ı jej pˇriˇradit centru stromu. Speci´alnˇe, pokud je centrem hrana, bude koˇrenem nov´y vrchol rozdˇeluj´ıc´ı“ tuto hranu na dvˇe. ” Petr Hlinˇen´ y, FI MU Brno
7
FI: MA010: Stromy a les
Definice: Koˇrenov´y strom T, r je uspoˇr´adan´y, pokud je pro kaˇzd´y jeho vrchol jednoznaˇcnˇe d´ano poˇrad´ı jeho potomk˚ u (zleva doprava). Uspoˇr´adan´y koˇrenov´y strom se tak´e naz´yv´a pˇestovan´y strom. 2 Uspoˇr´ adan´ y koˇrenov´ y strom si jinak tak´e m˚ uˇzeme pˇredstavit jako strom s vyznaˇcen´ ym koˇrenem a pevnˇe zvolen´ ym nakreslen´ım v rovinˇe bez kˇr´ıˇzen´ı hran. Nakreslen´ı hran potomk˚ u vzhledem k hranˇe rodiˇce pak ud´ av´ a (ve zvolen´e orientaci) poˇrad´ı potomk˚ u.
sfkoˇren s rodiˇc
s
s s
s s
potomci:
1
s
2
s
3
s
4
s
s
Uspoˇr´ ad´ an´ı potomk˚ u vrcholu ve stromu je pˇrirozenˇe poˇzadov´ ano v mnoha praktick´ ych situac´ıch. Napˇr´ıklad ve stromov´ ych datov´ ych struktur´ ach jsou ˇcasto potomci explicitnˇe seˇrazeni podle dan´eho kl´ıˇce, jako tˇreba ve vyhled´ avac´ıch bin´ arn´ıch stromech. I v pˇr´ıpadech, kdy uspoˇr´ ad´ an´ı potomk˚ u ve stromˇe nen´ı d´ ano, je moˇzn´e jej jednoznaˇcnˇe definovat, jak uvid´ıme v n´ asleduj´ıc´ı ˇc´ asti. Petr Hlinˇen´ y, FI MU Brno
8
FI: MA010: Stromy a les
4.3
Isomorfismus strom˚ u
Jelikoˇz stromy jsou speci´aln´ım pˇr´ıpadem graf˚ u, je isomorfismus strom˚ u tot´eˇz co isomorfismus graf˚ u. Avˇsak na rozd´ıl od obecn´ych graf˚ u, kdy je urˇcen´ı isomorfismu tˇeˇzk´y probl´em, pro isomorfismus strom˚ u existuje efektivn´ı postup, kter´y si uk´aˇzeme d´ale. 2 Definice: Dva koˇrenov´e stromy T, r a T ′ , r′ jsou isomorfn´ı pokud existuje isomorfismus mezi stromy T a T ′ , kter´y koˇren r zobrazuje na koˇren r′ . r′ sf
r f s s s s
s
s
s s
s
s
s
s
s 6≃
s
s
s s s
s s
s
2
Definice: Dva uspoˇr´adan´e koˇrenov´e stromy jsou isomorfn´ı pokud je mezi nimi isomorfismus koˇrenov´ych strom˚ u, kter´y nav´ıc zachov´av´a poˇrad´ı potomk˚ u vˇsech vrchol˚ u. r′ s f
r sf s s s
s
s s
s
Petr Hlinˇen´ y, FI MU Brno
s
s
s
s 6≃ 9
s
s
s s s
s s
s
s
FI: MA010: Stromy a les
K´ odov´ an´ı uspoˇr´ adan´ ych koˇrenov´ ych strom˚ u ( z´avorkov´an´ı“ strom˚ u) ” Definice: ( ((()()())()) (()(())) )
s ( (()()()) () ) ( ()()() )
s ( () (()) )
s
s
s (())
s ()
s
s
s
()
()
()
s ()
s ()
K´od uspoˇr´adan´eho koˇrenov´eho stromu se spoˇc´ıt´a rekurzivnˇe z k´ od˚ u vˇsech podstrom˚ u koˇrene, seˇrazen´ych v dan´em poˇrad´ı a uzavˇren´ych do p´aru z´avorek. 2 Pozn´ amka: M´ısto znak˚ u ‘(’ a ‘)’ lze pouˇz´ıt i jin´e symboly, tˇreba ‘0’ a ‘1’.
Lema 4.10. Dva uspoˇr´adan´e koˇrenov´e (pˇestovan´e) stromy jsou isomorfn´ı pr´avˇe kdyˇz jejich k´ ody z´ıskan´e podle pˇredchoz´ıho popisu jsou shodn´e ˇretˇezce. Petr Hlinˇen´ y, FI MU Brno
10
FI: MA010: Stromy a les
Fakt. Je-li d´an k´ od s uspoˇr´adan´eho koˇrenov´eho stromu, pˇr´ısluˇsn´y strom nakresl´ıme n´asleduj´ıc´ım postupem: – Pˇri pˇreˇcten´ı znaku ‘(’ na zaˇc´atku spust´ıme pero na pap´ır, do koˇrene. 2 – Pˇri kaˇzd´em dalˇs´ım pˇreˇcten´ı znaku ‘(’ nakresl´ıme hranu do n´asleduj´ıc´ıho potomka souˇcasn´eho vrcholu. 2 – Pˇri kaˇzd´em pˇreˇcten´ı znaku ‘)’ se perem vr´at´ıme do rodiˇce souˇcasn´eho vrcholu, pˇr´ıpadnˇe zvedneme pero, pokud uˇz jsme v koˇreni. 2 Pˇr´ıklad 4.11. Nakreslete jako pˇestovan´y strom ten odpov´ıdaj´ıc´ı z´avorkov´emu k´ odu ( (()(()()()())) (()()) ) . f s s s s
s s
s
s s
s
s 2
Petr Hlinˇen´ y, FI MU Brno
11
FI: MA010: Stromy a les
Pˇri urˇcov´an´ı isomorfismu obecn´ych strom˚ u pouˇzijeme z´avorkov´y k´ od, pro kter´y koˇren vol´ıme v centru a potomky seˇrad´ıme podle jejich k´ od˚ u vzestupnˇe abecednˇe. Algoritmus 4.12. Urˇ cen´ı isomorfismu dvou strom˚ u. input: stromy T a U ; if (|V (T )|!=|V (U )|) return ’Nejsou isomorfn´ ı.’; (U,s) = korenove centrum(U); (T,r) = korenove centrum(T); k = minimalni kod(T,r); m = minimalni kod(U,s); if (k==m jako ˇretˇezce) return ’Jsou isomorfn´ ı.’; else return ’Nejsou isomorfn´ ı.’; 2 Funkce minimalni kod(strom X, vrchol r) { if (|V (X)|==1) return "()"; d = poˇcet komponent grafu X-r, tj. podstrom˚ u koˇrene r; for (i = 1,...,d) { Y[i] = i-t´a souvisl´a komponenta grafu X-r; s[i] = i-t´y soused r, tj. koˇren podstromu Y[i]; k[i] = minimalni kod(Y[i],s[i]); } sort k[1]<=k[2]<=...<=k[d] lexikograficky (abecednˇe); return "("+k[1]+...+k[d]+")"; } Petr Hlinˇen´ y, FI MU Brno
12
FI: MA010: Stromy a les
D˚ ukaz spr´avnosti Algoritmu 4.12 je pod´an v n´asleduj´ıc´ım tvrzen´ı. Vˇ eta 4.13. Mˇejme dva stromy T, U o stejn´em poˇctu vrchol˚ u a necht’ (T ′ , r) a (U ′ , s) jsou po ˇradˇe jejich koˇrenov´e stromy z´ıskan´e v prvn´ı ˇc´asti Algoritmu 4.12 (kde r, s jsou centra T, U ). Pak plat´ı: a) T a U jsou isomorfn´ı, pr´avˇe kdyˇz (T ′ , r) je isomorfn´ı (U ′ , s). b) (T ′ , r) je isomorfn´ı (U ′ , s), pr´avˇe kdyˇz minimalni kod(T′ , r) = minimalni kod(U′ , s). D˚ ukaz (n´aznak): Tvrzen´ı (a) ihned plyne z jednoznaˇcnosti definice centra stromu. Za druh´e (b) dokazujeme indukc´ı podle hloubky naˇsich koˇrenov´ych strom˚ u T ′ , r a U ′ , s. (Zˇrejmˇe pokud maj´ı r˚ uzn´e hloubky, isomorfn´ı nejsou.) Dva koˇrenov´e stromy hloubky 0 jsou vˇzdy isomorfn´ı a maj´ı shodn´y k´ od ()“. D´ale vezmeme T ′ , r a U ′ , s hloubky ℓ > 0. ” Pokud jejich k´ ody vyjdou shodn´e, jsou isomorfn´ı. Naopak pro isomorfn´ı T ′ , r a U ′ , s existuje bijekce mezi vz´ajemnˇe isomorfn´ımi podstromy jejich koˇren˚ u, tud´ıˇz podle indukˇcn´ıho pˇredpokladu k´ ody tˇechto podstrom˚ u jsou po dvojic´ıch shodn´e. Jelikoˇz se v obou pˇr´ıpadech setˇr´ıd´ı k´ ody podstrom˚ u stejnˇe, vyjde minimalni kod(T′ , r) = minimalni kod(U′ , s). 2
Petr Hlinˇen´ y, FI MU Brno
13
FI: MA010: Stromy a les
4.4
Kostry graf˚ u
Definice 4.14. Kostrou souvisl´eho grafu G je podgraf v G, kter´y je s´am stromem a obsahuje vˇsechny vrcholy grafu G.
2
Pˇr´ıklad 4.15. Kolik r˚ uzn´ych koster m´a tento graf? s
s
s
s
s
s
s
s
s
s
s
Pod´ıvejme se na kostru grafu takto – jak´e hrany z grafu vymaˇzeme, aby zbyl strom? Zajist´e mus´ıme vymazat nˇekterou hranu z prvn´ı kruˇznice (5 moˇznost´ı) a nˇekterou hranu z druh´e kruˇznice (6 moˇznost´ı). Na druhou stranu to v tomto jednoduch´em pˇr´ıkladˇe uˇz staˇc´ı, vˇzdy pak zbude strom. V´ybˇer vymazan´e hrany z prvn´ı kruˇznice je nez´avisl´y na druh´e kruˇznici (jsou disjunktn´ı), a proto dle principu nez´avisl´ych v´ybˇer˚ u m´ame 5·6 = 30 moˇznost´ı vybrat dvˇe hrany k vymaz´an´ı. Celkem tedy vyjde 30 koster. 2
Petr Hlinˇen´ y, FI MU Brno
14
FI: MA010: Stromy a les
N´asleduj´ıc´ı v´ysledek patˇr´ı ke kr´asn´ym drahokam˚ um“ teorie graf˚ u. ” ´ y graf Kn pro n > 0 m´a pˇresnˇe nn−2 koster. Vˇ eta 4.16. (Cayley) Upln´
2
Definice. Laplaceova matice Q = (qij )ni,j=1 grafu G o n vrcholech je definov´ana: – qii = dG (i) (stupeˇn vrcholu), – qij = 0 pro vrcholy i 6= j nespojen´e hranou, – qij = −1 pro vrcholy i 6= j spojen´e hranou.
2
Vˇ eta 4.17. Necht’ Q je Laplaceova matice grafu G a matice Q′ vznikne vyˇskrtnut´ım jej´ıho prvn´ıho ˇr´adku a sloupce. Pak poˇcet koster grafu G je roven determinantu |Q′ |. D˚ ukaz t´eto pˇrekvapiv´e vˇety je mimo dosah naˇsi pˇredn´ aˇsky (vyuˇz´ıv´ a siln´e n´ astroje line´ arn´ı algebry). Uvˇedomte si, proˇc samotn´ a matice Q je singul´ arn´ı (determinantu 0) – nebot’ souˇcet prvk˚ uv kaˇzd´em ˇr´ adku je 0. Je tak´e moˇzno vyˇskrt´ avat jin´e ˇr´ adky a sloupce, ale m˚ uˇze se t´ım zmˇenit znam´enko determinantu.
Petr Hlinˇen´ y, FI MU Brno
15
FI: MA010: Stromy a les
