Drzewo rozpinające

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Drzewem rozpinającym (ang. Spanning Tree) grafu G nazywamy drzewo, które zawiera wszystkie wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem zbioru krawędzi grafu.

Konstrukcja drzewa rozpinającego polega na usuwaniu z grafu tych krawędzi, które należą do cykli. Najmniejszą liczbą krawędzi jaką trzeba usunąć z grafu, aby graf stał się acykliczny (stał się drzewem) nazywa się rzędem acykliczności grafu lub liczbą cyklometryczną.

Zobacz też[edytuj | edytuj kod]