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

\subchapter{Orientovan� grafy}{

% S

	\shortdef{Orientovan� graf}{$\Vec{G} = (V,\Vec{E})$,
		kde $V$ je libovoln� kone�n� mno�ina
		a $\Vec{E} \subseteq V \times V$.}

	\definition{
		$\deg^+ v = $ vstupn� stupe� $v$ $=$ po�et hran vedouc�ch do $v$.

		$\deg^- v = $ v�stupn� stupe� $v$ $=$ po�et hran vedouc�ch z $v$.
	}

	\example{
		$$\Vec{G} = (\{a,b,c\},\{(a,b),(b,b),(a,c),(c,a)\})$$

		\asciiart{
         <\
      _ *-/
      /| b
    /
a /
* -----> * c
  <-----
		}

		$$ \eqmalign{\deg^+a &= 1 &\qquad \deg^+ b &= 2\cr
		             \deg^-a &= 2 &\qquad \deg^- b &= 1} $$
	}

	\definition{
		$\Vec{G}$ je {\bf slab� souvisl�}, pokud
		$\forall x,y \in V$ existuje (neorientovan�)
		cesta z $x$ do $y$.
		$$x\bullet\to\bullet\leftarrow\bullet\to\bullet\leftarrow\bullet y$$

		$\Vec{G}$ je {\bf slab� souvisl�}, pokud
		$\forall x,y \in V$ existuje orientovan�
		cesta z $x$ do $y$.
		$$x\bullet\to\bullet\to\bullet\to\bullet\to\bullet y$$
	}

	\definition{
		Orientovan� graf $\Vec{G}$ je {\bf eulerovsk�}, pokud
		lze nakreslit jedn�m uzav�en�m orientovan�m tahem.

		$$ \cdots \to \bullet \to \bullet \to \cdots $$
	}

	\theorem{}{podm�nka eulerovsk�ho grafu}{
		$\Vec{G} = (V, \Vec{E})$ je eulerovsk�
		$\Longleftrightarrow$
		$\Vec{G}$ je slab� souvisl� a $\undernote{\forall v \in V: \deg^+v=\deg^-v}{(*)}$.

		\proof{
			\proofrightimpl{Z�ejm�.}
			\proofleftimpl{
				\lemma{}{Ka�dou hranou grafu spl�uj�c�ho $(*)$
					vede uzav�en� orientovan� tah.

					\proof{
						Nejdel�� orientovan� tah danou hranou je uzav�en�.
						Kdy� ho toti� vedeme, postupn� umaz�v�me hrany
						a~nakonec n�m podle rovnosti v $(*)$ zbyde jen
						posledn� hrana, kter� vede do $v$.

						\qed
					}
				}

				Nejdel�� uzav�en� orientovan� tah v $\Vec{G}$ je eulerovsk�.
				Jinak (obdobn� jako v neorientovan�m p��pad�, schematicky):
				\asciiart{
 /<-\
|    * nejdel�� uzav�en� orientovan� tah
 \->/
				}

				Po pou�it� lemmatu a odstran�n� hran tahu bychom v�ak na�li
				je�t� dal�� jin� uzav�en� orientovan� tah, d�ky souvislosti
				m� alespo� jeden spole�n� vrchol. Pak ale m��eme oba tahy
				propojit do jednoho del��ho uzav�en�ho tahu.

				\XXX
			}
		}
	}

}

\bend
