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

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Spanning Tree, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2025-12-14].
• Spanning tree (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-12-14].