%
% 02-priklady.tex
%
% Developed by Ondrej Jombik <nepto@platon.sk>
% Copyright (c) 2003 Platon SDG, http://platon.sk/
% Licensed under terms of GNU General Public License.
% All rights reserved.
%
% Changelog:
% 07/06/2003 - created
%

% $Platon$

\begin{example} % /* #1

Dok�te, �e �ubovo�n� dve najdlh�ie cesty v~s�vislom grafe maj� spolo�n�
vrchol. Maj� spolo�n� aj hranu?

\end{example} % */

\begin{solution} % /*

Dok�eme sporom. Majme cesty $a$~a~$b$, ktor� nemaj� spolo�n� vrchol.

\inputImage{picture1}{0.5\textwidth}{images/picture1}{Cesty $a$ a $b$
bez spolo�n�ho vrchola.}

Ke�e graf je spojit�, potom existuje cesta medzi ka�d�m bodom na
ceste~$a$ a ka�d�m bodom na ceste~$b$. Spojme teda bod v~polovici
cesty~$a$ s bodom v~polovici cesty~$b$. Takto vytvoren� spojnica je
dlh�ia ako cesta~$a$ alebo dlh�ia ako cesta~$b$, �o je spor
s~predpokladom, �e cesty $a$~a~$b$ s� najdlh�ie.

Spolo�n� hranu nemaj�. D�kaz kontrapr�kladom.

\inputImage{picture2}{0.2\textwidth}{images/picture2}{Dve najdlh�ie
cesty bez spolo�nej hrany.}

\end{solution} % */

\begin{example} % /* #2

Dok�te, �e ka�d� graf $G$ obsahuje cestu d�ky $\delta(G)$ a kru�nicu
d��ky aspo� $\delta(G) + 1$ (pre $\delta(G) \ge 2$).

\end{example} % */

\begin{solution} % /*

Nech $x_0, \dots, x_k$ je najdlh�ia cesta v~grafe~$G$. Potom v�etci
susedia vrcholu~$x_k$ le�ia na tejto ceste. Ak by nele�ali, nebola by to
najdlh�ia cesta. Z~toho potom vypl�va, �e $k \ge d(x_k) \ge \delta(G)$.
Ak $i < k$ je minim�lne a $(x_i, x_k) \in E(G)$, potom $x_i, \dots, x_k,
x_i$ je cyklus d��ky aspo�~$\delta(G) + 1$.

\end{solution} % */

\begin{example} % /* #3

Dok�te alebo vyvr�te nasleduj�ce tvrdenia.

\begin{enumerate}
	\item Ka�d� uzavret� sled p�rnej d�ky obsahuje kru�nicu p�rnej
		d�ky.
	\item Ka�d� uzavret� sled nep�rnej d�ky obsahuje kru�nicu nep�rnej
		d�ky.
\end{enumerate}

\end{example} % */

\begin{solution} ~ % /*

\begin{enumerate}
	\item Neplat�. D�kaz kontrapr�kladom.
		\inputImage{picture3}{0.3\textwidth}{images/picture3}{Dve
		kru�nice nep�rnej d�ky.}
	\item Plat�. Uva�ujme uzavret� sled obsahuj�ci len kru�nice p�rnej
		d�ky.  D�ka tohto sledu je v�dy p�rna. Tak�e neexistuje
		uzavret� sled nep�rnej d�ky, ktor� by obsahoval len kru�nice
		p�rnej d�ky. Potom ale ka�d� uzavret� sled nep�rnej d�ky mus�
		obsahova� kru�nicu nep�rnej d�ky.

\end{enumerate}

\end{solution} % */

\begin{example} % /* #4

Dok�te, �e komplement�rny graf k~nes�visl�mu grafu je s�visl�.

\end{example} % */

\begin{solution} % /*

Bez ujmy na v�eobecnosti predpokladajme, �e m�me graf~$G$ skladaj�ci sa
z~dvoch kompletn�ch komponentov~$A$~a~$B$. Graf~$G$ je teda nes�visl�.
V~komplement�rnom grafe~$G^{'}$ bude ka�d� vrchol komponentu~$A$ spojen�
s~ka�d�m vrcholom komponentu~$B$. �i�e pre ka�d� vrchol z~$A$ plat�, �e
z~neho existuje cesta d�ky~$1$ do~�ubovo�n�ho vrcholu z~$B$ a cesta
d�ky najviac~$2$ do~�ubovo�n�ho vrcholu z~$A$. Analogicky
pre~komponent~$B$.

Ke�e z~ka�d�ho vrcholu grafu~$G^{'}$ existuje cesta do �ubovo�n�ho
vrcholu, graf~$G^{'}$ je s�visl�. Obdobne tvrdenie plat� aj pre
grafy~$G$ skladaj�ce sa z~viac ako dvoch komponentov.

\end{solution} % */

