%
% 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=/*,*/