W dziedzinie matematyki w teorii grafów , a drzewa rozpinającego wystąpienia undirected wykresu i powiązany jest wał zawarte na tym wykresie, która łączy wszystkie węzły grafu.
Równoważnie jest to maksymalny podgraf acykliczny lub nawet minimalnie połączony podgraf pokrywający .
W niektórych przypadkach liczbę drzew rozpinających połączonego wykresu można łatwo obliczyć. Na przykład, jeśli samo jest drzewem, to podczas gdy jeśli jest n-cyklem , to . Dla dowolnego wykresu można go obliczyć za pomocą twierdzenia Kirchhoffa .
Wzór Cayley obliczyć bezpośrednio do całkowitego wykresie . Rozumiemy .
Jeśli G jest pełnym wykresem dwudzielnym , to jest .
Drzewa rozpinające wykresu tworzą matroid i dlatego mogą być wyliczane przez algorytm z wielomianowym opóźnieniem .
Klasycznym problemem algorytmicznym jest znalezienie na wykresie ważonym drzewa opinającego o minimalnej wadze . Waga może oznaczać trudność w uzyskaniu połączenia, na przykład długi czas przejścia łącza. W przypadku grafu ważonego również istnieje kilka algorytmów ( algorytm Borůvka , algorytm Prim , algorytm Kruskala …).
Drzewa spinające są badane w informatyce teoretycznej pod kątem ich zastosowań w sieciach komputerowych.
W ten sposób mogą zdefiniować ścieżkę umożliwiającą przekazywanie informacji z jednego węzła sieci do dowolnego innego węzła, unikając jednocześnie obecności pętli. Pętle są denerwujące w sieci komputerowej, ponieważ informacje mogą przechodzić przez pętlę i obracać się kilka razy, zanim dotrą do celu, lub nawet obracać się w nieskończoność w pętli, nigdy nie docierając do celu. W skrajnym przypadku burzy rozgłoszeniowej sieć staje się bezużyteczna.
Algorytm Spanning Tree Protocol odkryty przez Radię Perlman w 1985 roku umożliwia znalezienie drzewa opinającego na dowolnym wykresie. Umożliwia nawet znalezienie takiego drzewa w multigrafie , który może zatem zawierać kilka krawędzi między daną parą węzłów. Po zdefiniowaniu drzewa opinającego urządzenia zlokalizowane w węzłach sieci blokują administracyjnie wszystkie nadmiarowe łącza. W przypadku awarii łącza do drzewa opinającego obliczane jest nowe drzewo, co umożliwia kontynuowanie działania sieci, jeśli istnieje zapasowe łącze zapasowe.