1. Czym jest drzewo i las?

Drzewo

• W teorii grafów a drzewo jest Graf nieskierowany, spójny i acykliczny . Innymi słowy, spójny graf, który nie zawiera ani jednego cyklu, nazywa się drzewem.
• Drzewo reprezentuje strukturę hierarchiczną w formie graficznej.
• Elementy drzewa nazywane są ich węzłami, a krawędzie drzewa nazywane są gałęziami.
• Drzewo z n wierzchołkami ma (n-1) krawędzi.
• Drzewa zapewniają wiele przydatnych aplikacji, od prostych jak drzewo genealogiczne po tak złożone, jak drzewa w strukturach danych w informatyce.
• A liść w drzewie jest wierzchołek stopnia 1 lub każdy wierzchołek nie mający dzieci nazywany jest liściem.

Przykład

W powyższym przykładzie wszystkie są drzewami mającymi mniej niż 6 wierzchołków.

Las

W teorii grafów a las Jest graf nieskierowany, rozłączony, acykliczny . Innymi słowy, rozłączny zbiór drzew nazywany jest lasem. Każdy element lasu to drzewo.

co to jest maven

Przykład

Powyższy wykres wygląda jak dwa podwykresy, ale jest to pojedynczy, niepołączony wykres. Na powyższym wykresie nie ma cykli. Dlatego jest to las.

2. Właściwości drzew

1. Każde drzewo, które ma co najmniej dwa wierzchołki, powinno mieć co najmniej dwa liście.
2. Drzewa mają wiele cech:
   Niech T będzie grafem mającym n wierzchołków, wtedy poniższe stwierdzenia są równoważne:
   • T jest drzewem.
   • T nie zawiera cykli i ma n-1 krawędzi.
   • T jest spójny i ma (n -1) krawędź.
   • T jest grafem spójnym, a każda krawędź jest krawędzią ciętą.
   • Dowolne dwa wierzchołki grafu T są połączone dokładnie jedną ścieżką.
   • T nie zawiera cykli i dla każdej nowej krawędzi e graf T+ e ma dokładnie jeden cykl.
3. Każda krawędź drzewa jest obcięta.
4. Dodanie jednej krawędzi do drzewa definiuje dokładnie jeden cykl.
5. Każdy spójny graf zawiera drzewo rozpinające.
6. Każde drzewo ma co najmniej dwa wierzchołki stopnia drugiego.

3. Drzewo opinające

A drzewo rozpinające w grafie połączonym G jest podgrafem H grafu G, który zawiera wszystkie wierzchołki G i jest również drzewem.

Przykład

Rozważmy następujący wykres G:

Z powyższego wykresu G możemy zaimplementować następujące trzy drzewa rozpinające H:

Metody znajdowania drzewa opinającego

Drzewo opinające możemy znaleźć systematycznie, stosując jedną z dwóch metod:

1. Metoda wycinania
2. Metoda budowania

1. Metoda wycinania

• Zacznij wybierać dowolny cykl na wykresie G.
• Usuń jedną z krawędzi cyklu.
• Powtarzaj ten proces, aż nie pozostaną żadne cykle.

Przykład

• Rozważmy wykres G,

• Jeśli usuniemy krawędź ac, która niszczy cykl a-d-c-a z powyższego wykresu, otrzymamy następujący wykres:

• Usuń krawędź cb, która niszczy cykl a-d-c-b-a z powyższego wykresu, a otrzymamy następujący wykres:

• Jeśli usuniemy krawędź ec, która niszczy cykl d-e-c-d z powyższego wykresu, otrzymamy następujące drzewo rozpinające:

2. Metoda budowania

• Wybieraj krawędzie grafu G pojedynczo. W taki sposób, że nie powstają żadne cykle.
• Powtarzaj ten proces, aż wszystkie wierzchołki zostaną uwzględnione.

Przykład

Rozważmy następujący wykres G,

• Wybierz krawędź ok ,

• Wybierz krawędź z ,

• Następnie wybierz krawędź ec ,

• Następnie wybierz krawędź cb , ostatecznie otrzymujemy następujące drzewo opinające:

Ranga obwodu

Liczba krawędzi, które musimy usunąć z G, aby otrzymać drzewo rozpinające.

Drzewo opinające G = m- (n-1) , czyli tzw ranga obwodu z G.

 Where, m = No. of edges. n = No. of vertices. 

Przykład

Na powyższym wykresie krawędzie m = 7 i wierzchołki n = 5

przełącz Javę

Wtedy ranga obwodu wynosi:

 G = m - (n - 1) = 7 - (5 - 1) = 3