Drzewo rozpinające

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

• 
  Drzewo rozpinające (czerwone krawędzie) w grafie
• 
  Inne drzewo rozpinające w tym samym grafie

Drzewo rozpinające można znaleźć przykładowo wykorzystując algorytm DFS lub Dijkstry.

Zobacz też

• minimalne drzewo rozpinające
• teoria grafów
• twierdzenie Kirchhoffa