V matematike je spanning strom subgrafom neorientovaného grafu, ktorý obsahuje všetky vrcholy neorientovaného grafu. Je to základný nástroj na riešenie zložitých problémov v matematike, ako je problém so štyrmi farebnými mapami a problém cestujúceho obchodníka. Zvyčajne je to preklenutý strom vytvorený rozvetvením z jedného z vnútorných bodov, preto je opísaný ako strom.

Podrobné vysvetlenie

Ak chcete vizualizovať spanning strom, najprv obrázok neorientovaný graf: napríklad náhodný kolekcia bodov spojených riadkami. Pripojenia musia byť neorientované; Znamená to, že môžete prejsť v oboch smeroch na tratiach, aby ste sa dostali z jedného bodu do druhého. Každý bod musí byť nejakým spôsobom spojený so zvyškom a každý bod môže mať viacero pripojení.

Spanning strom pre tento graf je ľubovoľný podgraf (graf s použitím rovnakých bodov), ktorý sa dotýka všetkých bodov, hoci nemusí zdieľať všetky rovnaké čiary.

Graf, Podmienky siete, protokol Spanning Tree