03 Charakterizace stromů
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
Charakterizace stromů
- Nechť $G=(V,E)$ je graf, pak následující tvrzení jsou ekvivalentní:
- $G$ je strom
- Pro každé 2 vrcholy $u, v \in V$ existuje právě jedna $s$-$v$-cesta
- Důkaz sporem: U více cest vznikne kružnice
- $G$ je souvislý a vynecháním libovolné hrany vznikne nesouvislý graf
- Důkaz sporem: Nelze odebrat, jinak by tam předtím musela být kružnice a tedy by to nebyl strom
- $G$ je souvislý a $|E| = |V|-1$
- Důkaz indukcí:
- IP: $|V(G’)| = |E(G’)+1$
- $|V(G)| = |V(G’)+1$
- $|V(G)| = |E(G’)+1$
- $\implies |V(G)| = |E(G)+1$
- Důkaz indukcí: