Drzewo rozpinające () – 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 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 [dostęp 2025-12-14]. Spanning tree , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-12-14].
Kategoria:Teoria grafów Kategoria:Dwuczłonowe relacje matematyczne