Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace PB165 ­ Grafy a sítě Stromy 24. září 2007 PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Obsah přednášky 1 Kružnice a cykly 2 Stromy a jejich vlastnosti 3 Kořenové stromy 4 Binární stromy, reprezentace PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Kružnice a cyklus v grafu Definice Kružnice (uzavřená cesta) v grafu je netriviální neorientovaná cesta, jež začíná i končí ve stejném vrcholu. Cyklus je orientovaná (z orientovaných hran složená) kružnice respektující orientaci těchto hran. Cyklus je tedy vždy kružnicí, ale každá kružnice nemusí být vždy cyklem. Krom zákazu opakování vrcholů (vyjma shodnosti prvního a posledního) je důležitý i zákaz opakování hran ­ jinak by kružnicí mohl být sled u, e, v, e, u. Zákaz opakování vrcholů znemožňuje využít násobných hran multigrafu s výjimkou kružnice na 2 vrcholech. Samostatný vrchol, který je cestou, za cyklus nepovažujeme. Graf, který obsahuje cyklus, se nazývá cyklický. Pokud graf cyklus neobsahuje, nazýváme jej acyklický. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Kružnice v grafu ­ příklady V Internetu existuje mnoho redundantních linek ­ graf jeho fyzického propojení je cyklický. Lokální ethernetové sítě mají acyklickou topologii. Sítě založené na technologii Token Ring mají logickou kruhovou topologii. Sítě SONET podporují zapojení do kruhu. Obrázek: Levý graf je cyklický, pravý acyklický PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Cyklické hrany Definice Pokud je hrana v grafu součástí nějakého cyklu, nazývá se cyklická. Věta Odstraníme-li ze souvislého grafu G hranu e, vzniklý graf G - e bude souvislý právě tehdy když e je cyklická. Důkaz. Před odstraněním hrany je (z definice) každý vrchol grafu G dosažitelný z každého jiného vrcholu. Nechť hrana e spojuje vrcholy u, v. Po jejím odstranění je každý vrchol grafu G dosažitelný z vrcholu u nebo v (tedy může i z o obou). Graf se tak rozpadne nejvýše na 2 souvislé podgrafy ­ komponenty souvislosti. Právě tehdy, když existuje cyklus, jehož je e součástí, existuje cesta mezi u a v, která neprochází hranou e. Graf G - e je souvislý právě tehdy, když existuje cesta mezi u a v neobsahující hranu e. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Cyklické hrany ­ příklady Obrázek: Cyklické hrany jsou označeny zeleně, ostatní, které způsobí rozpad grafu, červeně. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Topologie sítě CESNET PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Topologie sítě GÉANT PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Stromy Definice Les je graf, který neobsahuje kružnice. Strom je graf, který neobsahuje kružnice a je souvislý. Strom je tedy souvislý les. Lokální ethernetová síť má topografii stromu, protože je souvislá a acyklická. Obrázek: Jednoduchý příklad stromu PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Vlastnosti stromů Následující věta má význam zejména pro důkazy vět dalších: Věta Každý strom s alespoň 1 hranou obsahuje nejméně 2 vrcholy stupně 1. Důkaz. Jelikož cest v konečném grafu je konečně mnoho, existuje mezi nimi vždy nejdelší cesta ­ tedy taková, která prochází nejvíce hranami. Pokud některý z jejích koncových vrcholů má stupeň vyšší než 1, vede z něj hrana, která není součástí této cesty. Pokud tato hrana vede do vrcholu, který je součástí cesty, existuje v grafu cyklus a ten tedy není stromem. Vede-li tato hrana do vrcholu, který součástí cesty není, dá se tato cesta prodloužit a není tudíž nejdelší. V obou případech tak docházíme ke sporu. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Počet hran stromů Důsledkem předchozí věty je, že každý graf, jehož všechny vrcholy jsou stupně alespoň 2, obsahuje kružnici. Věta Strom s n vrcholy obsahuje právě n - 1 hran. Důkaz. Indukcí: triviální strom s 1 vrcholem neobsahuje žádnou hranu. Předpokládáme, že tvrzení platí pro strom s k vrcholy. Uvažujme strom G s k + 1 vrcholy a jeho vrchol v stupně 1. Odebráním vrcholu v a jemu incidentní hrany vznikne graf G - v. Jelikož v je stupně 1, zůstává graf G - v souvislý. Odebrání vrcholu z grafu do něj nemůže nijak vnést cyklus. Graf G - v je tedy souvislý a acyklický, je tedy stromem s k vrcholy. Odebrání v z G odstranilo právě 1 hranu, G má tedy k hran. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Počet hran lesu Žádná hrana ve stromě není cyklická. Odstranění libovolné hrany tedy způsobí rozpad na 2 komponenty souvislosti. Jelikož z každého souvislého grafu lze odebírat hrany dokud není stromem, je k - 1 zároveň dolní hranicí pro počet hran libovolného souvislého grafu s k vrcholy. Větu dokázanou na předchozí straně lze aplikovat i na lesy. Jeho komponenty souvislosti jsou stromy. Pro každou komponentu je třeba od počtu jejích vrcholů odečíst 1 hranu. Věta Les o n vrcholech a k komponentách má n - k hran. Obrázek: Les, jež se skládá z 8 vrcholů, 3 komponent a 5 hran. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Další vlastnosti stromů Věta Mezi každými 2 vrcholy ve stromu vede právě jedna cesta. Důkaz. Uvažujme, že mezi některými 2 vrcholy vedou 2 cesty. Potom je lze rozdělit na 3 části: společný počátek, rozdílná část a společný konec. Nechť u je první vrchol na těchto cestách, kterým se cesty rozdělují, a v je první vrchol, kterým se opětovně spojují. Potom rozdílné úseky cest mezi vrcholy u a v tvoří kružnici a graf tedy není stromem, což je spor. Obrázek: Zeleně je vyznačena přidávaná hrana, červeně existující cyklus v grafu. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Další vlastnosti stromů Důsledkem jedinečnosti cest mezi vrcholy stromu je následující věta: Věta Přidáním libovolné hrany do stromu vznikne právě jedna kružnice. Důkaz. Nechť přidaná hrana e spojuje vrcholy u, v. Mezi nimi již vede právě jedna cesta. Přidáním hrany e vznikne cesta druhá, tedy i kružnice. Zbývá dokázat, že vznikne nejvýše jedna kružnice: každá vzniknuvší kružnice bude procházat hranou e. Pokud by jí procházely 2 kružnice, musely by ještě před přidáním hrany e existovat 2 různé cesty mezi u a v, tedy i kružnice, a graf by tak nebyl stromem. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Stromy a jejich vlastnosti ­ cvičení 1 Nakreslete 10vrcholový les složený z 3 komponent a obsahující právě 8 hran. Pokud to není možné, zdůvodněte proč. 2 Dokažte, že mají-li dvě kružnice v grafu společnou hranu, existuje v tomto grafu kružnice tuto hranu neobsahující. 3 Dokažte, že přidáním libovolné hrany do souvislého grafu vznikne alespoň jedna kružnice. 4 Kolik vznikne kružnic, přidáme-li ke stromu dvě hrany? 5 Dokažte, že souvislý graf o n vrcholech a n hranách obsahuje právě jeden cyklus. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Kořenový strom Definice Strom, jehož hrany jsou orientované, se nazývá také orientovaný. Orientovaný strom, jenž má určen význačný vrchol (kořen) r, a v němž existuje orientovaná cesta z r do všech ostatních vrcholů, se naývá kořenový strom. Při kreslení kořenových grafů se obvykle vynechávají šipky definující orientaci hran, předpokládá se, že směřují ,,od kořene . Vzhledem k absenci cyklů je interpretace jednoznačná. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Kořenový strom ­ příklady Kde v sítích najdeme kořenové stromy? Směrování ­ cíl paketu je kořenem stromu cest vedoucích od ostatních vrcholů k němu. DNS ­ hierarchická struktura serverů obsluhujících domény různých úrovní. Multicast ­ zdroj je kořenem, cesty k příjemcům tvoří strom. Obrázek: Dvě obvyklá kreslení kořenového stromu. Kořen je vyznačen modře. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Vztah orientovaných a kořenových stromů Každý kořenový strom je orientovaný. Jaké jsou podmínky pro to, aby orientovaný strom byl zároveň kořenovým? Věta Orientovaný strom je kořenový právě tehdy, když právě jeden z jeho vrcholů má vstupní stupeň 0 a všechny ostatní vrcholy 1. Důkaz. Nechť r je kořen stromu a jeho vstupní stupeň je vyšší než 0. Potom do něj vede hrana z některého z ostatních vrcholů stromu. Do toho ovšem vede cesta z kořene, v grafu je tedy cyklus, čímž docházíme ke sporu. Pokud do některého z ostatních vrcholů (označme jej u) vedou více než 2 hrany (z různých vrcholů v, w), potom do něj vedou 2 cesty z kořene, a to skrze cesty do v, w. Tím opět docházíme ke sporu. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Vztah orientovaných a kořenových stromů ­ pokračování důkazu Důkaz. Označme r vrchol, jehož vstupní stupeň je 0. Poté pro každý jiný vrchol w platí následující: Vstupní stupeň w je roven 1. Existuje tedy právě jeden vrchol, u1, z nějž vede do w hrana. Není-li u1 totožný s r, vede do něj opět hrana z právě jednoho vrcholu, u2. Takto tvořená řada vrcholů, z nichž vede cesta do w, je nutně konečná, neboť strom je acyklický, tudíž se v ní žádný z vrcholů nemůže opakovat. Posledním vrcholem v této posloupnosti musí být r. Do každého vrcholu stromu tedy vede orientovaná cesta z vrcholu r a ten je tudíž kořenem stromu. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Hloubka vrcholů a výška stromů Definice Vzdálenost (počet hran na cestě) vrcholu od kořene stromu se nazývá hloubka či úroveň vrcholu. Hloubka kořene je rovna 0. Je zvykem kreslit vrcholy jedné úrovně ve stejné výšce. Definice Výškou kořenového stromu označujeme nejvyšší z hloubek všech jeho vrcholů. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Rodiče a sourozenci v kořenových stromech Definice Vede-li v kořenovém stromu hrana z vrcholu u do v, nazývá se u rodičem (otcem) v a v synem. Vrcholy mající společného rodiče nazýváme sourozenci. Obrázek: Vrchol u je rodičem obou vrcholů v, w, které jsou sourozenci. Definice Vrchol u je předkem vrcholu v, pokud leží na cestě z r do v. v se v takovém případě nazývá následníkem vrcholu u PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Listy a vnitřní vrcholy stromu Definice Vrchol, jenž nemá žádné potomky, nazýváme list stromu. Ostatní vrcholy se označují jako vnitřní. Obrázek: Vrcholy v, w, x jsou následníky vrcholu u. Vrchol w má jediného následníka x. Předky x jsou u, w. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Isomorfismus kořenových stromů Definice Kořenové stromy považujeme za isomorfní, pokud mezi nimi existuje isomorfismus který zobrazí kořen stromu na kořen. Obrázek: Dva levé grafy na obrázku jsou isomorfní kořenové stromy. Dva pravé grafy jsou isomorfní stromy, ale ne isomorfní kořenové stromy. Existuje tedy více různých tříd kořenových stromů s ohledem na isomorfismus než tříd stromů se stejným počtem vrcholů. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace n-ární, úplné stromy Definice Kořenový strom, jehož každý vrchol má nejvýše n potomků, se nazývá n-ární. n-ární strom, jehož vnitřní vrcholy mají právě n potomků a všechny listy jsou stejné hloubky, se nazývá úplný n-ární. Obrázek: Levý strom je 3-ární (ternární), pravý je úplný ternární. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Uspořádané stromy V některých případech může být výhodné potomky každého vrcholu jednoznačně pojmenovat a seřadit: Definice Uspořádaný strom je kořenový strom s daným pořadím potomků každého vrcholu. Při kreslení uspořádaného grafu se dané pořadí vrcholů dodržuje ve směru zleva doprava. Obrázek: Isomorfní kořenové stromy s různým uspořádáním. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Počet vrcholů úrovně stromu Pro každou úroveň n-árního stromu je dán limit počtu vrcholů v této úrovni: Věta V m-té úrovni n-árního stromu se nachází nejvýše nm vrcholů. Důkaz. Indukcí: Pro kořen platí triviálně: n0 = 1. Nechť je v úrovni k právě nk vrcholů. Každý z nich může mít nejvýše n potomků. Úroveň k + 1 tedy obsahuje nejvýše n nk = nk+1 vrcholů. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Kořenové stromy ­ cvičení 1 Nakreslete, nebo zdůvodněte proč to není možné: 1 Binární strom výšky 5 s právě 12 vrcholy a právě 5 listy. 2 Binární strom výšky 3 s právě 12 vrcholy. 2 Kolik existuje různých neúplných ternárních stromů výšky 3 takových, že každý vnitřní vrchol má právě 3 potomky. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Binární stromy Speciálním (a prakticky nejpoužívanějším) n-árním stromem je strom binární. Definice Uspořádaný 2-ární strom se nazývá binární. Potomci každého vrcholu jsou označováni jako levý a pravý. Každý kořenový strom lze převést na binární. Vnitřní algoritmy směrovacích zařízení mohou být založeny na binárních stromech. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Podstromy binárních stromů Definice Indukovaný podgraf binárního stromu G, tvořený jedním potomkem vrcholu v a všemi jeho následníky, se nazývá podstromem vrcholu v a stromu G. Podstrom binárního stromu je také binárním stromem. Každý vrchol má levý a pravý podstrom, přičemž jeho levý, resp. pravý, potomek je kořenem tohoto podstromu. Pravý a levý podstrom binárního stromu o výšce h mají výšku nejvýše h - 1, přičemž nejméně jeden z nich má výšku právě h - 1. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Podstromy binárních stromů ­ příklad Obrázek: Levý a pravý podstrom kořene stromu. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Počet vrcholů úplného binárního stromu Věta Úplný binární strom výšky h má právě 2h+1 - 1 vrcholů. Důkaz. Indukcí: Pro binární strom výšky 0 platí zřejmě. Nechť strom výšky k má právě 2k+1 - 1 vrcholů. jak bylo dokázáno dříve, (k + 1). vrstva obsahuje 2k+1 vrcholů. Strom výšky k + 1 tedy má 2k+1 - 1 + 2k+1 = 2 2k+1 - 1 = 2k+2 - 1 vrcholů. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Reprezentace kořenových stromů Kořenové stromy lze jednoznačně reprentovat polem rodičů ­ tedy polem, ve kterém je pro každý vrchol uložen pouze název jeho rodiče. Taková reprezentace je velmi prostorově výhodná (lineární prostorová složitost). Pole rodičů má tvar: - 0 0 0 2 2 3. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Reprezentace úplných ohodnocených stromů Obdobně výhodně lze reprezentovat úplné ohodnocené stromy. Každý vrchol může mít v lineárním poli pevně danou pozici. Na této pozici je v poli uloženo ohodnocení vrcholu. Konkrétně pro binární strom: Kořen je uložen na pozici 0. Potomci vrcholu k jsou uloženi na pozicích 2 k + 1, 2 k + 2. Pole reprezentující tento binární graf obsahuje hodnoty g r n e v i q. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Průchod binárním stromem V některých případech (např. synchronizace distribuovaných algoritmů a výpočtů) je potřebné projít všemi vrcholy grafu a vykonat nějakou akci. Průchod binárním stromem je možné provést 2 základními způsoby: 1 Průchod po úrovních 2 Průchod po podstromech PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Průchod binárním stromem po úrovních Vlož kořen do fronty. Dokud je fronta neprázdná: Odstraň její první vrchol a proveď akci. Vlož do fronty jeho potomky v daném pořadí. Vrcholy stromu jsou navštíveny v pořadí a, b, c, d, e, f , g, h, i, j, k, l. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Průchod binárním stromem po podstromech Proveď akci v kořenu stromu. Spusť algoritmus průchodu v levém podstromu. Spusť algoritmus průchodu v pravém podstromu. Tato verze algoritmu je rekurzivní. Průchod je možné implementovat iterativně bez rekurzivních volání za použití zásobníku. Akci lze také provádět po průchodu levým či oběma stromy. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Průchod po podstromech ­ příklad Vrcholy stromu jsou navštíveny v pořadí a, b, d, h, l, e, i, j, c, f , g, k. PB165 ­ Grafy a sítě Kružnice a cykly Stromy a jejich vlastnosti Kořenové stromy Binární stromy, reprezentace Cvičení ­ reprezentace kořenových stromů Nakreslete všechny binární stromy výšky 2 a rozdělte je do tříd podle isomorfismu. Nakreslete kořenový strom podle zadaného pole rodičů: - 0 1 1 2 2 3 4 4 PB165 ­ Grafy a sítě