Reklama

drzewo rozpinajace

(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.

Reklama

Encyklopedia Internautica
Reklama
Reklama
Reklama