\begin{example} % /* #5

Ur�ite priemern� stupe�, po�et hr�n, priemer, polomer, obvod a d�ku
najdlh�ej kru�nice v~$n$-rozmernej kocke. Ko�ko r�znych najkrat��ch
ciest existuje medzi dan�mi vrcholmi v $n$-rozmernej kocke?

\end{example} % */

\begin{solution} % /*
	TODO
\end{solution} % */

\begin{example} % /* #6

Dok�te, �e ak $G$ je jednoduch� graf s~$\delta(G) \ge \frac{n - 1}{2}$,
potom je s�visl�.

\end{example} % */

\begin{solution} % /*

Sporom. Nech graf~$G$ nie je s�visl�. Zoberme najmen�iu komponentu~$A$.
T� m� najviac $\frac{n}{2}$~vrcholov. Potom ale $\delta(A) \le
\frac{n}{2} - 1$.

\end{solution} % */

\begin{example} % /* #7

Dok�te, �e ak graf~$G$ je samokomplement�rny graf r�du~$n$, tak
$n~mod~4 = 0$ alebo $n~mod~4 = 1$. N�jdite aspo� 3 samokomplement�rne
grafy.

\end{example} % */

\begin{solution} % /*

Ak je graf samokomplement�rny, jeho doplnok je s~n�m izomorfn�. Ak je
graf r�du~$n$, znamen� to, �e $|V(G)| = |G| = n$.

Zoberme kompletn� graf~$K_n$ r�du~$n$. Po�et jeho hr�n je~$\frac{n (n -
1)}{2}$. Po�et hr�n v~samokomplement�rnom grafe mus� by� p�rny
(polovi�n�), tak�e plat� $\frac{n (n - 1)}{2}~mod~2 = 0$, resp. $n (n -
1)~mod~4 = 0$. �i�e bu� $n~mod~4 = 0$ alebo $n~mod~4 = 1$.

Najmen�� samokomplement�rny graf vyzer� nasledovne.

\inputImage{picture4}{0.3\textwidth}{images/picture4}{Najmen��
samokomplement�rny graf.}

In� pr�klady samokomplement�rnych grafov.

\begin{tabular}{r @{~} c @{~} l}
	$K_n$				& --	& kompletn� graf r�du~$n$		\\
	$\overline{K_n}$	& --	& doplnok ku kompletn�mu grafu (len mno�ina bodov)
\end{tabular}

\inputImage{picture5}{0.5\textwidth}{images/picture5}{Samokomplement�rny~graf.}

\inputImage{picture6}{1.1\textwidth}{images/picture6}{Samokomplement�rny~graf.}

\end{solution} % */

\begin{example} % /* #8

Dok�te, �e v~ka�dom s�vislom grafe existuje dominujuca mno�ina, ktorej
doplnok je dominuj�ca mno�ina.

Dominuj�ca mno�ina grafu~$G$ je tak� podmno�ina vrcholov, �e plat�:

$$
(\forall v \in V(G)) ~ ((v \notin D) \Rightarrow \exists u \in D: (v, u) \in E(G))
$$

\end{example} % */

\begin{solution} % /*

V~dominuj�cej mno�ine~$D$ grafu~$G$ m��e by� len tak� vrchol~$v$,
ktor�ho susedn� vrcholy v~tejto mno�ine nie s�. Ke�e graf~$G$ je
s�visl�, tak $D$ je minim�lne pokrytie.

Doplnok dominuj�cej mno�iny $D^{'} = V(G) - D$ je taktie� dominuj�ca
mno�ina, preto�e $(\forall u \in D) ~ (\exists v \in D^{'}: (u, v) \in
E(G))$.

\end{solution} % */

