---
# System prepended metadata

title: Zajęcia 01.03.2021 - Drzewa
tags: [Informatyka 1PR, grafy]

---

# Zajęcia 01.03.2021 - Drzewa

###### tags: `Informatyka 1PR` `grafy`

<!-- | Nr  | Imię i nazwisko       | Ocena |
|:--- |:--------------------- |:----- |
| 1   | Wojciech Romanowski   |       |
| 2   | Kamil Żmudziński      |       |
| 3   | Jakub Zaszkodny       |       |
| 4   | Wojciech Reda         |       |
| 5   | Wojciech Rybak        |       |
| 6   | Jan Sas               |       |
| 7   | Alicja Rosińska       |       |
| 8   | Maciej Solecki        |       |
| 9   | Konrad Sobczak        |       |
| 10  | Mikołaj Sczogiel      |       |
| 11  | Radek Pałys           |       |
| 12  | Zuzanna Trzebiatowska |       |
 -->

---
<!-- :::danger -->
**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).
<!-- ::: -->
<!-- :::info -->
Intuicyjnie, cykl to po prostu "pętla" wierzchołków w grafie.
<!-- ::: -->

<!-- :::danger -->
**Definicja 2. Drzewo** to spójny graf acykliczny (nie posiadający cyklu).
<!-- ::: -->

<!-- :::info -->

```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."
}
```

<!-- ::: -->
---

<!-- :::info -->
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ę.
<!-- $$\tag*{$\blacksquare$}$$  -->

<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."
}
```

<!-- **Definicja 4.** -->