\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