W tym artykule omówimy drzewo rozpinające i minimalne drzewo rozpinające. Zanim jednak przejdziemy bezpośrednio do drzewa opinającego, przyjrzyjmy się najpierw krótkiemu opisowi grafu i jego typów.
Wykres
Wykres można zdefiniować jako grupę wierzchołków i krawędzi łączących te wierzchołki. Rodzaje wykresów podano w następujący sposób:
Przejdźmy teraz do drzewa rozpinającego temat.
Co to jest drzewo rozpinające?
Drzewo rozpinające można zdefiniować jako podgraf nieskierowanego, połączonego grafu. Obejmuje wszystkie wierzchołki wraz z możliwie najmniejszą liczbą krawędzi. Jeśli pominięto jakikolwiek wierzchołek, nie jest to drzewo rozpinające. Drzewo rozpinające to podzbiór grafu, który nie ma cykli i którego również nie można rozłączyć.
Drzewo rozpinające składa się z (n-1) krawędzi, gdzie „n” to liczba wierzchołków (lub węzłów). Krawędzie drzewa rozpinającego mogą mieć przypisane wagi lub nie. Wszystkie możliwe drzewa rozpinające utworzone z danego grafu G miałyby tę samą liczbę wierzchołków, ale liczba krawędzi w drzewie rozpinającym byłaby równa liczbie wierzchołków danego grafu minus 1.
Może mieć kompletny graf nieskierowany Nn-2 liczba drzew rozpinających, gdzie N to liczba wierzchołków grafu. Załóżmy, że n = 5 , wyniosłaby liczba maksymalnych możliwych drzew rozpinających 55-2= 125.
Zastosowania drzewa opinającego
Zasadniczo drzewo opinające służy do znalezienia minimalnej ścieżki łączącej wszystkie węzły grafu. Niektóre z typowych zastosowań drzewa opinającego są wymienione poniżej:
- Analiza skupień
- Planowanie sieci cywilnej
- Protokół routingu sieci komputerowej
Przyjrzyjmy się teraz drzewu opinającemu na przykładzie.
Przykład drzewa opinającego
Załóżmy, że wykres będzie -
Jak omówiono powyżej, drzewo rozpinające zawiera taką samą liczbę wierzchołków jak graf, liczba wierzchołków na powyższym wykresie wynosi 5; dlatego drzewo rozpinające będzie zawierać 5 wierzchołków. Krawędzie drzewa rozpinającego będą równe liczbie wierzchołków grafu minus 1. Zatem w drzewie rozpinającym będą 4 krawędzie.
Niektóre z możliwych drzew rozpinających, które zostaną utworzone na podstawie powyższego wykresu, są podane w następujący sposób:
Właściwości drzewa opinającego
Niektóre właściwości drzewa opinającego podano w następujący sposób:
- Może istnieć więcej niż jedno drzewo rozpinające połączonego grafu G.
- Drzewo opinające nie ma żadnych cykli ani pętli.
- Drzewo rozpinające jest minimalnie podłączony, więc usunięcie jednej krawędzi z drzewa spowoduje rozłączenie wykresu.
- Drzewo rozpinające jest maksymalnie acykliczny, więc dodanie jednej krawędzi do drzewa spowoduje utworzenie pętli.
- Może być maksimum Nn-2 liczba drzew rozpinających, które można utworzyć z pełnego grafu.
- Drzewo rozpinające ma n-1 krawędzie, gdzie „n” to liczba węzłów.
- Jeśli graf jest grafem pełnym, wówczas drzewo rozpinające można skonstruować poprzez usunięcie maksymalnych (e-n+1) krawędzi, gdzie „e” to liczba krawędzi, a „n” to liczba wierzchołków.
Zatem drzewo rozpinające jest podzbiorem połączonego grafu G i nie ma drzewa rozpinającego grafu rozłączonego.
Minimalne drzewo rozpinające
Minimalne drzewo rozpinające można zdefiniować jako drzewo rozpinające, w którym suma wag krawędzi jest minimalna. Ciężar drzewa rozpinającego jest sumą ciężarów nadanych krawędziom drzewa rozpinającego. W prawdziwym świecie wagę tę można uznać za odległość, obciążenie ruchem, natężenie ruchu lub dowolną wartość losową.
Przykład minimalnego drzewa rozpinającego
Przyjrzyjmy się minimalnemu drzewu rozpinającemu na przykładzie.
Suma krawędzi powyższego wykresu wynosi 16. Oto niektóre z możliwych drzew rozpinających utworzonych na podstawie powyższego wykresu:
Zatem minimalne drzewo rozpinające wybrane z powyższych drzew rozpinających dla danego grafu ważonego to -
Zastosowania minimalnego drzewa rozpinającego
Zastosowania minimalnego drzewa rozpinającego podano w następujący sposób:
- Minimalne drzewo rozpinające można wykorzystać do projektowania sieci wodociągowych, telekomunikacyjnych i elektroenergetycznych.
- Można go używać do wyszukiwania ścieżek na mapie.
Algorytmy minimalnego drzewa rozpinającego
Minimalne drzewo rozpinające można znaleźć na podstawie wykresu ważonego, korzystając z algorytmów podanych poniżej -
- Algorytm Prima
- Algorytm Kruskala
Zobaczmy krótki opis obu algorytmów wymienionych powyżej.
Algorytm Prima - Jest to zachłanny algorytm rozpoczynający się od pustego drzewa opinającego. Służy do znalezienia minimalnego drzewa rozpinającego z wykresu. Algorytm ten znajduje podzbiór krawędzi obejmujący każdy wierzchołek grafu w taki sposób, że suma wag krawędzi może być zminimalizowana.
status git -s
Aby dowiedzieć się więcej o algorytmie prima, kliknij poniższy link - https://www.javatpoint.com/prim-algorithm
Algorytm Kruskala - Algorytm ten jest również używany do znalezienia minimalnego drzewa rozpinającego dla połączonego grafu ważonego. Algorytm Kruskala również opiera się na podejściu zachłannym, które znajduje optymalne rozwiązanie na każdym etapie, zamiast skupiać się na optymalnym globalnym.
Aby dowiedzieć się więcej o algorytmie prima, kliknij poniższy link - https://www.javatpoint.com/kruskal-algorithm
To tyle na temat artykułu. Mam nadzieję, że artykuł będzie dla Ciebie pomocny i pouczający. W tym miejscu omówiliśmy drzewo opinające i minimalne drzewo opinające wraz z ich właściwościami, przykładami i zastosowaniami.