9 Stromy a kostry grafů Na rozdíl od předchozí lekce, která se zabývala grafy z obecného a také trochu povrchního pohledu, se nyní soustředíme na jednu konkrétní nepříliš obtížnou oblast, které se budeme věnovat do větší hloubky. Jde o problematiku stromů, neboli acyklických souvislých grafů, představujících nejjednodušší podobu grafů. Stručný přehled lekce * Stromy a jejich vlastnosti s důkazy. * Minimální kostra grafu a její základní algoritmy. * Dodatek: systémy různých reprezentantů. Petr Hliněný, Fl MU Brno, 2017 1/16 Fl: IB000: Stromy a kostry ■r 9.1 Stromy - grafy bez kružnic Začněme ilustračními obrázky stromu. Povšimněte si přitom jedné zvláštnosti, totiž že v informatice stromy typicky rostou „shora dolů"... Charakteristickými znaky stromu je absence kružnic a souvislost. □ Definice 9.1. Strom je (jednoduchý) souvislý graf T bez kružnic. □ Obecněji les je pak graf bez kružnic (jednoduchý, nemusí být souvislý). Komponenty souvislosti lesa jsou stromy. Jeden vrchol bez hran a prázdný graf jsou také stromy. Grafy bez kružnic také obecně nazýváme acyklické. Petr Hliněný, Fl MU Brno, 2017 2/16 Fl: IB000: Stromy a kostry ■r Vlastnosti stromů Tvrzení 9.2. Strom s více než jedním vrcholem obsahuje vrchol stupně 1. Důkaz: Vezmeme libovolný strom Tav něm libovolný vrchol v. Jelikož souvislý graf s více než jedním vrcholem nemá vrchol stupně 0, vrch. v má incidentní hranu. nZvolme (sestrojme) nyní nejdelší možnou cestu S y T začínající ve v: * S začne libovolnou hranou vycházející z v; * v každém dalším vrcholu u cesty S, který má stupeň větší než 1, pokračuje S další hranou. Pokud by tomu tak nebylo, není S nejdelší možná nebo další hrana vede do některého předchozího vrcholu cesty S. Tím bychom ale získali kružnici. s \ / □ Proto cesta S nutně skončí v nějakém vrcholu stupně 1 v T. □ Definice: Každý jeho vrchol stromu stupně 1 nazveme listem stromu. Petr Hliněný, Fl MU Brno, 2017 3/16 Fl: IB000: Stromy a kostry Počet hran stromu Věta 9.3. Strom na n vrcholech má presne n — 1 hran pro n > 1. Důkaz: Toto tvrzení dokážeme indukcí podle n. * Strom s jedním vrcholem má n — 1 = 0 hran. * Nechť T je strom na n > 1 vrcholech. Podle Tvrzení 9.2 má T vrchol v stupně 1. Označme T' — T — v graf vzniklý z T odebráním vrcholu v. Pak T' je také souvislý bez kružnic, tudíž strom na n — 1 vrcholech. Dle indukčního předpokladu T' má n —1 — 1 hran, a proto Tmán —1 — 1 + 1 = n — 1 hran. ^ Petr Hliněný, Fl MU Brno, 2017 4/16 Fl: IB000: Stromy a kostry Cesty ve stromech Věta 9.5. Mezi každými dvěma vrcholy stromu vede právě jediná cesta. u ®---- Důkaz: Jelikož strom T je souvislý dle definice, mezi libovolnými dvěma vrcholy u,v vede nějaká cesta. Pokud by existovaly dvě různé cesty R\,R2 mezi u,v, tak bychom vzali jejich symetrický rozdíl, podgraf H = R1AR2 s neprázdnou množinou hran, kde H zřejmě má všechny stupně sudé. ^Na druhou stranu se však podgraf stromu musí opět skládat z komponent stromů, a tudíž obsahovat vrchol stupně 1 podle Tvrzení 9.2, což je spor. □ Důsledek 9.6. Přidáním jedné hrany do stromu vznikne právě jedna kružnice. Petr Hliněný, Fl MU Brno, 2017 5/16 Fl: IB000: Stromy a kostry Alternativní charakterizace stromů Na dané množině vrcholů je (vzhledem k inkluzi množin hran) strom • minimální souvislý graf (plyne z Věty 9.5) • a zároveň maximální acyklický graf (plyne z Důsledku 9.6). Petr Hliněný, Fl MU Brno, 2017 6/16 Fl: IB000: Stromy a kostry Kořenový strom Definice: Strom T s vyznačeným vrcholem r £ V (T), zkráceně dvojice (T, r), nazýváme kořenovým stromem s kořenem r. Vrchol p nazveme potomkem vrcholu q, pokud cesta z kořene r do p obsahuje (neboli vede přes) q. V kořenovém stromu nazveme listem každý vrchol, který nemá potomky. Každý vrchol kořenového stromu je potomkem kořene. V přirozeně přeneseném významu se u kořenových stromů používají pojmy rodič, děti/synové, sourozenci, předchůdce, následník, atd. kořen □ Definice: Výška kořenového stromu je rovna největší vzdálenosti z jeho kořene do některého listu. Petr Hliněný, Fl MU Brno, 2017 7/16 Fl: IB000: Stromy a kostry 9.2 Problém minimální kostry V návaznosti na učivo o stromech se podívame na tradiční a široce studovaný problém nalezení minimálního souvislého podgrafu (stromu) - této úloze se říká minimální kostra neboli MST (z anglického minimum spanning tree). Petr Hliněný, Fl MU Brno, 2017 8/16 Fl: IB000: Stromy a kostry ■r Minimální kostra a vážené grafy Definice: Podgraf T C G souvislého grafu G se nazýva kostrou, pokud * T je stromem a * V (T) = V (G), neboli T propojuje všechny vrcholy G. □ Avšak každý strom na daných n vrcholech má stejně hran, presne n — 1. Jaký smysl tedy má dávat slovo „minimální" u hledané kostry? Definice: Vážený graf je graf G spolu s ohodnocením w hran reálnými čísly Vahou (délkou) kostry T C G váženého souvislého grafu (G,w) rozumíme Definice 9.7. Problém minimální kostry (MST) ve váž. grafu (G,w) hledá kostru T C G s nejmenší možnou vahou (přes všechny kostry grafu G). w : E{G) -> R.c Petr Hliněný, Fl MU Brno, 2017 9/16 Fl: IB000: Stromy a kostry ■r Historické ohlédnutí Problém minimální kostry je ve skutečnosti historicky úzce svázán s jižní Moravou a Brnem, konkrétně s elektrifikací jihomoravských vesnic ve dvacátých letech! Právě na základě tohoto praktického optimalizačního problému brněnský matematik Otakar Borůvka jako první v matematické literatuře zformuloval a podal řešení problému minimální kostry v roce 1926. Ve výzkumu minimálních koster pokračoval i velmi dobře známý český matematik Vojtěch Jarník, s publikací v roce 1930 (viz Algoritmus 9.10). První nečeskou publikací na toto téma je pak až Kruskalův hladový algoritmus z roku 1956 (viz Algoritmus 9.8). Petr Hliněný, Fl MU Brno, 2017 10/16 Fl: IB000: Stromy a kostry TZ-"- Řešení minimální kostry 3 4 3 3 4 3 14 2 14 2 Algoritmus 9.8. Hladový postup pro minimální kostru grafu (G,w). Mějme dán souvislý vážený graf G s ohodnocením hran w. 1. Seřadíme všechny hrany G jako E(G) — (ei, • • •, em) tak, že w(e\) < w(e2) < • • • < w(em). 2. Inicializujeme prázdnou kostru T — (V(G),0). □ 3. Po řadě pro i — 1, 2,... , m provedeme následující: • Pokud T + a nevytváří kružnici, tak E(T)