\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
