Struktura danych i algorytmy - drzewo opinające
Drzewo rozpinające to podzbiór Grafu G, który ma wszystkie wierzchołki pokryte minimalną możliwą liczbą krawędzi. Dlatego drzewo opinające nie ma cykli i nie można go odłączyć.
Na podstawie tej definicji możemy wyciągnąć wniosek, że każdy połączony i nieukierunkowany Graf G ma co najmniej jedno drzewo opinające. Odłączony graf nie ma żadnego drzewa opinającego, ponieważ nie można go rozpiąć na wszystkie jego wierzchołki.
Znaleźliśmy trzy rozpinające się drzewa z jednego pełnego wykresu. Pełny wykres nie skierowany może mieć maksimumnn-2 liczba drzew rozpinających, gdzie nto liczba węzłów. W powyższym przykładzien is 3, W związku z tym 33−2 = 3 możliwe są drzewa spinające.
Ogólne właściwości drzewa opinającego
Teraz rozumiemy, że jeden wykres może mieć więcej niż jedno drzewo opinające. Poniżej przedstawiono kilka właściwości drzewa opinającego połączonego z wykresem G -
Połączony wykres G może mieć więcej niż jedno drzewo opinające.
Wszystkie możliwe drzewa rozpinające grafu G mają taką samą liczbę krawędzi i wierzchołków.
Drzewo opinające nie ma żadnego cyklu (pętli).
Usunięcie jednej krawędzi z drzewa opinającego spowoduje odłączenie wykresu, tj. Drzewo opinające zostanie odłączone minimally connected.
Dodanie jednej krawędzi do drzewa opinającego utworzy obwód lub pętlę, czyli drzewo opinające maximally acyclic.
Matematyczne właściwości drzewa opinającego
Drzewo opinające ma n-1 krawędzie, gdzie n to liczba węzłów (wierzchołków).
Z pełnego wykresu, usuwając maksimum e - n + 1 krawędzi, możemy skonstruować drzewo opinające.
Pełny wykres może mieć maksimum nn-2 liczba drzew rozpinających.
W związku z tym możemy wywnioskować, że drzewa opinające są podzbiorem połączonych wykresów G, a odłączone wykresy nie mają drzewa opinającego.
Zastosowanie Spanning Tree
Drzewo rozpinające jest zasadniczo używane do znajdowania minimalnej ścieżki połączenia wszystkich węzłów na wykresie. Typowe zastosowanie drzew rozpinających to:
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis
Zrozummy to na małym przykładzie. Rozważmy sieć miejską jako ogromny wykres, a teraz planujemy rozmieścić linie telefoniczne w taki sposób, aby przy minimalnej liczbie linii można było podłączyć się do wszystkich węzłów miasta. W tym miejscu pojawia się drzewo opinające.
Minimalne drzewo rozpinające (MST)
Na wykresie ważonym minimalne drzewo opinające to drzewo opinające, które ma minimalną wagę niż wszystkie inne drzewa opinające na tym samym wykresie. W rzeczywistych sytuacjach wagę tę można zmierzyć jako odległość, zatłoczenie, obciążenie ruchem lub dowolną wartość oznaczoną na krawędziach.
Algorytm minimalnego drzewa opinającego
Dowiemy się tutaj o dwóch najważniejszych algorytmach drzewa opinającego -
Algorytm Kruskala
Algorytm Prima
Oba są chciwymi algorytmami.