(spanning tree)
podgraf zawierajacy wszystkie wierzcholki grafu, bedacy drzewem i majacy wystarczajaco duzo krawedzi, aby podgraf byl spójny, lecz nie az tyle, zeby mial cykl. Kazde d.r. grafu o n wierzcholkach ma dokladnie n-1 krawedzi.
drzewo rozpinajace
Informatyka