\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
