\input /home/pasky/school/fastex/lib.tex

\subchapter{Stromy}{

	\shortdef{Strom}{Souvislý graf bez kružnic.}

	\shortdef{List}{Vrchol stupně 1.}

	\lemma{}{
		Každý strom s alespoň 2 vrcholy má alespoň 2 listy.

		\proof{
			Koncové vrcholy nejdelší cesty jsou listy:

			\asciiart{
o - o - o - o - o - o - o - o - o - o
       /   /|  / \     /
      o   o o o   o   o
                      |
                      o
}

			Pokud by nebyly listy, existovala by hrana vedoucí
			do jiného vrcholu na cestě (ale pak by to byl cyklus),
			nebo do nového vrcholu, ale pak by původní graf nebyl souvislý.
		}

		\observation{
			$G$ graf, $v \in V(G)$ list. Pak:

			$$ G \textbox{strom} \Leftrightarrow G-v \textbox{strom} $$

			\proof{
				$$ G \textbox{souvislý} \Leftrightarrow G-v \textbox{souvislý} $$
				(zřejmé)

				$$ G \textbox{má kružnici} \Leftrightarrow G-v \textbox{má kružnici} $$
				(kružnice obsahuje samé vrcholy stupně alespoň 2)

				\qed
			}

			\scpart{Důsledek:}{
				$G$ strom ($|V(G)| \ge 1$) $\Longleftrightarrow$ z $G$ dostaneme $K_1 = \bullet$
				postupným odebíráním bodů.
			}
		}
	}

	\theorem{}{}{
		Nechť $G=(V,E)$ je graf. Pak následující tvrzení jsou ekvivalentní:
		\list{
		\listItem{$G$ je strom}
		\listItem{$\forall x,y \in V$: existuje právě jedna cesta z $x$ do $y$}
		\listItem{$G$ je souvislý, ale $G-e$ není souvislý pro $\forall e \in E$}
		\listItem{$G$ nemá kružnici a $G+e$ má kružnici pro $\forall e \in \cn{V}{2} \setminus E$}
		\listItem{$G$ je souvislý a $|V| = |E| + 1$}
		}

		\proof{
			\scpart{(i) $\Rightarrow$ (ii)}{
				$$ G \textbox{souvislý} \Longrightarrow \textbox{existuje cesta z $x$ do $y$} $$

				$$ G \textbox{bez kružnic} \Longrightarrow \textbox{neexistují 2 cesty z $x$ do $y$} $$

				Předpokládám $P_1,P_2$ různé cesty z $x$ do $y$:

				$$ \eqalign{P_1 &= x e_1 v_1 e_2 v_2 \cdots y\cr
				            P_2 &= x e_1' v_1' e_2' v_2' \cdots y} $$

				Nechť $i$ je minimální, pro které platí $e_i \ne e_i'$.

				Nechť $j \ge i$ je minimální, pro které $\existss k$ takové, že $v_j' = v_k$.

				Pak $v_{i-1} = v_{i-1}', v_i', \ldots, v_j' = v_k, v_{k-1}, \ldots, v_i$ tvoří kružnici.

				\XXX
			}

			\scpart{(ii) $\Rightarrow$ (iii)}{
				$e = \{x, y\}$

				$G - e$ není souvislý, jinak by existovaly dvě cesty z $x$ do $y$ (jedna v $G-e$, druhá $e$).
			}

			\scpart{(iii) $\Rightarrow$ (iv)}{
				Tvrdíme, že $G$ nemá kružnici. Pro spor tedy předpokládejme,
				že kružnici má. Potom vynecháním libovolné hrany kružnice
				se neporuší souvislost. To je ale spor s (iii).

				$G + e$ ($e = \{x,y\}$) má kružnici: $G$ je souvislý, tedy
				existuje cesta z $x$ do $y$ v $G$ a přímá hrana dotvoří
				kružnici.
			}

			\scpart{(iv) $\Rightarrow$ (i)}{
				$G$ souvislý: $x, y \in V$, existuje cesta z $x$ do $y$ v $G$?
				\list{
					\alistItem{$\{x,y\} \in E$: platí}
					\alistItem{$\{x,y\} \notin E$:
						$G+\{x,y\}$ má kružnici, která nebyla v $G$,
						tedy nutně prochází hranou $\{x,y\}$.
						Ostatní hrany kružnice tvoří cestu
						z~$x$ do $y$ v~$G$.
					}
				}
			}

			\scpart{(i) $\Rightarrow$ (v)}{
				$|V| = |E| + 1$: z předchozího důsledku.

				Odebráním listu odebereme právě jednu hranu,
				platnost rovnice se tedy nemění. Opakováním
				dostaneme jednovrcholový strom $K_1 = \bullet$,
				pro ten rovnice platí.
			}

			\scpart{(v) $\Rightarrow$ (i)}{
				$G = (V,E)$ souvislý, $|V| = |E| + 1$.

				$G$ nemá kružnici: nechť $G$ má kružnici;
				odebereme jednu její hranu, neporušíme
				souvislost. Má-li stále ještě nějakou kružnici,
				opět z ní odebereme hranu. To opakujeme,
				až dostaneme graf $G' = (V,E')$ souvislý
				bez kružnic (tedy strom $|V| = |E'| + 1$),
				$|E'| < |E|$. Ale předpoklad zněl, že
				$|V| = |E| + 1$.

				\XXX
			}
		}
	}

}

\bend