11 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, 2024 1/17 Fl: IB000: Stromy a kostry ■r 11.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 11.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, 2024 2/17 Fl: IB000: Stromy a kostry ■r Vlastnosti stromů Tvrzení 11.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. □ Petr Hliněný, Fl MU Brno, 2024 3/17 Fl: IB000: Stromy a kostry Definice: Každý jeho vrchol stromu stupně 1 nazveme listem stromu. Petr Hliněný, Fl MU Brno, 2024 4/17 Fl: IB000: Stromy a kostry Počet hran stromu Věta 11.3. Strom na n vrcholech má přesně n — 1 hran pro n > 1. * Předpokládejme platnost tvrzení pro libovolné přirozené n := i > 1. Nechť T je nyní libovolný strom na n := i + 1 vrcholech. Podle Tvrzení 11.2 obsahuje T vrchol v stupně 1. Označme T' — T — v graf vzniklý z T odebráním vrcholu v a jedné jeho hrany. Pak T' je také souvislý graf bez kružnic, a tudíž strom na n — 1 = i vrcholech. Dle indukčního předpokladu Tf má i — 1 — n — 2 hran, a proto T má // — 2 + 1 = // — 1 hran. ^ Důkaz: Toto tvrzení dokážeme indukcí podle n. * Strom s jedním vrcholem má přesně 0 = n — 1 hran. T : v Petr Hliněný, Fl MU Brno, 2024 5/17 Fl: IB000: Stromy a kostry Cesty ve stromech Věta 11.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 R2 nnezi u b 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í 11.2, což je spor. □ Důsledek 11.6. Přidáním jedné hrany do stromu vznikne právě jedna kružnice. Petr Hliněný, Fl MU Brno, 2024 6/17 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 11.5) • a zároveň maximální acyklický graf (plyne z Důsledku 11.6). Petr Hliněný, Fl MU Brno, 2024 7/17 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. nVrchol p nazveme následníkem vrcholu q, pokud cesta z kořene r do p obsahuje (neboli vede přes) q. Dále p nazveme potomkem q, pokud p je následníkem q a zároveň {p, q} je hranou T.c V kořenovém stromu nazveme listem každý vrchol, který nemá potomky. Každý vrchol kořenového stromu je následníkem kořene. V přirozeně přeneseném významu se u kořenových stromů používají pojmy rodič, prarodič, děti/synové, sourozenci, předchůdci, 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, 2024 8/17 Fl: IB000: Stromy a kostry 11.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, 2024 9/17 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 11.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, 2024 10/17 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 11.10). První ne-českou publikací na toto téma je pak až Kruskalův hladový algoritmus z roku 1956 (viz Algoritmus 11.8). Petr Hliněný, Fl MU Brno, 2024 11/17 Fl: IB000: Stromy a kostry TZ-"- Řešení minimální kostry 3 4 3 3 4 3 14 2 14 2 Algoritmus 11.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(ei) < w(e2) < • • • < w(em). □ 2. Inicializujeme prázdnou kostru T — (y(G),0). □ 3. Po řadě pro i — 1, 2,... , m provedeme následující: • Pokud T + a nevytváří kružnici, tak E(T)