Součásti dokumentu 01ZTGA
Zdrojový kód
%\wikiskriptum{01ZTGA}
\section{Jednotažky}
Název kapitoly neformálně vystihuje vlastnost tzv. eulerovských grafů,
které je možné nakreslit jedním tahem. Vše, co bude řečeno o eulerovských
grafech, lze aplikovat i na zobecněné grafy ve smyslu definice \ref{def:zobecneny_graf}.
\begin{notation}
Buď $G=(V,E)$ graf, $v_{0},v_{1},...,v_{k}$ sled v $G$. Potom tento
sled zapisujeme také jako $v_{0}e_{1}v_{1}e_{2}v_{2}...e_{k}v_{k}$,
přičemž $\left(\forall i\in\{1,2,...,k\}\right)\left(e_{i}=\{ v_{i-1},v_{i}\}\right).$
\end{notation}
\begin{defn}
Graf $G=(V,E)$, resp. $G=(V,E,\varphi)$, se nazývá \textbf{eulerovský}
(angl. \emph{eulerian}), existuje-li v něm ,,eulerovský{}`` cyklus
(angl. \emph{Euler tour}) $v_{0}e_{1}v_{1}e_{2}v_{2}...e_{m}v_{m}$
takový, že \[
\left(\forall i,j\in\{1,2,...,m\}\right)\left(i\neq j\Rightarrow e_{i}\neq e_{j}\}\right)\]
a $E=\{ e_{1},...,e_{m}\}$, tj. $m=\# E$.
\end{defn}
\begin{rem*}
Řekneme, že sled $v_{0}e_{1}v_{1}e_{2}v_{2}...e_{k}v_{k}$ je \textbf{tah}
(angl. \emph{trail}) v $G$, jestliže \[
\left(\forall i,j\in\{1,2,...,k\}\right)\left(i\neq j\Rightarrow e_{i}\neq e_{j}\}\right).\]
\end{rem*}
\begin{thm}
\label{thm:eulerovske-grafy}Buď $G=(V,E)$ souvislý graf. Potom $G$
je eulerovský, právě když $\left(\forall v\in V\right)(d(v)$ je sudý$)$.
\end{thm}
\begin{proof}
$\boxed{{\Rightarrow:}}$
$G$ je eulerovský, v $G$ tedy existuje cyklus, který projde všechny
hrany, a to každou právě jednou. Půjdeme-li po tomto cyklu, je zřejmé,
že vstoupíme do každého vrcholu právě tolikrát, kolikrát z něj vystoupíme,
a to nikdy po hraně, po které jsme již prošli. Z toho plyne, že na
každý vrchol je napojen sudý počet hran.
$\boxed{{\Leftarrow:}}$
Když má každý vrchol sudý stupeň, tak jeden ($v_{1}$) vybereme a
vydáme se po libovolné hraně, která z něj vede. Z vrcholu, do nějž
jsme se dostali, pokračujeme stejným způsobem dál. Přitom za sebou
obarvujeme hrany a nikdy se nevydáme po hraně, která je již obarvená.
Je zřejmé, že jediný vrchol, z nějž už nebudeme schopni pokračovat
dál, je ten, ze kterého jsme začínali. Potom už jsme buď prošli všechny
hrany, nebo z několika vrcholů vede nenulový, ale sudý počet dosud
neobarvených hran. Vybereme jeden ($v_{2}$) takový, který leží na
cyklu, který jsme již obarvili (to musí být možné, jinak by graf nebyl
souvislý). Z něj začneme nový cyklus. Po jeho dokončení oba cykly
sjednotíme, a to tak, že původní cyklus začneme ve $v_{1}$, přerušíme
jej ve $v_{2}$, provedeme druhý cyklus, a následně dokončíme cyklus
původní. Úvahu lze opakovat, dokud existují neobarvené hrany. Právě
popsaný postup je znázorněn na obrázku \ref{cap:eulerovska_cesta}.%
\begin{figure}
\begin{center}
%Title: euler.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 22:07:04 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,.56}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 4.523 22.623
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,1,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.618 26.134
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{1,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.773 25.303
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.305}}} at 2.362 22.246
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.305}}} at 4.801 22.856
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.305}}} at 4.191 24.685
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.305}}} at 2.362 24.380
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.305}}} at 2.362 26.209
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.305}}} at 0.533 25.294
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,.56}\plot 4.523 22.623 4.521 22.621 /
\plot 4.521 22.621 4.519 22.614 /
\plot 4.519 22.614 4.513 22.604 /
\plot 4.513 22.604 4.504 22.587 /
\plot 4.504 22.587 4.492 22.566 /
\plot 4.492 22.566 4.475 22.536 /
\plot 4.475 22.536 4.453 22.500 /
\plot 4.453 22.500 4.430 22.460 /
\plot 4.430 22.460 4.403 22.415 /
\plot 4.403 22.415 4.371 22.365 /
\plot 4.371 22.365 4.337 22.312 /
\plot 4.337 22.312 4.301 22.257 /
\plot 4.301 22.257 4.261 22.200 /
\plot 4.261 22.200 4.219 22.142 /
\plot 4.219 22.142 4.172 22.083 /
\plot 4.172 22.083 4.123 22.024 /
\plot 4.123 22.024 4.070 21.965 /
\plot 4.070 21.965 4.013 21.905 /
\plot 4.013 21.905 3.952 21.846 /
\plot 3.952 21.846 3.886 21.787 /
\plot 3.886 21.787 3.812 21.725 /
\plot 3.812 21.725 3.732 21.666 /
\plot 3.732 21.666 3.645 21.605 /
\plot 3.645 21.605 3.552 21.548 /
\plot 3.552 21.548 3.452 21.493 /
\plot 3.452 21.493 3.351 21.442 /
\plot 3.351 21.442 3.251 21.400 /
\plot 3.251 21.400 3.158 21.361 /
\plot 3.158 21.361 3.073 21.328 /
\plot 3.073 21.328 2.997 21.302 /
\plot 2.997 21.302 2.932 21.281 /
\plot 2.932 21.281 2.874 21.262 /
\plot 2.874 21.262 2.828 21.249 /
\plot 2.828 21.249 2.788 21.239 /
\plot 2.788 21.239 2.754 21.230 /
\plot 2.754 21.230 2.724 21.224 /
\plot 2.724 21.224 2.699 21.217 /
\plot 2.699 21.217 2.673 21.213 /
\plot 2.673 21.213 2.650 21.211 /
\plot 2.650 21.211 2.625 21.209 /
\plot 2.625 21.209 2.595 21.207 /
\plot 2.595 21.207 2.561 21.205 /
\putrule from 2.561 21.205 to 2.521 21.205
\putrule from 2.521 21.205 to 2.474 21.205
\putrule from 2.474 21.205 to 2.417 21.205
\putrule from 2.417 21.205 to 2.352 21.205
\plot 2.352 21.205 2.278 21.209 /
\plot 2.278 21.209 2.193 21.215 /
\plot 2.193 21.215 2.102 21.224 /
\plot 2.102 21.224 2.004 21.237 /
\plot 2.004 21.237 1.905 21.253 /
\plot 1.905 21.253 1.808 21.277 /
\plot 1.808 21.277 1.719 21.302 /
\plot 1.719 21.302 1.636 21.332 /
\plot 1.636 21.332 1.564 21.357 /
\plot 1.564 21.357 1.503 21.385 /
\plot 1.503 21.385 1.450 21.408 /
\plot 1.450 21.408 1.405 21.429 /
\plot 1.405 21.429 1.369 21.446 /
\plot 1.369 21.446 1.340 21.463 /
\plot 1.340 21.463 1.317 21.476 /
\plot 1.317 21.476 1.295 21.488 /
\plot 1.295 21.488 1.278 21.501 /
\plot 1.278 21.501 1.264 21.512 /
\plot 1.264 21.512 1.249 21.524 /
\plot 1.249 21.524 1.236 21.537 /
\plot 1.236 21.537 1.219 21.554 /
\plot 1.219 21.554 1.200 21.573 /
\plot 1.200 21.573 1.179 21.596 /
\plot 1.179 21.596 1.156 21.626 /
\plot 1.156 21.626 1.126 21.662 /
\plot 1.126 21.662 1.092 21.704 /
\plot 1.092 21.704 1.056 21.753 /
\plot 1.056 21.753 1.014 21.812 /
\plot 1.014 21.812 0.972 21.878 /
\plot 0.972 21.878 0.931 21.950 /
\plot 0.931 21.950 0.891 22.028 /
\plot 0.891 22.028 0.857 22.109 /
\plot 0.857 22.109 0.830 22.189 /
\plot 0.830 22.189 0.809 22.265 /
\plot 0.809 22.265 0.790 22.335 /
\plot 0.790 22.335 0.777 22.396 /
\plot 0.777 22.396 0.766 22.451 /
\plot 0.766 22.451 0.758 22.500 /
\plot 0.758 22.500 0.751 22.540 /
\plot 0.751 22.540 0.745 22.574 /
\plot 0.745 22.574 0.743 22.602 /
\plot 0.743 22.602 0.741 22.627 /
\plot 0.741 22.627 0.739 22.650 /
\putrule from 0.739 22.650 to 0.739 22.672
\putrule from 0.739 22.672 to 0.739 22.695
\plot 0.739 22.695 0.741 22.716 /
\plot 0.741 22.716 0.743 22.741 /
\plot 0.743 22.741 0.747 22.771 /
\plot 0.747 22.771 0.754 22.807 /
\plot 0.754 22.807 0.764 22.847 /
\plot 0.764 22.847 0.775 22.896 /
\plot 0.775 22.896 0.792 22.953 /
\plot 0.792 22.953 0.813 23.017 /
\plot 0.813 23.017 0.838 23.089 /
\plot 0.838 23.089 0.870 23.167 /
\plot 0.870 23.167 0.908 23.252 /
\plot 0.908 23.252 0.953 23.336 /
\plot 0.953 23.336 1.003 23.419 /
\plot 1.003 23.419 1.058 23.497 /
\plot 1.058 23.497 1.118 23.571 /
\plot 1.118 23.571 1.177 23.639 /
\plot 1.177 23.639 1.238 23.700 /
\plot 1.238 23.700 1.302 23.755 /
\plot 1.302 23.755 1.363 23.806 /
\plot 1.363 23.806 1.425 23.855 /
\plot 1.425 23.855 1.488 23.897 /
\plot 1.488 23.897 1.552 23.940 /
\plot 1.552 23.940 1.615 23.978 /
\plot 1.615 23.978 1.676 24.011 /
\plot 1.676 24.011 1.740 24.045 /
\plot 1.740 24.045 1.799 24.075 /
\plot 1.799 24.075 1.856 24.105 /
\plot 1.856 24.105 1.911 24.130 /
\plot 1.911 24.130 1.962 24.153 /
\plot 1.962 24.153 2.007 24.172 /
\plot 2.007 24.172 2.047 24.189 /
\plot 2.047 24.189 2.079 24.204 /
\plot 2.079 24.204 2.102 24.213 /
\plot 2.102 24.213 2.121 24.221 /
\plot 2.121 24.221 2.134 24.225 /
\plot 2.134 24.225 2.140 24.227 /
\plot 2.140 24.227 2.142 24.229 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,.56}\plot 2.142 24.229 4.225 22.860 /
%
% arrow head
%
\plot 3.717 23.012 4.225 22.860 3.884 23.266 /
%
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,1,0}\plot 4.106 24.886 4.047 24.469 /
\plot 4.047 24.469 4.523 22.981 /
\plot 4.523 22.981 2.559 22.504 /
\putrule from 2.559 22.504 to 2.559 24.587
\plot 2.559 24.587 3.810 24.826 /
\plot 3.810 24.826 2.559 25.838 /
%
% arrow head
%
\plot 3.050 25.637 2.559 25.838 2.858 25.400 /
%
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,1,0}\plot 2.618 26.134 2.623 26.137 /
\plot 2.623 26.137 2.629 26.139 /
\plot 2.629 26.139 2.644 26.145 /
\plot 2.644 26.145 2.665 26.151 /
\plot 2.665 26.151 2.695 26.164 /
\plot 2.695 26.164 2.733 26.179 /
\plot 2.733 26.179 2.781 26.198 /
\plot 2.781 26.198 2.838 26.219 /
\plot 2.838 26.219 2.904 26.242 /
\plot 2.904 26.242 2.976 26.268 /
\plot 2.976 26.268 3.054 26.295 /
\plot 3.054 26.295 3.137 26.325 /
\plot 3.137 26.325 3.224 26.352 /
\plot 3.224 26.352 3.313 26.382 /
\plot 3.313 26.382 3.404 26.410 /
\plot 3.404 26.410 3.495 26.437 /
\plot 3.495 26.437 3.586 26.460 /
\plot 3.586 26.460 3.675 26.484 /
\plot 3.675 26.484 3.763 26.503 /
\plot 3.763 26.503 3.852 26.520 /
\plot 3.852 26.520 3.939 26.532 /
\plot 3.939 26.532 4.024 26.541 /
\plot 4.024 26.541 4.106 26.545 /
\plot 4.106 26.545 4.187 26.543 /
\plot 4.187 26.543 4.263 26.535 /
\plot 4.263 26.535 4.337 26.522 /
\plot 4.337 26.522 4.407 26.501 /
\plot 4.407 26.501 4.468 26.471 /
\plot 4.468 26.471 4.523 26.433 /
\plot 4.523 26.433 4.574 26.380 /
\plot 4.574 26.380 4.610 26.319 /
\plot 4.610 26.319 4.633 26.251 /
\plot 4.633 26.251 4.646 26.179 /
\plot 4.646 26.179 4.648 26.105 /
\plot 4.648 26.105 4.642 26.027 /
\plot 4.642 26.027 4.627 25.948 /
\plot 4.627 25.948 4.606 25.866 /
\plot 4.606 25.866 4.578 25.783 /
\plot 4.578 25.783 4.547 25.701 /
\plot 4.547 25.701 4.511 25.616 /
\plot 4.511 25.616 4.470 25.529 /
\plot 4.470 25.529 4.428 25.444 /
\plot 4.428 25.444 4.386 25.362 /
\plot 4.386 25.362 4.341 25.284 /
\plot 4.341 25.284 4.299 25.207 /
\plot 4.299 25.207 4.259 25.138 /
\plot 4.259 25.138 4.223 25.074 /
\plot 4.223 25.074 4.189 25.021 /
\plot 4.189 25.021 4.161 24.977 /
\plot 4.161 24.977 4.140 24.941 /
\plot 4.140 24.941 4.125 24.915 /
\plot 4.125 24.915 4.115 24.898 /
\plot 4.115 24.898 4.108 24.890 /
\plot 4.108 24.890 4.106 24.886 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{1,0,0}\plot 0.773 25.303 2.201 26.016 /
\putrule from 2.201 26.016 to 2.201 24.646
\plot 2.201 24.646 0.953 25.241 /
%
% arrow head
%
\plot 1.477 25.160 0.953 25.241 1.346 24.885 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.191 24.685 4.193 24.689 /
\plot 4.193 24.689 4.199 24.697 /
\plot 4.199 24.697 4.208 24.712 /
\plot 4.208 24.712 4.223 24.737 /
\plot 4.223 24.737 4.244 24.771 /
\plot 4.244 24.771 4.271 24.816 /
\plot 4.271 24.816 4.303 24.869 /
\plot 4.303 24.869 4.339 24.932 /
\plot 4.339 24.932 4.379 25.002 /
\plot 4.379 25.002 4.424 25.080 /
\plot 4.424 25.080 4.470 25.163 /
\plot 4.470 25.163 4.517 25.252 /
\plot 4.517 25.252 4.564 25.343 /
\plot 4.564 25.343 4.608 25.434 /
\plot 4.608 25.434 4.650 25.527 /
\plot 4.650 25.527 4.688 25.620 /
\plot 4.688 25.620 4.724 25.711 /
\plot 4.724 25.711 4.754 25.802 /
\plot 4.754 25.802 4.779 25.893 /
\plot 4.779 25.893 4.796 25.982 /
\plot 4.796 25.982 4.807 26.067 /
\plot 4.807 26.067 4.809 26.151 /
\plot 4.809 26.151 4.801 26.234 /
\plot 4.801 26.234 4.782 26.312 /
\plot 4.782 26.312 4.750 26.386 /
\plot 4.750 26.386 4.707 26.454 /
\plot 4.707 26.454 4.648 26.513 /
\plot 4.648 26.513 4.587 26.558 /
\plot 4.587 26.558 4.515 26.592 /
\plot 4.515 26.592 4.439 26.619 /
\plot 4.439 26.619 4.356 26.638 /
\plot 4.356 26.638 4.269 26.651 /
\plot 4.269 26.651 4.180 26.655 /
\putrule from 4.180 26.655 to 4.087 26.655
\plot 4.087 26.655 3.992 26.651 /
\plot 3.992 26.651 3.897 26.642 /
\plot 3.897 26.642 3.797 26.628 /
\plot 3.797 26.628 3.698 26.611 /
\plot 3.698 26.611 3.598 26.590 /
\plot 3.598 26.590 3.497 26.566 /
\plot 3.497 26.566 3.395 26.541 /
\plot 3.395 26.541 3.291 26.513 /
\plot 3.291 26.513 3.192 26.484 /
\plot 3.192 26.484 3.090 26.454 /
\plot 3.090 26.454 2.993 26.424 /
\plot 2.993 26.424 2.900 26.395 /
\plot 2.900 26.395 2.811 26.365 /
\plot 2.811 26.365 2.728 26.338 /
\plot 2.728 26.338 2.652 26.312 /
\plot 2.652 26.312 2.587 26.289 /
\plot 2.587 26.289 2.527 26.268 /
\plot 2.527 26.268 2.479 26.251 /
\plot 2.479 26.251 2.438 26.236 /
\plot 2.438 26.236 2.409 26.226 /
\plot 2.409 26.226 2.388 26.217 /
\plot 2.388 26.217 2.373 26.213 /
\plot 2.373 26.213 2.366 26.211 /
\plot 2.366 26.211 2.362 26.209 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 4.801 22.856 to 4.801 22.854
\plot 4.801 22.854 4.798 22.847 /
\plot 4.798 22.847 4.794 22.837 /
\plot 4.794 22.837 4.788 22.822 /
\plot 4.788 22.822 4.779 22.801 /
\plot 4.779 22.801 4.767 22.771 /
\plot 4.767 22.771 4.752 22.737 /
\plot 4.752 22.737 4.735 22.695 /
\plot 4.735 22.695 4.714 22.648 /
\plot 4.714 22.648 4.691 22.598 /
\plot 4.691 22.598 4.665 22.540 /
\plot 4.665 22.540 4.635 22.483 /
\plot 4.635 22.483 4.606 22.422 /
\plot 4.606 22.422 4.572 22.358 /
\plot 4.572 22.358 4.534 22.295 /
\plot 4.534 22.295 4.494 22.229 /
\plot 4.494 22.229 4.451 22.164 /
\plot 4.451 22.164 4.405 22.098 /
\plot 4.405 22.098 4.354 22.030 /
\plot 4.354 22.030 4.299 21.963 /
\plot 4.299 21.963 4.238 21.895 /
\plot 4.238 21.895 4.172 21.827 /
\plot 4.172 21.827 4.098 21.757 /
\plot 4.098 21.757 4.017 21.687 /
\plot 4.017 21.687 3.931 21.618 /
\plot 3.931 21.618 3.835 21.550 /
\plot 3.835 21.550 3.734 21.484 /
\plot 3.734 21.484 3.630 21.423 /
\plot 3.630 21.423 3.526 21.370 /
\plot 3.526 21.370 3.427 21.321 /
\plot 3.427 21.321 3.334 21.277 /
\plot 3.334 21.277 3.251 21.241 /
\plot 3.251 21.241 3.175 21.211 /
\plot 3.175 21.211 3.109 21.184 /
\plot 3.109 21.184 3.052 21.162 /
\plot 3.052 21.162 3.004 21.143 /
\plot 3.004 21.143 2.961 21.129 /
\plot 2.961 21.129 2.925 21.118 /
\plot 2.925 21.118 2.893 21.107 /
\plot 2.893 21.107 2.864 21.099 /
\plot 2.864 21.099 2.836 21.090 /
\plot 2.836 21.090 2.807 21.084 /
\plot 2.807 21.084 2.777 21.078 /
\plot 2.777 21.078 2.745 21.071 /
\plot 2.745 21.071 2.707 21.067 /
\plot 2.707 21.067 2.665 21.063 /
\plot 2.665 21.063 2.616 21.057 /
\plot 2.616 21.057 2.557 21.054 /
\plot 2.557 21.054 2.489 21.050 /
\plot 2.489 21.050 2.413 21.048 /
\putrule from 2.413 21.048 to 2.326 21.048
\plot 2.326 21.048 2.231 21.052 /
\plot 2.231 21.052 2.127 21.059 /
\plot 2.127 21.059 2.019 21.069 /
\plot 2.019 21.069 1.909 21.086 /
\plot 1.909 21.086 1.801 21.110 /
\plot 1.801 21.110 1.700 21.137 /
\plot 1.700 21.137 1.607 21.167 /
\plot 1.607 21.167 1.524 21.196 /
\plot 1.524 21.196 1.450 21.226 /
\plot 1.450 21.226 1.384 21.253 /
\plot 1.384 21.253 1.329 21.279 /
\plot 1.329 21.279 1.283 21.302 /
\plot 1.283 21.302 1.242 21.323 /
\plot 1.242 21.323 1.211 21.340 /
\plot 1.211 21.340 1.181 21.357 /
\plot 1.181 21.357 1.158 21.372 /
\plot 1.158 21.372 1.137 21.387 /
\plot 1.137 21.387 1.118 21.402 /
\plot 1.118 21.402 1.099 21.419 /
\plot 1.099 21.419 1.079 21.435 /
\plot 1.079 21.435 1.060 21.455 /
\plot 1.060 21.455 1.039 21.476 /
\plot 1.039 21.476 1.014 21.503 /
\plot 1.014 21.503 0.986 21.535 /
\plot 0.986 21.535 0.955 21.573 /
\plot 0.955 21.573 0.921 21.618 /
\plot 0.921 21.618 0.883 21.670 /
\plot 0.883 21.670 0.840 21.732 /
\plot 0.840 21.732 0.798 21.802 /
\plot 0.798 21.802 0.754 21.878 /
\plot 0.754 21.878 0.711 21.963 /
\plot 0.711 21.963 0.673 22.051 /
\plot 0.673 22.051 0.641 22.145 /
\plot 0.641 22.145 0.618 22.236 /
\plot 0.618 22.236 0.599 22.324 /
\plot 0.599 22.324 0.586 22.407 /
\plot 0.586 22.407 0.578 22.481 /
\plot 0.578 22.481 0.572 22.549 /
\plot 0.572 22.549 0.567 22.610 /
\putrule from 0.567 22.610 to 0.567 22.663
\putrule from 0.567 22.663 to 0.567 22.708
\putrule from 0.567 22.708 to 0.567 22.748
\plot 0.567 22.748 0.569 22.784 /
\plot 0.569 22.784 0.574 22.816 /
\plot 0.574 22.816 0.578 22.845 /
\plot 0.578 22.845 0.582 22.873 /
\plot 0.582 22.873 0.588 22.900 /
\plot 0.588 22.900 0.595 22.930 /
\plot 0.595 22.930 0.603 22.962 /
\plot 0.603 22.962 0.614 22.995 /
\plot 0.614 22.995 0.627 23.034 /
\plot 0.627 23.034 0.643 23.078 /
\plot 0.643 23.078 0.663 23.129 /
\plot 0.663 23.129 0.684 23.188 /
\plot 0.684 23.188 0.711 23.252 /
\plot 0.711 23.252 0.745 23.324 /
\plot 0.745 23.324 0.783 23.402 /
\plot 0.783 23.402 0.828 23.484 /
\plot 0.828 23.484 0.878 23.569 /
\plot 0.878 23.569 0.936 23.654 /
\plot 0.936 23.654 1.003 23.741 /
\plot 1.003 23.741 1.075 23.821 /
\plot 1.075 23.821 1.149 23.891 /
\plot 1.149 23.891 1.226 23.956 /
\plot 1.226 23.956 1.302 24.011 /
\plot 1.302 24.011 1.376 24.062 /
\plot 1.376 24.062 1.452 24.107 /
\plot 1.452 24.107 1.528 24.145 /
\plot 1.528 24.145 1.602 24.179 /
\plot 1.602 24.179 1.676 24.208 /
\plot 1.676 24.208 1.750 24.236 /
\plot 1.750 24.236 1.825 24.259 /
\plot 1.825 24.259 1.897 24.280 /
\plot 1.897 24.280 1.966 24.299 /
\plot 1.966 24.299 2.034 24.316 /
\plot 2.034 24.316 2.098 24.331 /
\plot 2.098 24.331 2.155 24.342 /
\plot 2.155 24.342 2.208 24.352 /
\plot 2.208 24.352 2.252 24.361 /
\plot 2.252 24.361 2.288 24.367 /
\plot 2.288 24.367 2.318 24.373 /
\plot 2.318 24.373 2.339 24.376 /
\plot 2.339 24.376 2.352 24.378 /
\plot 2.352 24.378 2.358 24.380 /
\putrule from 2.358 24.380 to 2.362 24.380
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.191 24.685 4.801 22.856 /
\plot 4.801 22.856 2.362 22.246 /
\putrule from 2.362 22.246 to 2.362 24.380
\plot 2.362 24.380 4.801 22.856 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.362 24.380 4.191 24.685 /
\plot 4.191 24.685 2.362 26.209 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 0.533 25.294 2.362 26.209 /
\putrule from 2.362 26.209 to 2.362 24.380
\plot 2.362 24.380 0.533 25.294 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at 1.105 25.180
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at 2.743 25.980
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}%
} [lB] at 4.191 22.399
\linethickness=0pt
\putrectangle corners at 0.364 26.702 and 4.970 21.002
\endpicture}
\end{center}
\caption{\label{cap:eulerovska_cesta}Tvorba cyklu v eulerovském grafu}
\end{figure}
\end{proof}
\begin{rem*}
Existují také tzv. náhodně eulerovské grafy, které mají jeden vrchol
s tou vlastností, že při náhodném průchodu grafu a barvení cest za
sebou lze vždy pokračovat po neobarvených hranách až na případ, kdy
se nacházíme ve startovním vrcholu a všechny hrany už jsou obarvené.
\end{rem*}
\begin{rem*}
Uvažujme jednotažky takové, že je možné je namalovat jedním tahem
a přitom začít a skončit v obecně různých vrcholech. Tyto jednotažky
jsou právě takové souvislé grafy, které splňují jednu z následujících
dvou podmínek (viz obrázek \ref{cap:jednotazka}):%
\begin{figure}
\begin{center}
%Title: jednotazka.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:45:28 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.091:0.091 360 degrees
from 1.750 22.498 center at 1.659 22.498
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at 2.028 26.558
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at 1.289 23.973
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at 2.766 23.973
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at 2.766 25.451
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at 1.289 25.451
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.2032cm>
{\color[rgb]{0,0,0}\plot 2.766 23.973 1.659 22.498 /
\setsolid
%
% arrow head
%
\plot 1.842 22.996 1.659 22.498 2.086 22.813 /
%
\setdashes < 0.2032cm>
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 1.659 22.498 1.289 23.973 /
\setsolid
%
% arrow head
%
\plot 1.561 23.518 1.289 23.973 1.265 23.444 /
%
\setdashes < 0.2032cm>
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setsolid
{\color[rgb]{0,0,0}\plot 1.289 25.451 2.766 23.973 /
%
% arrow head
%
\plot 2.300 24.225 2.766 23.973 2.515 24.440 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 1.289 23.973 to 1.289 25.451
%
% arrow head
%
\plot 1.441 24.943 1.289 25.451 1.137 24.943 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.766 25.451 1.289 23.973 /
%
% arrow head
%
\plot 1.540 24.440 1.289 23.973 1.756 24.225 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 1.289 25.451 to 2.766 25.451
%
% arrow head
%
\plot 2.258 25.298 2.766 25.451 2.258 25.603 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.028 26.558 1.289 25.451 /
%
% arrow head
%
\plot 1.444 25.958 1.289 25.451 1.698 25.789 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.766 25.451 2.028 26.558 /
%
% arrow head
%
\plot 2.437 26.220 2.028 26.558 2.183 26.051 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 2.766 23.973 to 2.766 25.451
%
% arrow head
%
\plot 2.919 24.943 2.766 25.451 2.614 24.943 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 1.289 23.973 to 2.766 23.973
%
% arrow head
%
\plot 2.258 23.821 2.766 23.973 2.258 24.126 /
%
}%
%
% Fig TEXT object
%
\put{\SetFigFont{11}{13.2}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c\'{i}l}%
} [lB] at 3.135 23.882
%
% Fig TEXT object
%
\put{\SetFigFont{11}{13.2}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}start}%
} [lB] at 0.129 23.882
\linethickness=0pt
\putrectangle corners at 0.097 26.666 and 3.167 22.390
\endpicture}
\end{center}
\caption{\label{cap:jednotazka}Jednotažka se startovním a cílovým vrcholem}
\end{figure}
\begin{enumerate}
\item Všechny vrcholy mají sudý stupeň.
\item Právě dva vrcholy mají lichý stupeň.
\end{enumerate}
\end{rem*}
