\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