Čo je strom
Strom je súvislý graf, ktorý neobsahuje žiadnu kružnicu (je acyklický). Je to teda najúspornejší možný spôsob, ako pospájať všetky vrcholy do jedného kusa.
Malý strom (5 vrcholov)
Tento strom má 5 vrcholov a presne 4 hrany. Listy (stupeň 1) sú zafarbené.
Pojmy
List = vrchol stupňa 1 (vychádza z neho jediná hrana). Vnútorný vrchol = stupeň ≥ 2. Každý strom s aspoň 2 vrcholmi má aspoň 2 listy.
Koreňový a binárny strom
Keď jeden vrchol vyhlásime za koreň, dostaneme koreňový strom: každému vrcholu vieme určiť hĺbku (vzdialenosť od koreňa) a smer „nadol" k potomkom. Binárny strom je koreňový strom, v ktorom má každý vrchol najviac dvoch potomkov (ľavého a pravého).
Graf bez kružníc, ktorý nemusí byť súvislý, sa volá les — každý jeho komponent je strom. Strom je teda súvislý les. Navyše každý strom je bipartitný aj rovinný.
Vyber správnu odpoveď.
Vlastnosti stromov
Stromy sú výnimočné tým, koľko ekvivalentných charakterizácií majú. Najznámejšia: strom s n vrcholmi má presne n−1 hrán.
Počet hrán
Strom s n vrcholmi má presne n − 1 hrán. Strom s 5 vrcholmi má 4 hrany, s 8 vrcholmi má 7 hrán.
Jediná cesta
Medzi ľubovoľnými dvoma vrcholmi vedie práve jedna cesta. Keby viedli dve, vytvorili by spolu kružnicu.
Pridanie hrany
Pridanie ktorejkoľvek novej hrany do stromu vytvorí presne jednu kružnicu.
Pre graf G s n vrcholmi sú nasledujúce tvrdenia ekvivalentné: (1) G je strom; (2) G je súvislý a má n − 1 hrán; (3) G je acyklický a má n − 1 hrán; (4) medzi každými dvoma vrcholmi vedie práve jedna cesta.
Dôkaz indukciou podľa počtu vrcholov. Klikaj.
Vyber správnu odpoveď.
Kostra grafu
Kostra grafu G je jeho podgraf, ktorý je strom a zároveň obsahuje všetky vrcholy grafu G. Inými slovami — vyberieme z grafu čo najmenej hrán tak, aby ostal súvislý.
Definícia
Podgraf T ⊆ G je kostra, ak je súvislý, acyklický (teda strom) a obsahuje všetkých n vrcholov. Má teda n − 1 hrán.
Existencia
Každý súvislý graf má kostru. Stačí postupne odoberať hrany ležiace na kružniciach, kým nejaká kružnica existuje — súvislosť sa pritom nikdy nepokazí.
Kostru má graf práve vtedy, keď je súvislý. Nesúvislý graf nemá kostru (strom je súvislý), ale každý jeho komponent má vlastnú kostru — dohromady tvoria kostrový les.
Vyber správnu odpoveď.
Minimálna kostra (MST)
Ak má graf na hranách ohodnotenie (váhy — napríklad cenu kábla), hľadáme kostru s najmenším súčtom váh. Volá sa minimálna kostra (anglicky minimum spanning tree, MST).
Kruskalov algoritmus
Hrany utrieď podľa váhy od najmenšej. Postupne priber najlacnejšiu hranu, ktorá nevytvorí kružnicu; inak ju preskoč. Skončíš s n − 1 hranami.
Primov algoritmus
Začni v jednom vrchole. V každom kroku priber najlacnejšiu hranu, ktorá spája už pripojený vrchol s novým. Strom tak rastie z jedného komponentu.
Oba algoritmy sú hladové (greedy) a napriek tomu dávajú vždy optimálne riešenie. Ak sú všetky váhy rôzne, minimálna kostra je dokonca jediná.
Vrcholy A, B, C, D a hrany s váhami: AB = 1, BC = 2, CD = 3, AD = 4, AC = 5. Klikaj.
Vyber správnu odpoveď.
Aplikácie a počítanie
Stromy a kostry sú všade — od dátových štruktúr cez návrh sietí až po najkratšie cesty. Pozrime sa na tri klasiky.
Binárny strom a výška
Binárny strom s výškou h má najviac 2h+1 − 1 vrcholov. Naopak, na uloženie N vrcholov treba výšku aspoň log₂(N+1) − 1.
Cayleyho vzorec
Počet rôznych kostier úplného grafu Kₙ je presne nⁿ⁻². Napr. K₃ má 3 kostry, K₄ má 16.
Najkratšia cesta
Dijkstrov algoritmus nájde najkratšie cesty z jedného vrcholu do všetkých ostatných (pri nezáporných váhach), pričom buduje strom najkratších ciest.
Pozor na rozdiel: Cayleyho vzorec ráta koľko kostier existuje, kým Kruskal/Prim nájde jednu konkrétnu minimálnu. A Dijkstra rieši iný cieľ — najkratšie cesty, nie najľahšiu kostru.
Klikni a over si výsledok.
Vyber správnu odpoveď.
Záverečný kvíz
Desať otázok cez celú tému — od definície stromu cez vlastnosti a kostry až po Kruskala a Cayleyho vzorec.
Otestuj sa cez celú tému.