V teorii grafů je strom definován jako graf, který je souvislý a neobsahuje žádnou kružnici. Les je neorientovaný graf, ve kterém jsou libovolné dva vrcholy spojeny nejvýše jednou cestou. Ekvivalentní definice zní, že les je množina navzájem nepropojených stromů, což vysvětluje jeho název.
Tzv. zakořeněný strom (též kořenový) má jeden význačný vrchol - kořen. Zakořeněním stromu je definována orientace hran: hrany pak vedou směrem od kořene, což je možné díky tomu, že strom je acyklický. Uvažujme uzel A v kořenovém stromu, pak libovolný uzel X na jednoznačné cestě od kořene do uzlu A se nazývá „předchůdce“ uzlu A (předek). Kořen stromu nemá rodiče a list stromu nemá žádné syny.
Stromy se často využívají pro ukládání dat (typicky čísel) v informatice jako tzv. vyhledávací stromy. Jde o strom, kde z každého vrcholu vedou nanejvýš tři hrany (jedna "seshora" - od "otce" - a maximálně dvě "dolů" - k dvěma "synům") a kde pro každý prvek platí, že jeho levý syn je menší nebo roven otci, pravý syn větší. Důvodem, proč se takové struktury používají, je např. rychlejší nalezení prvku, než kdyby byly všechny prvky "za sebou" (v poli, spojovém seznamu).
Při špatném použití binárního vyhledávacího stromu může nastat situace, že z každého vrcholu půjde směrem dolů pouze jedna hrana s vyšším prvkem - tím by se ztrácela výhoda rychlého nalezení prvku. Z tohoto důvodu se zavádějí vylepšení binárního vyhledávacího stromu, která se sama starají o tzv. vyvažování. Takovými strukturami jsou např. AVL stromy.
V kontextu algoritmů pro hledání minimální kostry grafu, algoritmus pracuje ve fázích tak, že postupně spojuje komponenty souvislosti (na počátku je každý vrchol komponentou souvislosti) do větších a větších celků, až zůstane jen jediný, a to je hledaná minimální kostra. Algoritmus se zastaví, jestliže buď již obsahuje n − 1 hran nebo i = m, tedy se probraly všechny hrany z G. Nejrychlejší známý deterministický algoritmus pro hledání minimální kostry grafu vytvořil Bernard Chazelle modifikací Borůvova algoritmu.
Minimální kostry - Jarníkův-Primův algoritmus
Předpokládejme, že ohodnocení hran v grafu je prosté. Je-li navíc definována funkce (tzv. ...), pak ... (pokud jsou k dispozici další informace o funkci a jejím použití, lze je zde rozvést).
tags: #souvislost #silna #souvislost #stromy #a #kostry