3.2 Charakterizace stromů

Kombinace acykličnosti a souvislosti dává stromům několik unikátních vlastností a to umožňuje několik alternativních charakterizací stromů.

Věta 3.3 (o charakterizaci stromů)

Nechť \(G = (V, E)\) je graf. Pak následující tvrzení jsou ekvivalentní:

Důkaz (1) \(\implies\) (2)

(1) \(G\) je strom \(\implies\) (2) \(\forall\) 2 vrcholy \(u, v \in V\) \(\exists\) právě jedna \(u\)-\(v\)-cesta.

PS: Obrázek se dvěma rozcházejícími se cestami

Strom je souvislý, proto \(\forall x, y \in V\) \(\exists\) \(x\)-\(y\)-cesta.
Pro spor předpokládejme, že existují dva vrcholy \(u\) a \(v\), mezi kterými existují aspoň dvě různé cesty
\(P_{1} = a_{1}, ... , a_{k}\) a \(P_{2} = b_{1}, ... , b_{l}\) \((\)tedy \(a_{1} = b_{1} = u\) a \(a_{k} = b_{l} = v)\).
Nechť \(i \geq 1\) je nejmenší index takový, že \(a_{i} = b_{i}\) a \(a_{i+1} \neq b_{i+1}\).
Označme \(p, q > i\) takovou dvojici indexů, že \(a_{p} = b_{q}\) a \(\{a_{i+1}, . . . , a_{p−1}\} \cap \{b_{i+1}, . . . , b_{q−1}\} = \emptyset\).
Pak ale vrcholy \(\{a_{i}, a_{i+1}, . . . , a_{p−1}, a_{p}\}\) a \(\{b_{i+1}, . . . , b_{q−1}\}\) dohromady tvoří v \(G\) kružnici – SPOR

graph LR
u -- a1b1 --> a2/b2 --> ai/bi
ai/bi --> ai+1 --> a.. --> ap/bq
ai/bi --> bi+1 --> b.. --> ap/bq
ap/bq --> ... --> ak/bl/v

Důkaz (2) \(\implies\) (1)

(2) \(\forall 2\) vrcholy \(u, v \in V \exists\) právě jedna \(u\)-\(v\)-cesta \(\implies\) (1) \(G\) je strom.

Z předpokladu vyplývá, že \(G\) je souvislý.
Pokud by v \(G\) byla kružnice, tak by mezi nějakými dvěma jejími vrcholy existovaly alespoň dvě různé cesty, což je SPOR s předpokladem.
\(G\) je tedy strom.

Důkaz (1) \(\implies\) (3)

(1) \(G\) je strom \(\implies\) (3) \(G\) je souvislý a vynecháním libovolné hrany vznikne nesouvislý graf.

Souvislost \(G\) je splněna triviálně.
Předpokládejme pro spor, že existuje hrana \(e = \{u, v\} \in E\) taková, že graf \(G − e = (V, E \setminus \{e\})\) je souvislý.
Pak v \(G − e\) musí existovat \(u\)-\(v\)-cesta, která se ale po přidání hrany \(e\) stane v grafu \(G\) kružnicí, což je SPOR s předpokladem, že \(G\) je strom.

Důkaz (3) \(\implies\) (1)

(3) \(G\) je souvislý a vynecháním libovolné hrany vznikne nesouvislý graf \(\implies\) (1) \(G\) je strom

Souvislost \(G\) je splněna, stačí ukázat neexistenci kružnic v \(G\).
Předpokládejme pro spor, že:
- (1) vynecháním lib. hrany v \(G\) vznikne nesouvislý graf
- (2) \(G\) obsahuje kružnici \(C\).
Vyjmeme-li z \(G\) ale libovolnou hranu \(e = \{x, y\} \in C\), pak se \(G\) nerozpadne na dvě komponenty, protože jakékoliv cestě mezi libovolnými 2 vrcholy \(u\) a \(v\), která před tím obsahovala \(e\), poskytne \(C\) alternativní spojení.
Pro hrany kružnice \(C\) tudíž předpoklad (1) neplatí – dostali jsme SPOR.

Důkaz (1) \(\implies\) (4)

(1) \(G\) je strom \(\implies\) (4) \(G\) je souvislý a \(|V| = |E| + 1\)

Věta o trhání listů

Souvislost \(G\) je splněna triviálně.
Pro důkaz \(|V| = |E| + 1\) použijeme indukci podle \(|V|\).
Pro \(|V| = 1\) tvrzení platí triviálně. Předpokládejme \(|V| \gt 1\).
Dle Věty o existenci listů existuje v stromu \(G\) list \(v\).
Graf \(G' = G − v\) je dle Věty o trhání listů opět strom.
Dle indukčního předpokladu tedy platí \(|V(G')| = |E(G')| + 1\).
Vrátíme-li list \(v\) do grafu \(G\), zvýšíme počet vrcholů i počet hran o jedna. Proto
\(|V | = |V (G')| + 1 = (|E(G')| + 1) + 1 = |E| + 1\).

Důkaz (4) \(\implies\) (1)

Věta o trhání listů

(4) \(G\) je souvislý a \(|V| = |E| + 1\) \(\implies\) (1) \(G\) je strom

Indukcí podle \(|V|\). Pro \(|V| = 1\) tvrzení triviálně platí.
Ukážeme nejdříve, že z předpokladu plyne, že v \(G\) existuje list.
- Dle předpokladu platí \(\sum_{u \in V}deg_{G}(u) = 2|E| = 2|V| - 2\)
- Kdyby všechny stupně v \(G\) byly aspoň 2,
  pak \(\sum_{u \in V}deg_{G}(u) \geq 2|V|\)
- Tedy nějaký vrchol musí mít stupeň nejvýše 1. Označme ho \(v\).
- Protože \(G\) je souvislý, vrchol \(v\) nemůže mít stupeň 0.
- Vrchol \(v\) je tedy list.
Graf \(G' = G − v\) je souvislý a splňuje \(|V (G')| = |E(G')| + 1\), neboť jsme z \(G\) odebrali 1 vrchol a 1 hranu.
\(G'\) je tedy dle indukčního předpokladu strom.
Dle Věty o trhání listů je tedy \(G\) také strom