$
'
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 e DD e e eDD s s LL LLs s @ @ @ @ s
&Petr Hlinˇen´y,
FI MU Brno
1
s
FI: MA010: Stromy a les
%
$
'
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 e DD e e eDD s s LL LLs s @ @ @ @ s
s
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.
&Petr Hlinˇen´y,
FI MU Brno
2
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. 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 .
&Petr Hlinˇen´y,
FI MU Brno
2
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. 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 2 vrcholu stupnˇe 1 v T . Vˇ eta 4.3. Strom na n vrcholech m´a pˇresnˇe n − 1 hran pro n ≥ 1.
&Petr Hlinˇen´y,
FI MU Brno
2
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. 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 2 vrcholu stupnˇe 1 v T . Vˇ eta 4.3. Strom na n vrcholech m´a pˇresnˇe n − 1 hran pro n ≥ 1. 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 0 = T − v graf vznikl´y z T odebr´an´ım vrcholu v. Pak T 0 je tak´e souvisl´y bez kruˇznic, tud´ıˇz strom na n − 1 vrcholech. Dle indukˇcn´ıho pˇredpokladu T 0 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.
&Petr Hlinˇen´y,
FI MU Brno
3
FI: MA010: Stromy a les
%
$
' Vˇ eta 4.4. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta. 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, spor. Proto cesta mezi u a v existuje jen jedna.
&Petr Hlinˇen´y,
FI MU Brno
3
FI: MA010: Stromy a les
%
$
' Vˇ eta 4.4. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta. 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. 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.
&Petr Hlinˇen´y,
FI MU Brno
3
FI: MA010: Stromy a les
%
$
' Vˇ eta 4.4. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta. 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. 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 2 vznikne pr´avˇe jedna kruˇznice z e a jedin´e cesty mezi u, v v T podle Vˇety 4.4. Vˇ eta 4.6. Strom je minim´aln´ı souvisl´y graf (na dan´ych vrcholech).
&Petr Hlinˇen´y,
FI MU Brno
3
FI: MA010: Stromy a les
%
$
' Vˇ eta 4.4. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta. 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. 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 2 vznikne pr´avˇe jedna kruˇznice z e a jedin´e cesty mezi u, v v T podle Vˇety 4.4. Vˇ eta 4.6. Strom je minim´aln´ı souvisl´y graf (na dan´ych vrcholech). 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?
&Petr Hlinˇen´y,
FI MU Brno
4
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? 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. ”
&Petr Hlinˇen´y,
FI MU Brno
5
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. ” 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.
&Petr Hlinˇen´y,
FI MU Brno
5
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. ” 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. Pˇr´ıklad koˇrenov´eho stromu je na n´ asleduj´ıc´ım obr´ azku: r
s f @ s @s @ @ s @s @s a @aaaa s @ s s @s aas @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.
&Petr Hlinˇen´y,
FI MU Brno
6
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. Koˇren nem´ a ˇz´ adn´eho rodiˇce. koˇren
s f @ @ “prarodiˇc” @ s @s @ @ @ @ rodiˇc @ @ s s @ @s a a a @ @ s a @ aa @ @ @s aas @s s s @ potomci ˇ 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.
&Petr Hlinˇen´y,
FI MU Brno
6
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. Koˇren nem´ a ˇz´ adn´eho rodiˇce. koˇren
s f @ @ “prarodiˇc” @ s @s @ @ @ @ rodiˇc @ @ s s @ @s a a a @ @ s a @ aa @ @ @s aas @s s s @ potomci ˇ 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.
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.
&Petr Hlinˇen´y,
FI MU Brno
7
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. • Jinak vytvoˇr´ıme menˇs´ı strom T 0 ⊂ T vypuˇstˇen´ım vˇsech list˚ u T najednou. Je zˇrejm´e, ˇze T 0 je nepr´azdn´y, a vrac´ıme se na pˇredchoz´ı bod. Z´ıskan´e (rekurzivnˇe) centrum T 0 je z´aroveˇ n centrem T .
&Petr Hlinˇen´y,
FI MU Brno
7
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. • Jinak vytvoˇr´ıme menˇs´ı strom T 0 ⊂ T vypuˇstˇen´ım vˇsech list˚ u T najednou. Je zˇrejm´e, ˇze T 0 je nepr´azdn´y, a vrac´ıme se na pˇredchoz´ı bod. Z´ıskan´e (rekurzivnˇe) centrum T 0 je z´aroveˇ n centrem T . Pˇr´ıklad 4.9. Ilustrac´ı definice centra jsou n´asleduj´ıc´ı dva postupy nalezen´ı: s s sQQs s @s s s a aa s s s @s as s s @s s @s @s s s s s@s
&Petr Hlinˇen´y,
FI MU Brno
s sQQs
s
7
s @s s
s
s
s
sf
s f f s
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. • Jinak vytvoˇr´ıme menˇs´ı strom T 0 ⊂ T vypuˇstˇen´ım vˇsech list˚ u T najednou. Je zˇrejm´e, ˇze T 0 je nepr´azdn´y, a vrac´ıme se na pˇredchoz´ı bod. Z´ıskan´e (rekurzivnˇe) centrum T 0 je z´aroveˇ n centrem T . Pˇr´ıklad 4.9. Ilustrac´ı definice centra jsou n´asleduj´ıc´ı dva postupy nalezen´ı: s s sQQs s @s s s a aa s s s @s as s s @s s @s @s s s s s@s
s sQQs
s
s @s s
s
s
s
sf
s f f s 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. ” 7 FI: MA010: Stromy a les &Petr Hlinˇen´y, FI MU Brno
%
$
' 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.
&Petr Hlinˇen´y,
FI MU Brno
8
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. 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.
potomci:
1
f s koˇren @ @ @ s @s @ @ @ @ rodiˇc @ @ sa @s @s a a @ @ s a @ aa @ @ s s @ @s @s aas 2
3
4
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.
&Petr Hlinˇen´y,
FI MU Brno
9
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. Definice: Dva koˇrenov´e stromy T, r a T 0 , r0 jsou isomorfn´ı pokud existuje isomorfismus mezi stromy T a T 0 , kter´y koˇren r zobrazuje na koˇren r0 . r s f @ @s s @ @ @ @s s s a asaas s s @ s @
&Petr Hlinˇen´y,
FI MU Brno
6'
9
r0 sX f X X AA Xs @ @s A s As a @ s@s a @saas s s @
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. Definice: Dva koˇrenov´e stromy T, r a T 0 , r0 jsou isomorfn´ı pokud existuje isomorfismus mezi stromy T a T 0 , kter´y koˇren r zobrazuje na koˇren r0 . r s f @ @s s @ @ @ @s s s a asaas s s @ s @
6'
r0 sX f X X AA Xs @ @s A s As a @ s@s a @saas s s @
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 f s s @ @s @ sa @ @s @s @aa s s s @s as &Petr Hlinˇen´y,
FI MU Brno
6' 9
r0 s f @ s @s @ s s @s s s s sQQs 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.
&Petr Hlinˇen´y,
FI MU Brno
10
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. 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.
&Petr Hlinˇen´y,
FI MU Brno
11
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. – 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.
&Petr Hlinˇen´y,
FI MU Brno
11
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. – 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. – 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.
&Petr Hlinˇen´y,
FI MU Brno
11
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. – 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. – 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. Pˇr´ıklad 4.11. Nakreslete jako pˇestovan´y strom ten odpov´ıdaj´ıc´ı z´avorkov´emu k´odu ( (()(()()()())) (()()) ) . sf H HHH HH s Hs @ A AA @ @ s A s s @s !!AHHH ! ! AA HH !! As HHs ! 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´ ı.’;
&Petr Hlinˇen´y,
FI MU Brno
12
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´ ı.’; 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 0 , r) a (U 0 , 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 0 , r) je isomorfn´ı (U 0 , s). b) (T 0 , r) je isomorfn´ı (U 0 , s), pr´avˇe kdyˇz minimalni kod(T0 , r) = minimalni kod(U0 , 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 0 , r a U 0 , 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 0 , r a U 0 , s hloubky ` > 0. ” Pokud jejich k´ ody vyjdou shodn´e, jsou isomorfn´ı. Naopak pro isomorfn´ı T 0 , r a U 0 , 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(T0 , r) = minimalni kod(U0 , 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.
&Petr Hlinˇen´y,
FI MU Brno
14
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. Pˇr´ıklad 4.15. Kolik r˚ uzn´ych koster m´a tento graf? s s B B B B Bs s s
s s
s
s J J J J s Js
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´
&Petr Hlinˇen´y,
FI MU Brno
15
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´ 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.
&Petr Hlinˇen´y,
FI MU Brno
15
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´ 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. Vˇ eta 4.17. Necht’ Q je Laplaceova matice grafu G a matice Q0 vznikne vyˇskrtnut´ım jej´ıho prvn´ıho ˇr´adku a sloupce. Pak poˇcet koster grafu G je roven determinantu |Q0 |. 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
%