\begin{example} % /* #9

Nech $M$ a $N$ s� disjunktn� p�renia grafu~$G$, pri�om plat�
$|M|~>~|N|$. Uk�te, �e existuj� p�renia $M^{'}$~a~$N^{'}$ grafu~$G$
s~nasleduj�cimi vlastnos�ami.

$
\begin{array}{ll}
	1.	& |M^{'}| = |M| - 1				\\
	2.	& |N^{'}| = |N| + 1				\\
	3.	& M^{'} \cup N^{'} = M \cup N	\\
\end{array}
$

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #10

Graf~$G$ je zjednoten�m dvoch hranovo disjunktn�ch kostier. Je hranovo
$2$-s�visl�? Je $2$-s�visl�?

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #11

Nech $A$ je matica susednosti jednoduch�ho grafu. Nech �alej $A^k =
\underbrace{A \cdot A \cdot A \cdots A}_{k}$. Dok�te, �e~$a_{i,j}^k$ je
rovn� po�tu sledov d�ky~$k$, sp�jaj�cich vrcholy $v_i$ a $v_j$. Plat�
toto tvrdenie pre �ubovo�n� graf (s n�sobn�mi hranami a slu�kami)?

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #12

Dok�te, �e ka�d� strom m� nanajv�� jeden $1$-faktor.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #13

Dok�te, �e ak graf~$G$ je $k$-s�visl�, tak potom aj hranov� graf~$L(G)$
je $k$-s�visl�.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #14

Dok�te, �e ka�d� Cayleyho graf je s�visl�.

Majme grupu~$(G, \circ)$ a mno�inu~$X$ tak�, �e $X \subseteq G$. Nech pre
mno�inu~$X$ plat�

\begin{enumerate}
	\item $e \notin X$
	\item $x \in X \Rightarrow x^{-1} \in X$
	\item $\langle X \rangle = G$
\end{enumerate}

Potom {\it Cayleyho graf}~$C(G, X)$ generovan� grupou~$(G, \circ)$ a
mno�inou~$X$ je tak� graf, kde plat�

$$
V(C) = G ~\land~ (a, b) \in E(C) ~\Leftrightarrow~ a^{-1} \circ b \in X
$$

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #15

Dok�te, �e strom~$T$ m� $1$-faktor pr�ve vtedy, ke� plat�

$$
\forall v \in V(T):~ q(T - v) = 1
$$

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #16

Dok�te, �e graf, ktor� m� most nem� $1$-faktoriz�ciu (okrem trivi�lneho
pr�padu, �e graf s�m je $1$-faktorom).

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #17

Dok�te, �e pre $k$-kritick� graf plat� $\delta(G) \ge k - 1$.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #18

Dok�te, �e v $k$-kritickom grafe �iadny vrcholov� rez neindukuje kliku.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #19

Dok�te, �e ak $T$ a $R$ s� kostry $v$-vrcholov�ho grafu~$G$, tak
existuje postupnos� kostier

$$
T = T_0, T_1, \dots, T_n = R
$$

kde $T_i$ a $T_{i+1}$ maj� $v - 2$ spolo�n�ch hr�n pre $i = 0, 1, \dots,
n - 1$.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #20

Uk�te, �e ak $u$ a $v$ s� 2 r�zne vrcholy kritick�ho grafu, tak plat�
$N_G(u) \notsubseteq N_G(v)$ a $N_G(v) \notsubseteq N_G(u)$.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #21

Dok�te, �e pre �ubovo�n� graf~$G$ r�du~$n$ plat�

$$
\frac{n}{\alpha(G)} \le \chi(G) \le n - \alpha(G) + 1
$$

Majme mno�inu vrcholov~$N$ grafu~$G$. Ak $N$ indukuje bezhranov� graf,
potom mno�inu~$N$ naz�vame {\it nez�visl� mno�ina}. Po�et vrcholov
najv��ej nez�vislej mno�iny ozna�ujeme~$\alpha(G)$.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #22

Dok�te, �e ak $G$ je $r$-regul�rny graf nep�rneho r�du, tak plat�
$\chi^{'}(G) = r + 1$.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #23

Dok�te, �e pre ka�d� kubick� graf~$G$ s� nasleduj�ce tvrdenia
ekvivalentn�.

\begin{enumerate}
	\item $\chi^{'}(G) = 3$
	\item $G$ m� p�rny $2$-faktor
	\item pre ka�d� hranu~$e$ grafu~$G$ existuje p�rny $2$-faktor
		grafu~$G$, ktor� obsahuje t�to hranu
\end{enumerate}

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #24

Dok�te, �e ak~$G$ je jednozna�ne hranovo $3$-zafarbite�n� kubick� graf,
tak zjednotenie �ubovo�n�ch dvoch farebn�ch tried tvor� Hamiltonovsk�
kru�nicu.

Graf sa naz�va jednozna�ne hranovo $k$-zafarbite�n�, ak je
$k$-zafarbite�n� a pre ka�d� dve zafarbenia plat�, �e m��eme dosta�
jedno z~druh�ho permut�ciou farieb.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

\begin{example} % /* #25

{\it Paritn� lema.} Nech~$G$ je kubick� graf hranovo zafarben� tromi
farbami $1$, $2$ a $3$. �alej nech $S \subseteq E(G)$ je hranov� rez
grafu~$G$, pri�om~$|S| = n$ a $n_i$ je po�et hr�n z~$S$ farby~$i$. Potom plat�
$n_1 \equiv n_2 \equiv n_3 \equiv n ~(mod~2)$.

\end{example} % */

% \begin{solution} % /*
%	TODO
% \end{solution} % */

% vim: ts=4
% vim600: fdl=0 fdm=marker fdc=0 fmr=/*,*/

