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

\subchapter{Kreslen� grafu jedn�m tahem}{

\shortdef{Sled}{ $v_0, e_1, v_1, e_2, \ldots, e_n, v_n;\ e_i=\{v_{i-1},v_i\}$}
\shortdef{Tah}{ Sled, $e_i \not= e_j$ (pro $i\not=j$)}
\shortdef{Uzav�en� tah}{ Tah, $v_0 = v_m$}
\shortdef{``Cesta''}{ Tah, $v_i \not= v_j$}

\scpart{Eulerovsk� graf}{

	$G = (V,E)$ je {\bf Eulerovsk�} (lze nakreslit jedn�m uzav�en�m tahem),
	pokud existuje uzav�en� tah $v_0,e_1,\ldots,e_m,v_m$ takov�, �e:

	$$ \forall e \in E\ \onexists i:\ e=e_i\ \et\ \forall v \in V\ \existss i:\ v = v_i $$

	\theorem{}{}{

	$G$ je eulerovsk� graf, pr�v� kdy� je $G$ souvisl� a
	v�echny stupn� jsou sud�.

	\proof{
		\proofrightimpl{

		Uzav�en� eulerovsk� tah d�v� {\bf souvislost}
		(mezi ka�d�mi 2 vrcholy existuje tah, tedy i sled)
		i {\bf sud� stupn�} ($\deg v = 2|\{i \in \{1,\ldots,m\}:\ v = v_i\}|$).

		}

		\proofleftimpl{

		\shortdef{Pozorov�n�}{Pokud jsou v�echny stupn� sud�, ka�dou hranou vede uzav�en� tah.}
		\shortdef{D�kaz}{Nejdel�� tah danou hranou je nutn� uzav�en�. \sqed}

		$G = (V,E)$ souvisl�, v�echny stupn� sud�. Uk�eme (sporem), �e nejdel�� uzav�en�
		tah $T$ v $G$ je eulerovsk�.

		\shortdef{Co by bylo, kdyby nebyl}{Ze souvislosti v�me, �e existuje
			$v \in V(T),\ e \in E \setminus E(T),\ v \in e$.
			V grafu $G'=(V,E\setminus{}E(T))$ jsou v�echny stupn� sud�,
			tedy v $G'$ existuje uzav�en� tah $T'$, obsahuj�c� $e$.
		}

		Ve vrcholu $v$ propoj�me $T$, $T'$ do jednoho tahu. Schematicky:
		\TODO{Fig. D0}

		$\Rightarrow$ nov� del�� tah, ale $T$ m�l b�t nejdel��!

		\XXX

		}

	}
	}

}

}

\bend
