Drzewo opinające i minimalne drzewo opinające

W tym samouczku dowiesz się o drzewie opinającym i minimalnym drzewie opinającym za pomocą przykładów i rysunków.

Zanim dowiemy się o łączeniu drzew, musimy zrozumieć dwa wykresy: wykresy nieukierunkowane i wykresy połączone.

Nieukierunkowane wykres przedstawia wykres, w którym krawędzie nie być skierowana w dowolnym kierunku (tj. Krawędzie są dwukierunkowe).

Niekierowany wykres

Połączony wykres jest wykres, który zawsze jest ścieżka z wierzchołkiem każdego innego wierzchołka.

Połączony wykres

Drzewo opinające

Drzewo rozpinające to podgraf nie skierowanego połączonego grafu, który zawiera wszystkie wierzchołki grafu z minimalną możliwą liczbą krawędzi. Jeśli brakuje wierzchołka, nie jest to drzewo opinające.

Krawędzie mogą mieć przypisaną wagę lub nie.

Całkowita liczba drzew rozpinających z nwierzchołkami, które można utworzyć z pełnego wykresu, jest równa .n(n-2)

Jeśli tak n = 4, maksymalna liczba możliwych drzew rozpinających jest równa . W ten sposób 16 drzew rozpinających można utworzyć z pełnego wykresu z 4 wierzchołkami.44-2 = 16

Przykład drzewa opinającego

Rozważmy drzewo opinające z poniższymi przykładami:

Niech oryginalny wykres będzie:

Wykres normalny

Oto niektóre z możliwych drzew rozpinających, które można utworzyć na podstawie powyższego wykresu:

A spanning tree A spanning tree A spanning tree A spanning tree A spanning tree A spanning tree

Minimalne drzewo rozpinające

Minimalne drzewo opinające to drzewo opinające, w którym suma ciężaru krawędzi jest jak najmniejsza.

Przykład drzewa opinającego

Zrozummy powyższą definicję za pomocą poniższego przykładu.

Początkowy wykres to:

Wykres ważony

Możliwe drzewa opinające z powyższego wykresu to:

Minimalne drzewo opinające - 1 Minimalne drzewo opinające - 2 Minimalne drzewo opinające - 3 Minimalne drzewo opinające - 4

Minimalne drzewo opinające z powyższych drzew rozpinających to:

Minimalne drzewo rozpinające

Minimalne drzewo opinające z wykresu jest wyznaczane przy użyciu następujących algorytmów:

1. Algorytm Prima
2. Algorytm Kruskala

Aplikacje Spanning Tree

• Protokół routingu sieci komputerowej
• Analiza skupień
• Planowanie sieci cywilnej

Minimalne aplikacje drzewa opinającego

• Aby znaleźć ścieżki na mapie
• Do projektowania sieci, takich jak sieci telekomunikacyjne, wodociągowe i elektryczne.