Zajęcia 01.03.2021 - Drzewa

# Zajęcia 01.03.2021 - Drzewa ###### tags: `Informatyka 1PR` `grafy`  ---  **Definicja 1.** Graf posiada **cykl** jeżeli istnieją jakieś dwa wierzchołki $u$, $v$ takie, że z $u$ do $v$ można przejść na więcej niż jeden sposób (nie cofając się po krawędziach).   Intuicyjnie, cykl to po prostu "pętla" wierzchołków w grafie.   **Definicja 2. Drzewo** to spójny graf acykliczny (nie posiadający cyklu).   ```graphviz graph G { // rankdir=LR // rank = same // layout=dot subgraph clusterA{ pencolor=white node [shape=circle]; 1 -- 2; 1 -- 3; 3 -- 4; 3 -- 5; labelloc=b; label="Przykład drzewa"; } subgraph clusterB { pencolor=white node [shape=circle]; 6 [label="1"]; labelloc=b; label="Drzewo jednowierzchołkowe" } subgraph clusterC { pencolor=white; node[shape=circle]; 7 [label="1"] 8 [label="2"] 9 [label="3"] 7 -- {8, 9} {rank=same; 8 -- 9} labelloc=b label="To nie jest drzewo" } label="Rysunek 1. Przykłady drzew." } ```  ---  Drzewa często pojawiały się już na zajęciach pod postacią drzewa wywołań rekurencyjnych (np. w zadaniu _Hetmany_), czy trochę bardziej ukryte drzewo "zaznaczane" przez algorytm **DFS**: ```graphviz graph G { node [shape=circle] 1 -- 2 [color="red", style="bold"] 2 -- 3 [color="red", style="bold"] 2 -- 4 [color="red", style="bold"] {rank = "same"; 3 -- 4 [style="dashed"; color="blue"]} 1 -- 5 [color="red", style="bold"] 5 -- 6 [color="red", style="bold"] 6 -- 7 [color="red", style="bold"] 6 -- 8 [color="red", style="bold"] 6 -- 9 [color="red", style="bold"] 5 -- 9 [style="dashed", color="blue"] 1 -- 7 [style="dashed", color="blue"] label="Rysunek 2. Przykład przejścia algorytmu DFS po drzewie.\nCzerwone krawędzie to te, po których przejdziemy w algorytmie DFS,\n niebieskie to te, po których algorytm nie przejdzie. Czerwone krawędzie\nwyznaczają drzewo." } ``` **Definicja 3. Liściem** w drzewie nazywamy każdy wierzchołek stopnia $1$. Bardziej matematycznie: wierzchołek $v$ jest **liściem** $\iff \deg{v} = 1$. **Twierdzenie 4.** Liczba krawędzi $N$-wierzchołkowego drzewa wynosi dokładnie $N - 1$. **Dowód:** Dowód przeprowadzimy przy pomocy indukcji matematycznej, ważnej metody w dowodzeniu wielu twierdzeń, nie tylko dotyczących drzew. Pokażemy najpierw, że teza jest prawdziwa dla $N = 1$. W zasadzie, to nie mamy czego pokazywać - takie drzewo jest tylko jedno, nie ma w ogóle krawędzi, zatem teza jest prawdziwa, gdyż $N - 1 = 1 - 1 = 0$. Załóżmy teraz, że teza jest prawdziwa dla wszystkich drzew $N$-wierzchołkowych. Pokażemy, że każde $N+1$ wierzchołkowe drzewo ma w takim razie dokładnie $N$ krawędzi. Wybierzmy dowolne $N+1$ wierzchołkowe drzewo. **Każde drzewo ma co najmniej jednego liścia (dlaczego?)**. Wyobraźmy sobie teraz, że wyrzucamy tego liścia z naszego drzewa. Dostajemy w takim razie drzewo, które ma $N$ wierzchołków. Założyliśmy, że teza zachodzi dla wszystkich $N$ wierzchołkowych drzew, zatem nasze drzewo ma dokładnie $N-1$ krawędzi. Przypomnijmy sobie teraz o wyrzuconym przez nas liściu i dołóżmy go z powrotem do naszego drzewa. Skoro to był liść, to znaczy, że wraz z nim dołożyliśmy dokładnie jedną krawędź. W takim razie krawędzi jest teraz $N - 1 + 1 = N$, co potwierdza naszą tezę.  <a name="rys3"></a> ```graphviz graph G { node [shape="circle"] 1--2 1--3 3--4 3--5 3--6 [style="dashed", color="red"] 2--7 6 [color="red"] label="Rysunek 3. Przykładowy rysunek obrazujący dowód dla pewnego 7-wierzchołkowego grafu.\n W \"czarnym\" grafie, z założenia mamy dokładnie 5 krawędzi. Po dołożeniu czerwonego\n wierzchołka i czerwonej krawędzi wracamy do pierwotnego grafu, dla którego teza\nrównież zachodzi." } ``` Pokazaliśmy w tym momencie dowodzie rzeczy: - teza zachodzi dla $N = 1$, - jeżeli teza zachodzi dla pewnego $N$, to zachodzi dla $N + 1$. To wystarczy, żeby udowodnić prawdziwość tezy dla dowolnego $N\in\mathbb{N}$. Skoro teza zachodzi dla $N = 1$, to z drugiego punktu zachodzi dla $N = 2$. Ale w takim razie zachodzi też dla $N = 3$ (znowu korzystając z drugiego punktu), więc zachodzi też dla $N = 4$, itd. \begin{align} ''1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 5 \Rightarrow \ldots'' \end{align} Indukcja po rozmiarze drzewa jest bardzo częstą i użyteczną metodą dowodzenia własności drzew. Będzie się jeszcze pojawiać w przyszłości, dlatego zachęcam do próby dokładnego zrozumienia powyższego dowodu.  --- Bardzo często i wygodnie będzie nam wyróżniać jeden wierzchołek drzewa. Taki wyróżniony wierzchołek nazywamy **korzeniem** drzewa. Najczęściej drzewa rysujemy z korzeniem u szczytu i z wierzchołkami spadającymi w dół. #### Od tego momentu zakładamy, że każde roważane przez nas drzewo jest ukorzenione. **Fakt 4.** W drzewie, z każdego wierzchołka do każdego innego istnieje dokładnie jedna ścieżka. To twierdzenie również można udowodnić indukcyjnie. Zachęcam Was do samodzielnego spróbowania. **Definicja 5.** **Ojcem** wierzchołka $v$ w ukorzenionym drzewie jest pierwszy wierzchołek "nad" nim na ścieżce od $v$ do korzenia. Analogicznie definiujemy kolejne pojęcie: **synem** wierzchołka $v$ są wszystkie wierzchołki, dla których jest on ojcem. Na [rysunku 3](#rys3) ojcem wierzchołka $3$ jest wierzchołek $1$, a jego synami są wierzchołki $4, 5, 6$. **Definicja 6.** Wierzchołek $u$ jest **Przodkiem** wierzchołka $v$, jeżeli $u$ jest ojcem $v$ lub $u$ jest przodkiem ojca $v$ (czyli ojcem ojca ojca... ojca $v$). Mówimy, że $v$ jest **potomkiem** $u$ kiedy $u$ jest potomkiem $v$. Zauważ, że przodkowie wierzchołka to wszystkie wierzchołki leżące na ścieżce od tego wierzchołka do korzenia. **Definicja 7.** W ukorzenionym dzrzewie, **poddrzewem** wierzchołka $v$ nazwiemy graf złożony z wierzchołka $v$ i wszystkich jego potomków. ```graphviz graph G { node [shape="circle"] 1 -- 2 2 -- 5 5 -- 6 [color="red"] 5 -- 7 [color="red"] 1 -- 8 8 -- 9 2 -- 10 5 -- 11 [color="red"] 7 -- 3 [color="red"] 7 -- 4 [color="red"] 9 -- 12 5 [color="red"] 6 [color="red"] 7 [color="red"] 11 [color="red"] 4 [color="red"] 3 [color="red"] label="Rysunek 4. Czerwonym kolorem zostało oznaczone poddrzewo wierzchołka 5." } ```