Teoria grafów - drzewa
Drzewa to wykresy, które nie zawierają ani jednego cyklu. Reprezentują hierarchiczną strukturę w formie graficznej. Drzewa należą do najprostszych klas grafów. Pomimo swojej prostoty mają bogatą strukturę.
Drzewa zapewniają szereg użytecznych aplikacji, od prostych, jak drzewo genealogiczne, po tak złożone, jak drzewa w strukturach danych informatycznych.
Drzewo
ZA connected acyclic graphnazywa się drzewem. Innymi słowy, połączony wykres bez cykli nazywany jest drzewem.
Krawędzie drzewa są znane jako branches. Elementy drzew nazywane są ich węzłami. Nazywane są węzły bez węzłów potomnychleaf nodes.
Drzewo z „n” wierzchołkami ma „n-1” krawędzi. Jeśli ma jeszcze jedną krawędź więcej niż „n-1”, to ta dodatkowa krawędź powinna oczywiście łączyć się z dwoma wierzchołkami, co prowadzi do utworzenia cyklu. Następnie staje się wykresem cyklicznym, co jest naruszeniem dla wykresu drzewiastego.
Example 1
Wykres pokazany tutaj jest drzewem, ponieważ nie ma cykli i jest połączony. Ma cztery wierzchołki i trzy krawędzie, tj. Dla „n” wierzchołków „n-1” krawędzi, jak wspomniano w definicji.
Note - Każde drzewo ma co najmniej dwa wierzchołki pierwszego stopnia.
Example 2
W powyższym przykładzie wierzchołki „a” i „d” mają stopień pierwszy. A pozostałe dwa wierzchołki „b” i „c” mają stopień drugi. Jest to możliwe, ponieważ aby nie tworzyć cyklu, w dowolnym miejscu wykresu powinny znajdować się co najmniej dwie pojedyncze krawędzie. To nic innego jak dwie krawędzie z jednym stopniem.
Las
ZA disconnected acyclic graphnazywa się lasem. Innymi słowy, rozłączny zbiór drzew nazywany jest lasem.
Example
Poniższy wykres wygląda jak dwa pod-wykresy; ale jest to pojedynczy odłączony wykres. Na tym wykresie nie ma cykli. Stąd ewidentnie jest to las.
Drzewa spinające
Niech G będzie grafem połączonym, wtedy pod-graf H z G nazywany jest drzewem rozpinającym G, jeśli -
- H to drzewo
- H zawiera wszystkie wierzchołki G.
Drzewo rozpinające T grafu niekierowanego G to podgraf zawierający wszystkie wierzchołki G.
Example
W powyższym przykładzie G jest połączonym wykresem, a H jest pod-wykresem G.
Oczywiście wykres H nie ma cykli, jest to drzewo o sześciu krawędziach, czyli o jeden mniej niż całkowita liczba wierzchołków. Stąd H jest drzewem opinającym G.
Ranking obwodu
Niech „G” będzie grafem połączonym z „n” wierzchołkami i „m” krawędziami. Drzewo opinające „T” G zawiera (n-1) krawędzi.
Dlatego liczba krawędzi, które należy usunąć z `` G '', aby uzyskać drzewo opinające = m- (n-1), które nazywa się rangą obwodu G.
Ta formuła jest prawdziwa, ponieważ w drzewie rozpinającym musisz mieć krawędzi „n-1”. Poza krawędziami „m” musisz zachować na wykresie krawędzi „n – 1”.
Stąd usunięcie krawędzi „n – 1” z „m” daje krawędzie, które należy usunąć z wykresu w celu uzyskania drzewa opinającego, które nie powinno tworzyć cyklu.
Example
Spójrz na poniższy wykres -
Dla wykresu podanego w powyższym przykładzie masz m = 7 krawędzi in = 5 wierzchołków.
Wtedy ranga obwodu to -
Example
Niech „G” będzie grafem połączonym z sześcioma wierzchołkami, a stopień każdego z nich wynosi trzy. Znajdź rangę obwodu „G”.
Twierdzenie o sumie stopni wierzchołków
Twierdzenie Kirchoffa
Twierdzenie Kirchoffa jest przydatne w znajdowaniu liczby drzew rozpinających, które można utworzyć z połączonego wykresu.
Example
Macierz „A” powinna być wypełniona tak, jakby między dwoma wierzchołkami istniała krawędź, to należy ją podać jako „1”, w przeciwnym razie „0”.
$$ A = \ begin {vmatrix} 0 & a & b & c & d \\ a & 0 & 1 & 1 & 1 \\ b & 1 & 0 & 0 & 1 \\ c & 1 & 0 & 0 & 1 \\ d & 1 & 1 & 1 & 0 \ end {vmatrix} = \ begin {vmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \ end {vmatrix} $$Korzystając z twierdzenia Kirchoffa, należy je zmienić, zastępując podstawowe wartości przekątnych stopniem wierzchołków, a wszystkie inne elementy - -1.
$$ = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = M $$ $$ M = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = 8 $$ $$ Co \: \: współczynnik \: \: z \: \: m1 \: \: = \ begin {vmatrix } 2 & 0 & -1 \\ 0 & 2 & -1 \\ - 1 & -1 & 3 \ end {vmatrix} $$Zatem liczba drzew rozpinających = 8.