\input /home/pasky/school/fastex/lib.tex
%\caption{Uvod do teorie grafu}



\scpart{Definice}{
	Graf $G$ je uspořádaná dvojice $(V,E)$, kde $V$ je libovolná konečná
	množina (obecněji zcela libovolná) a $E \subseteq{} \cn{V}{2}$.
}


\shortdef{Úplný graf (na $n$ vrcholech)}{
	$$ K_{n} = (V, \cn{V}{2}) $$
}

\shortdef{Kružnice}{
	$$ C_{n} = (\{v_{1}, \ldots{}, v_{n}\}, \{\{v_{1},v_{2}\}, \{v_{2},v_{3}\}, \ldots{}, \{v_{n-1}, v_{n}\}, \{v_{n}, v_{1}\}\})\qquad n \ge 3 $$
}

\shortdef{Cesta}{
	$$ P_{n} = (\{v_{0}, \ldots{}, v_{n}\}, \{\{v_{0},v_{1}\}, \{v_{1},v_{2}\}, \ldots{}, \{v_{n-1}, v_{n}\}\}) $$
}

\shortdef{Sled}{
	$v_{0}, e_{1}, v_{1}, e_{2}, \ldots{}, e_{m}, v_{m}$, kde $e_{i} = \{ v_{i-1}, v_{i} \}$.
	(Cesta je tedy speciální druh sledu, kde jedním vrcholem neprojdeme vícekrát.)
}


\scpart{Úplný bipartitní graf $K_{n,m} = (V, E)$}{

	$$ V = \{ u_1, \ldots{}, u_{n}, v_{1}, \ldots{}, v_{m} \} $$
	$$ E = \{ \{u_{i},v_{j}\}:\ i = 1, \ldots{}, n;\ j = 1, \ldots{}, m \} $$
	$$ |V| = n + m,\ |E| = n \cdot m $$

\example{
	$K_{2,3}$:

	\asciiart{
*-\ * /-*
 \ X X /
  *-^-*
	}
}

}


\scpart{Bipartitní graf}{
	Graf $G = (V, E)$ takový, že:
	$$ V = \undernote{U \disjoin{} W}{V = U \cup{} W,\atop\scriptstyle U \cap{} W = 0} $$
	$$ E \subseteq{} \{ \{u,w\}:\ u \in{} U,\ w \in{} W \} $$
}


\scpart{Isomorfismus}{
	``Přejmenování vrcholů''

	$G \cong G'$ ($G$, $G'$ jsou {\bf{}izomorfní}), pokud existuje bijekce
	$ f\colon V(G) \bijection{} V(G') $ taková, že:

	$$ \{x, y\} \in{} E(G) \Leftrightarrow{} \{f(x), f(y)\} \in{} E(G') $$


	\shortnote{Izomorfismus je ekvivalence (reflexivní, symetrická, tranzitivní).}

}


\shortdef{Podgraf}{
	Graf $G'$ je {\bf{}podgrafem} grafu $G$ ($G' \subseteq{} G$), pokud $V(G') \subseteq{} V(G)$ a $E(G') \subseteq{} E(G)$.
}


\scpart{Indukovaný podgraf}{
	Graf $G'$ je {\bf{}indukovaným podgrafem} grafu $G$, pokud $V(G') \subseteq{} V(G)$ a $E(G') = E(G) \cap{} \cn{V(G')}{2}$.

\scpart{Pozorování}{
	Graf $G$ na $n$ vrcholech má $2^n$ indukovaných podgrafů
	(každá podmnožina $V$ {\bf{}indukuje} indukovaný podgraf).
}

}



\scpart{Souvislý graf}{

	Graf $G$ je {\bf{}souvislý}, pokud $\forall{x,y \in{} V(G)}$ existuje v $G$ cesta z $x$ do $y$: $x \pathin{G} y$.
	$\pathin{G}$ je ekvivalence na množině $V(G)$.

	\proof{
		Reflexivita a symetrie je zřejmá.

		Tranzitivita:
		$$ x \pathin{G} y \et y \pathin{G} z \Rightarrow{} \exists{\textbox{sled z $x$ do $z$}} $$
		Nejkratší sled z $x$ do $z$ je cesta $\Rightarrow{} x \pathin{G} z$.

		\qed
	}

	\note{
		$$ G \textbox{souvislý} \Leftrightarrow{} \forall{x, y \in{} V(G)}\ 
			\exists{\textbox{sled z $x$ do $y$ (v $G$)}} $$
	}

}

\scpart{Komponenta grafu $G$}{
	Podgraf indukovaný třídami ekvivalence $\pathin{G}$.

	\shortnote{$G$ souvislý $\Leftrightarrow$ má jednu komponentu.}

}


\scpart{Vzdálenost v grafu}{

	$$ x, y \in{} V(G),\ d_{G}(x,y) = \textbox{vzdálenost $x$, $y$ v $G$} = \textbox{délka nejkratší cesty z $x$ do $y$} $$

	\note{
		$ d_{G}(x,y) $ má vlastnosti metriky (vzdálenosti):

		$$ d_{G}(x,y) \ge{} 0 $$
		$$ d_{G}(x,y) = 0 \Leftrightarrow{} x = y $$
		$$ d_{G}(x,y) = d_{G}(y,x) $$
		$$ d_{G}(x,y) + d_{G}(y,z) \ge{} d_{G}(x,z) $$
	}

}

\shortdef{Sousedi v grafu}{
	$y$ je soused $x$ v $G$, pokud $\{x,y\} \in{} E(G)\ (\Leftrightarrow{} d_{G}(x,y) = 1)$.
}


\shortdef{Matice sousednosti}{
	$$ G = (\{v_1, \ldots{}, v_{n}\}, E):\ A_{G} = (a_{i,j})_{i,j=1}^{n},\ a_{i,j} =
		\cases{1&$\{v_{i},v_{j}\} \in{} E(G)$\cr
		       0&jinak} $$
}

\shortdef{Stupeň vrcholu}{
	Stupeň vrcholu $x$ v $G$ jest $\deg_{G}(x) = \deg(x) = $ počet hran obsahujících $x$ $=$ počet sousedů.
}

%\shortdef{Princip sudosti}{
%	$$ \forall{G = (V,E)}: \sum_{x \in{} V(G)} \deg_{G}(x) = 2|E| $$
%}

\bend