Drzewo rozpinające


Drzewo rozpinające w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Drzewo rozpinające (ang. Spanning Tree) – 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 kod

Na podstawie artykułu: "Drzewo rozpinające" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy