V matematice je překlenovací strom subgrafem neřízeného grafu, který obsahuje všechny vrcholy neorientovaného grafu. Je to základní nástroj, který se používá k řešení složitých problémů v matematice, jako je problém se čtyřbarevnou mapou a problém cestujícího prodavače. Obvykle se jedná o klenutý strom tvořený odbočením z jednoho z vnitřních bodů, což je důvod, proč je popsán jako strom.

Podrobné vysvětlení

Chcete-li vizualizovat spanning strom, první obrázek neorientovaného grafu: například náhodná kolekce bodů spojených čarami. Spojení musí být neřízená; to znamená, že můžete cestovat v obou směrech na tratích, abyste se dostali z jednoho bodu do druhého. Každý bod musí být nějakým způsobem připojen ke zbytku a každý bod může mít více spojení.

Spanning strom pro tento graf je nějaký subgraph (graf používat stejné body) který se dotýká všech bodů, ačkoli to nepotřebuje sdílet všechny stejné linky.

Graf, podmínky sítě, protokol Spanning Tree