Součásti dokumentu 01ZTGA
Zdrojový kód
%\wikiskriptum{01ZTGA}
\section{Planární grafy}
\begin{defn}
Graf $G$ nazveme \textbf{planárním} (rovinným) \textbf{grafem} (angl.
\emph{planar graph}), jestliže jej lze namalovat do roviny tak, že
se žádné dvě jeho hrany nekříží jinde než ve svých koncových vrcholech.
\end{defn}
\begin{rem*}
Uvedená definice je pouze intuitivní. Korektní definice by byla zbytečně
komplikovaná, neboť by vybočovala ze záměru přednášky, která je orientována
na kombinatorickou stránku teorie grafů. Pro představu se o takovou
definici \emph{pokusíme}:
Nechť $\mathcal{C}$ je množina všech jednoduchých spojitých křivek
v $\R^{2}$. Graf (bez násobných hran) $G$ se nazývá \textbf{planární}
právě tehdy, existuje-li prosté zobrazení $\varphi:V\cup\{\emptyset\}\mapsto\R^{2}\cup\{\emptyset\}$
a zobrazení $\psi:E\mapsto\mathcal{C}$, takové že
\[
\varphi(\emptyset)=\emptyset,\]
\[
\left(\forall e\in E,e=\{ u_{1},u_{2}\}\right)\left(\psi(e)_{orig}=\varphi(u_{1})\,\wedge\,\psi(e)_{term}=\varphi(u_{2})\right),\]
\[
\left(\forall e,f\in E,e=\{ u_{1},u_{2}\},f=\{ v_{1},v_{2}\}\right)\left(\psi(e)\cap\psi(f)=\varphi(e\cap f)\right),\]
kde $\psi_{orig}$ je počáteční bod (angl. \emph{origin}) křivky $\psi$
a $\psi_{term}$ je koncový bod (angl. \emph{terminus}) křivky $\psi$.
Pro studium vlastností planárních grafů je potřeba rozumět topologii
roviny, tj. lineárního prostoru $\R^{2}$. Zde se omezíme na intuitivní
chápání používaných pojmů.
\end{rem*}
\begin{rem}
\textbf{Jordanovou křivkou} rozumíme jednoduchou uzavřenou spojitou
křivku $\varphi$. Její \textbf{vnitřek} označujeme $\mathrm{int}\,\varphi$,
její \textbf{vnějšek} $\mathrm{ext}\,\varphi$. \textbf{Jordanova
věta} říká, že každá spojitá křivka $\psi$ s počátkem v bodě $x\in\mathrm{int}\,\varphi$
a koncem v bodě $y\in\mathrm{ext}\,\varphi$ protíná křivku $\varphi$,
tj $\varphi\cap\psi\neq\emptyset$. Tato skutečnost je téměř samozřejmá,
její formální důkaz je však obtížný.
\end{rem}
\begin{example*}
$K_{4}$ je planární graf. To je vidět na obrázku \ref{cap:planarni-K4}.%
\begin{figure}
\begin{center}
%Title: planarK4.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:20:48 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}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 1.547 26.551
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 1.547 25.599
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.500 26.075
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 0.595 26.075 1.547 26.551 /
\plot 1.547 26.551 2.500 26.075 /
\plot 2.500 26.075 1.547 25.599 /
\plot 1.547 25.599 0.595 26.075 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 0.595 26.075 to 2.500 26.075
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 1.547 26.551 to 1.552 26.551
\plot 1.552 26.551 1.560 26.549 /
\plot 1.560 26.549 1.577 26.547 /
\plot 1.577 26.547 1.604 26.545 /
\plot 1.604 26.545 1.640 26.539 /
\plot 1.640 26.539 1.689 26.532 /
\plot 1.689 26.532 1.748 26.526 /
\plot 1.748 26.526 1.816 26.515 /
\plot 1.816 26.515 1.897 26.505 /
\plot 1.897 26.505 1.983 26.492 /
\plot 1.983 26.492 2.076 26.480 /
\plot 2.076 26.480 2.176 26.465 /
\plot 2.176 26.465 2.278 26.450 /
\plot 2.278 26.450 2.381 26.433 /
\plot 2.381 26.433 2.485 26.416 /
\plot 2.485 26.416 2.589 26.397 /
\plot 2.589 26.397 2.690 26.378 /
\plot 2.690 26.378 2.788 26.359 /
\plot 2.788 26.359 2.883 26.340 /
\plot 2.883 26.340 2.974 26.319 /
\plot 2.974 26.319 3.059 26.295 /
\plot 3.059 26.295 3.139 26.272 /
\plot 3.139 26.272 3.213 26.249 /
\plot 3.213 26.249 3.279 26.223 /
\plot 3.279 26.223 3.336 26.196 /
\plot 3.336 26.196 3.385 26.168 /
\plot 3.385 26.168 3.421 26.139 /
\plot 3.421 26.139 3.444 26.107 /
\plot 3.444 26.107 3.452 26.075 /
\plot 3.452 26.075 3.444 26.043 /
\plot 3.444 26.043 3.421 26.012 /
\plot 3.421 26.012 3.385 25.982 /
\plot 3.385 25.982 3.336 25.955 /
\plot 3.336 25.955 3.279 25.927 /
\plot 3.279 25.927 3.213 25.902 /
\plot 3.213 25.902 3.139 25.878 /
\plot 3.139 25.878 3.059 25.855 /
\plot 3.059 25.855 2.974 25.832 /
\plot 2.974 25.832 2.883 25.811 /
\plot 2.883 25.811 2.788 25.792 /
\plot 2.788 25.792 2.690 25.773 /
\plot 2.690 25.773 2.589 25.753 /
\plot 2.589 25.753 2.485 25.734 /
\plot 2.485 25.734 2.381 25.718 /
\plot 2.381 25.718 2.278 25.701 /
\plot 2.278 25.701 2.176 25.686 /
\plot 2.176 25.686 2.076 25.671 /
\plot 2.076 25.671 1.983 25.658 /
\plot 1.983 25.658 1.897 25.646 /
\plot 1.897 25.646 1.816 25.635 /
\plot 1.816 25.635 1.748 25.624 /
\plot 1.748 25.624 1.689 25.618 /
\plot 1.689 25.618 1.640 25.612 /
\plot 1.640 25.612 1.604 25.605 /
\plot 1.604 25.605 1.577 25.603 /
\plot 1.577 25.603 1.560 25.601 /
\plot 1.560 25.601 1.552 25.599 /
\putrule from 1.552 25.599 to 1.547 25.599
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 0.595 26.075
}%
\linethickness=0pt
\putrectangle corners at 0.459 26.685 and 3.499 25.466
\endpicture}
\end{center}
\caption{\label{cap:planarni-K4}$K_{4}$ nakreslený do roviny}
\end{figure}
\end{example*}
\begin{example*}
$K_{5}$ není planární.
\end{example*}
\begin{proof}
Vezměme vrcholy $v_{1},v_{2},v_{3}$ a spojme je hranami, jako na
obrázku \ref{cap:neplanarni-K5}. Tyto hrany vytvoří Jordanovu křivku
$\varphi$. Aby bylo možné spojit i vrcholy $v_{4}$ a $v_{5}$, nemůže
podle Jordanovy věty ležet $v_{4}\in\mathrm{int}\,\varphi$ a $v_{5}\in\mathrm{ext}\,\varphi$
nebo naopak. Nechť jsou tedy $v_{4},v_{5}\in\mathrm{ext}\,\varphi$.
Spojíme $v_{4}$ s $v_{1},v_{2},v_{3}$, čímž se (podle obrázku) dostane
vrchol $v_{2}$ do vnitřku křivky $\psi$ tvořené hranami mezi vrcholy
$v_{1},v_{3},v_{4}$. Umístíme-li nyní vrchol $v_{5}$ do $\mathrm{ext}\,\psi$,
nebude možné jej spojit s $v_{2}$. Umístíme-li jej někam do $\mathrm{int}\,\psi$,
nebude možné jej spojit s jedním z vrcholů $v_{1},v_{3},v_{4}$. Pokud
bychom předpokládali $v_{4},v_{5}\in\mathrm{int}\,\varphi$, byl by
další postup podobný. %
\begin{figure}
\begin{center}
%Title: planar_neni_K5.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 20:44:40 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}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 4.523 25.243
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.618 24.289
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.618 25.720
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 1.190 25.241
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 1.190 25.241 1.187 25.243 /
\plot 1.187 25.243 1.183 25.250 /
\plot 1.183 25.250 1.177 25.262 /
\plot 1.177 25.262 1.166 25.279 /
\plot 1.166 25.279 1.151 25.303 /
\plot 1.151 25.303 1.135 25.334 /
\plot 1.135 25.334 1.111 25.375 /
\plot 1.111 25.375 1.088 25.419 /
\plot 1.088 25.419 1.060 25.470 /
\plot 1.060 25.470 1.031 25.527 /
\plot 1.031 25.527 1.001 25.586 /
\plot 1.001 25.586 0.972 25.650 /
\plot 0.972 25.650 0.944 25.713 /
\plot 0.944 25.713 0.919 25.781 /
\plot 0.919 25.781 0.895 25.847 /
\plot 0.895 25.847 0.876 25.914 /
\plot 0.876 25.914 0.861 25.980 /
\plot 0.861 25.980 0.853 26.046 /
\plot 0.853 26.046 0.851 26.109 /
\plot 0.851 26.109 0.855 26.173 /
\plot 0.855 26.173 0.870 26.234 /
\plot 0.870 26.234 0.891 26.295 /
\plot 0.891 26.295 0.925 26.352 /
\plot 0.925 26.352 0.972 26.410 /
\plot 0.972 26.410 1.031 26.463 /
\plot 1.031 26.463 1.103 26.509 /
\plot 1.103 26.509 1.190 26.551 /
\plot 1.190 26.551 1.270 26.581 /
\plot 1.270 26.581 1.357 26.604 /
\plot 1.357 26.604 1.448 26.623 /
\plot 1.448 26.623 1.539 26.638 /
\plot 1.539 26.638 1.628 26.649 /
\plot 1.628 26.649 1.715 26.657 /
\plot 1.715 26.657 1.799 26.664 /
\plot 1.799 26.664 1.880 26.666 /
\putrule from 1.880 26.666 to 1.954 26.666
\putrule from 1.954 26.666 to 2.026 26.666
\plot 2.026 26.666 2.093 26.664 /
\plot 2.093 26.664 2.157 26.659 /
\plot 2.157 26.659 2.218 26.655 /
\plot 2.218 26.655 2.275 26.651 /
\plot 2.275 26.651 2.330 26.645 /
\plot 2.330 26.645 2.385 26.638 /
\plot 2.385 26.638 2.441 26.632 /
\plot 2.441 26.632 2.496 26.623 /
\plot 2.496 26.623 2.551 26.615 /
\plot 2.551 26.615 2.608 26.607 /
\plot 2.608 26.607 2.667 26.596 /
\plot 2.667 26.596 2.728 26.585 /
\plot 2.728 26.585 2.796 26.575 /
\plot 2.796 26.575 2.866 26.562 /
\plot 2.866 26.562 2.942 26.547 /
\plot 2.942 26.547 3.023 26.530 /
\plot 3.023 26.530 3.107 26.513 /
\plot 3.107 26.513 3.200 26.492 /
\plot 3.200 26.492 3.296 26.469 /
\plot 3.296 26.469 3.397 26.444 /
\plot 3.397 26.444 3.501 26.416 /
\plot 3.501 26.416 3.605 26.386 /
\plot 3.605 26.386 3.708 26.352 /
\plot 3.708 26.352 3.810 26.314 /
\plot 3.810 26.314 3.924 26.266 /
\plot 3.924 26.266 4.026 26.215 /
\plot 4.026 26.215 4.117 26.162 /
\plot 4.117 26.162 4.195 26.109 /
\plot 4.195 26.109 4.261 26.056 /
\plot 4.261 26.056 4.318 26.001 /
\plot 4.318 26.001 4.367 25.948 /
\plot 4.367 25.948 4.407 25.897 /
\plot 4.407 25.897 4.439 25.845 /
\plot 4.439 25.845 4.466 25.792 /
\plot 4.466 25.792 4.485 25.741 /
\plot 4.485 25.741 4.502 25.688 /
\plot 4.502 25.688 4.515 25.637 /
\plot 4.515 25.637 4.523 25.588 /
\plot 4.523 25.588 4.530 25.540 /
\plot 4.530 25.540 4.534 25.493 /
\plot 4.534 25.493 4.536 25.449 /
\putrule from 4.536 25.449 to 4.536 25.406
\plot 4.536 25.406 4.534 25.370 /
\plot 4.534 25.370 4.532 25.337 /
\plot 4.532 25.337 4.530 25.309 /
\putrule from 4.530 25.309 to 4.530 25.286
\plot 4.530 25.286 4.528 25.269 /
\plot 4.528 25.269 4.525 25.256 /
\plot 4.525 25.256 4.523 25.248 /
\putrule from 4.523 25.248 to 4.523 25.243
\putrule from 4.523 25.243 to 4.523 25.241
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 4.523 25.241 2.618 24.289 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 4.523 25.241 2.618 25.718 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.618 24.289 2.612 24.285 /
\plot 2.612 24.285 2.601 24.276 /
\plot 2.601 24.276 2.580 24.261 /
\plot 2.580 24.261 2.551 24.240 /
\plot 2.551 24.240 2.512 24.213 /
\plot 2.512 24.213 2.468 24.181 /
\plot 2.468 24.181 2.417 24.147 /
\plot 2.417 24.147 2.362 24.111 /
\plot 2.362 24.111 2.305 24.075 /
\plot 2.305 24.075 2.250 24.041 /
\plot 2.250 24.041 2.195 24.009 /
\plot 2.195 24.009 2.140 23.982 /
\plot 2.140 23.982 2.087 23.956 /
\plot 2.087 23.956 2.036 23.940 /
\plot 2.036 23.940 1.988 23.929 /
\plot 1.988 23.929 1.943 23.925 /
\plot 1.943 23.925 1.905 23.933 /
\plot 1.905 23.933 1.875 23.954 /
\plot 1.875 23.954 1.858 23.986 /
\plot 1.858 23.986 1.854 24.022 /
\plot 1.854 24.022 1.861 24.060 /
\plot 1.861 24.060 1.873 24.098 /
\plot 1.873 24.098 1.894 24.136 /
\plot 1.894 24.136 1.918 24.174 /
\plot 1.918 24.174 1.945 24.210 /
\plot 1.945 24.210 1.971 24.249 /
\plot 1.971 24.249 1.996 24.287 /
\plot 1.996 24.287 2.017 24.327 /
\plot 2.017 24.327 2.034 24.367 /
\plot 2.034 24.367 2.047 24.409 /
\plot 2.047 24.409 2.049 24.454 /
\plot 2.049 24.454 2.040 24.494 /
\plot 2.040 24.494 2.024 24.528 /
\plot 2.024 24.528 1.994 24.553 /
\plot 1.994 24.553 1.958 24.566 /
\plot 1.958 24.566 1.920 24.562 /
\plot 1.920 24.562 1.884 24.547 /
\plot 1.884 24.547 1.850 24.526 /
\plot 1.850 24.526 1.816 24.498 /
\plot 1.816 24.498 1.784 24.469 /
\plot 1.784 24.469 1.755 24.439 /
\plot 1.755 24.439 1.721 24.412 /
\plot 1.721 24.412 1.687 24.390 /
\plot 1.687 24.390 1.651 24.376 /
\plot 1.651 24.376 1.613 24.371 /
\plot 1.613 24.371 1.577 24.384 /
\plot 1.577 24.384 1.547 24.409 /
\plot 1.547 24.409 1.530 24.443 /
\plot 1.530 24.443 1.522 24.483 /
\putrule from 1.522 24.483 to 1.522 24.522
\plot 1.522 24.522 1.530 24.558 /
\plot 1.530 24.558 1.545 24.591 /
\plot 1.545 24.591 1.564 24.623 /
\plot 1.564 24.623 1.585 24.651 /
\plot 1.585 24.651 1.607 24.676 /
\plot 1.607 24.676 1.628 24.704 /
\plot 1.628 24.704 1.649 24.733 /
\plot 1.649 24.733 1.668 24.767 /
\plot 1.668 24.767 1.683 24.805 /
\plot 1.683 24.805 1.691 24.848 /
\putrule from 1.691 24.848 to 1.691 24.896
\plot 1.691 24.896 1.683 24.951 /
\plot 1.683 24.951 1.666 25.004 /
\plot 1.666 25.004 1.640 25.053 /
\plot 1.640 25.053 1.607 25.093 /
\plot 1.607 25.093 1.571 25.127 /
\plot 1.571 25.127 1.532 25.154 /
\plot 1.532 25.154 1.492 25.176 /
\plot 1.492 25.176 1.450 25.193 /
\plot 1.450 25.193 1.408 25.205 /
\plot 1.408 25.205 1.365 25.216 /
\plot 1.365 25.216 1.323 25.224 /
\plot 1.323 25.224 1.285 25.231 /
\plot 1.285 25.231 1.251 25.235 /
\plot 1.251 25.235 1.223 25.237 /
\plot 1.223 25.237 1.206 25.239 /
\plot 1.206 25.239 1.194 25.241 /
\putrule from 1.194 25.241 to 1.190 25.241
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.618 25.718 2.623 25.715 /
\plot 2.623 25.715 2.629 25.709 /
\plot 2.629 25.709 2.642 25.698 /
\plot 2.642 25.698 2.661 25.684 /
\plot 2.661 25.684 2.686 25.665 /
\plot 2.686 25.665 2.716 25.639 /
\plot 2.716 25.639 2.750 25.610 /
\plot 2.750 25.610 2.788 25.576 /
\plot 2.788 25.576 2.826 25.540 /
\plot 2.826 25.540 2.866 25.499 /
\plot 2.866 25.499 2.904 25.459 /
\plot 2.904 25.459 2.940 25.415 /
\plot 2.940 25.415 2.974 25.368 /
\plot 2.974 25.368 3.006 25.317 /
\plot 3.006 25.317 3.035 25.265 /
\plot 3.035 25.265 3.059 25.205 /
\plot 3.059 25.205 3.078 25.142 /
\plot 3.078 25.142 3.090 25.074 /
\plot 3.090 25.074 3.095 25.004 /
\plot 3.095 25.004 3.090 24.934 /
\plot 3.090 24.934 3.078 24.867 /
\plot 3.078 24.867 3.059 24.803 /
\plot 3.059 24.803 3.035 24.744 /
\plot 3.035 24.744 3.006 24.691 /
\plot 3.006 24.691 2.974 24.640 /
\plot 2.974 24.640 2.940 24.594 /
\plot 2.940 24.594 2.904 24.549 /
\plot 2.904 24.549 2.866 24.507 /
\plot 2.866 24.507 2.826 24.469 /
\plot 2.826 24.469 2.788 24.431 /
\plot 2.788 24.431 2.750 24.397 /
\plot 2.750 24.397 2.716 24.367 /
\plot 2.716 24.367 2.686 24.342 /
\plot 2.686 24.342 2.661 24.323 /
\plot 2.661 24.323 2.642 24.308 /
\plot 2.642 24.308 2.629 24.297 /
\plot 2.629 24.297 2.623 24.291 /
\plot 2.623 24.291 2.618 24.289 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 1.190 25.241 1.192 25.248 /
\plot 1.192 25.248 1.194 25.262 /
\plot 1.194 25.262 1.198 25.288 /
\plot 1.198 25.288 1.204 25.324 /
\plot 1.204 25.324 1.215 25.372 /
\plot 1.215 25.372 1.226 25.428 /
\plot 1.226 25.428 1.240 25.489 /
\plot 1.240 25.489 1.257 25.555 /
\plot 1.257 25.555 1.274 25.620 /
\plot 1.274 25.620 1.295 25.684 /
\plot 1.295 25.684 1.319 25.743 /
\plot 1.319 25.743 1.346 25.798 /
\plot 1.346 25.798 1.376 25.849 /
\plot 1.376 25.849 1.410 25.891 /
\plot 1.410 25.891 1.450 25.925 /
\plot 1.450 25.925 1.496 25.948 /
\plot 1.496 25.948 1.547 25.957 /
\plot 1.547 25.957 1.596 25.950 /
\plot 1.596 25.950 1.643 25.931 /
\plot 1.643 25.931 1.685 25.904 /
\plot 1.685 25.904 1.721 25.872 /
\plot 1.721 25.872 1.750 25.834 /
\plot 1.750 25.834 1.776 25.794 /
\plot 1.776 25.794 1.795 25.751 /
\plot 1.795 25.751 1.810 25.707 /
\plot 1.810 25.707 1.822 25.662 /
\plot 1.822 25.662 1.835 25.618 /
\plot 1.835 25.618 1.846 25.574 /
\plot 1.846 25.574 1.861 25.529 /
\plot 1.861 25.529 1.875 25.485 /
\plot 1.875 25.485 1.897 25.442 /
\plot 1.897 25.442 1.922 25.398 /
\plot 1.922 25.398 1.954 25.358 /
\plot 1.954 25.358 1.992 25.320 /
\plot 1.992 25.320 2.038 25.286 /
\plot 2.038 25.286 2.089 25.258 /
\plot 2.089 25.258 2.142 25.241 /
\plot 2.142 25.241 2.199 25.235 /
\plot 2.199 25.235 2.254 25.241 /
\plot 2.254 25.241 2.303 25.258 /
\plot 2.303 25.258 2.347 25.284 /
\plot 2.347 25.284 2.385 25.315 /
\plot 2.385 25.315 2.421 25.353 /
\plot 2.421 25.353 2.453 25.396 /
\plot 2.453 25.396 2.483 25.440 /
\plot 2.483 25.440 2.510 25.487 /
\plot 2.510 25.487 2.536 25.533 /
\plot 2.536 25.533 2.557 25.580 /
\plot 2.557 25.580 2.576 25.620 /
\plot 2.576 25.620 2.593 25.656 /
\plot 2.593 25.656 2.603 25.684 /
\plot 2.603 25.684 2.612 25.701 /
\plot 2.612 25.701 2.616 25.713 /
\plot 2.616 25.713 2.618 25.718 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\psi$}%
} [lB] at 4.166 26.433
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\varphi$}%
} [lB] at 1.071 24.052
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{4}$}%
} [lB] at 4.881 25.123
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{3}$}%
} [lB] at 2.500 23.575
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at 2.500 26.196
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 0.476 25.123
\linethickness=0pt
\putrectangle corners at 0.444 26.803 and 4.913 23.376
\endpicture}
\end{center}
\caption{\label{cap:neplanarni-K5}$K_{5}$ není planární}
\end{figure}
\end{proof}
\begin{rem*}
Uvedený důkaz je velice těžkopádný. Za chvíli vyslovíme větu, která
umožní dokázat stejné tvrzení mnohem snáze. Její pomocí dále dokážeme,
že také úplný bipartitní graf na $3+3$ vrcholech ($K_{3,3}$) není
planární.
\end{rem*}
\begin{defn}
Nechť $G=(V,E)$, $e=\{ u,v\}\in E$, . Potom definujeme \textbf{dělení
hrany} $e$ jako graf\[
G\% e=(V\cup\{\alpha\},E\backslash\{ u,v\}\cup\{\{ u,\alpha\},\{\alpha,v\}\}),\]
kde $\alpha\notin V$.
\end{defn}
\begin{obs*}
$G$ je planární $\Leftrightarrow$ $G\% e$ je planární.
\end{obs*}
\begin{defn}
Graf $H$ nazveme \textbf{dělením grafu} $G$, vznikne-li z $G$ konečným
počtem opakování operace dělení hrany.
\end{defn}
\begin{obs*}
Jestliže $G$ obsahuje jako svůj podgraf dělení $K_{5}$ nebo $K_{3,3}$,
tak $G$ není planární.
\end{obs*}
\begin{thm}
\textbf{\emph{(Kuratowski, 1930)}}
Graf $G$ není planární právě tehdy, když obsahuje jako svůj podgraf
dělení $K_{5}$ nebo $K_{3,3}$.
\end{thm}
\begin{proof}
Implikace $\boxed{{\Leftarrow:}}$ je obsažena v předchozí poznámce.
Implikaci $\boxed{{\Rightarrow:}}$ dokazovat nebudeme.
\end{proof}
\begin{rem*}
\emph{(Zajímavost)} Je otázka, jestli je každý graf $G$ planární
právě tehdy, jde-li namalovat na povrch koule či do jiných ploch.
Pro kouli uvedená ekvivalence platí, protože mezi rovinou a koulí
(až na jeden její bod) existuje bijekce - takzvaná \emph{stereografická
projekce} $\pi$, definovaná následovně. Kouli $B$ položíme na rovinu
$P$. Označme jako $z$ nejvyšší bod $B$, tj. průsečík $B$ s kolmicí
na $P$ vedenou bodem dotyku $B$ a $P$. Libovolný bod $x$ na $B$
kromě bodu $z$ spojíme přimkou s bodem $z$. Její průsečík s rovinou
$P$ pak označíme jako $\pi(x)$. $\pi$ pak představuje bijekci\[
\pi:B\backslash\{ z\}\mapsto P.\]
Pro jiné plochy však už ekvivalence neplatí. Například $K_{5}$ je
možné namalovat na torus a $K_{3,3}$ na Möbiův list, jak je vidět
na obrázku \ref{cap:K5-na-toru}. Zvláště v druhém případě je však
třeba si uvědomit, že ,,namalovat na plochu{}`` znamená spíše ,,položit
do plochy{}``, nikoliv namalovat na jednu stranu papíru. Pokud si
vyrobíme Möbiův list z pásky papíru, jejíž jeden konec přetočíme o
$180^{\circ}$ a oba konce spojíme, musíme graf nakreslit na obě strany,
jako kdyby byl papír průhledný.%
\begin{figure}
\begin{center}
%Title: K5_na_toru.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 20:01:44 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=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 2.618:1.784 360 degrees
from 5.476 24.289 center at 2.857 24.289
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.190:0.476 360 degrees
from 4.047 24.409 center at 2.857 24.409
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.174}}} at 3.334 23.575
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.178}}} at 3.512 22.860
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.178}}} at 2.796 23.158
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.178}}} at 3.988 23.425
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.178}}} at 3.452 23.218
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.784:1.130 360 degrees
from 4.642 24.289 center at 2.857 24.289
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 23.813
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.119:0.119 360 degrees
from 9.644 23.813 center at 9.525 23.813
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 23.813
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.119:0.119 360 degrees
from 8.691 24.765 center at 8.572 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 24.765
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.119:0.119 360 degrees
from 10.596 24.765 center at 10.478 24.765
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.796 23.158 3.334 23.575 /
\plot 3.334 23.575 3.988 23.427 /
\plot 3.988 23.427 3.512 22.860 /
\plot 3.512 22.860 2.796 23.144 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 3.512 22.845 3.452 23.218 /
\plot 3.452 23.218 3.334 23.561 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 3.334 23.575 3.332 23.582 /
\plot 3.332 23.582 3.330 23.594 /
\plot 3.330 23.594 3.323 23.616 /
\plot 3.323 23.616 3.317 23.639 /
\plot 3.317 23.639 3.308 23.666 /
\plot 3.308 23.666 3.296 23.696 /
\plot 3.296 23.696 3.283 23.728 /
\plot 3.283 23.728 3.264 23.762 /
\plot 3.264 23.762 3.243 23.798 /
\plot 3.243 23.798 3.213 23.838 /
\plot 3.213 23.838 3.186 23.868 /
\plot 3.186 23.868 3.160 23.891 /
\plot 3.160 23.891 3.137 23.908 /
\plot 3.137 23.908 3.118 23.920 /
\plot 3.118 23.920 3.103 23.929 /
\plot 3.103 23.929 3.097 23.933 /
\putrule from 3.097 23.933 to 3.095 23.933
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 3.512 22.860 to 3.512 22.858
\plot 3.512 22.858 3.509 22.849 /
\plot 3.509 22.849 3.507 22.830 /
\plot 3.507 22.830 3.503 22.805 /
\plot 3.503 22.805 3.495 22.775 /
\plot 3.495 22.775 3.486 22.744 /
\plot 3.486 22.744 3.471 22.708 /
\plot 3.471 22.708 3.452 22.667 /
\plot 3.452 22.667 3.429 22.631 /
\plot 3.429 22.631 3.408 22.606 /
\plot 3.408 22.606 3.387 22.587 /
\plot 3.387 22.587 3.370 22.572 /
\plot 3.370 22.572 3.353 22.559 /
\plot 3.353 22.559 3.340 22.553 /
\plot 3.340 22.553 3.334 22.549 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setdots < 0.1143cm>
{\color[rgb]{0,0,0}\plot 3.317 22.549 3.315 22.549 /
\plot 3.315 22.549 3.308 22.549 /
\plot 3.308 22.549 3.300 22.551 /
\plot 3.300 22.551 3.285 22.553 /
\plot 3.285 22.553 3.268 22.557 /
\plot 3.268 22.557 3.249 22.564 /
\plot 3.249 22.564 3.226 22.572 /
\plot 3.226 22.572 3.203 22.583 /
\plot 3.203 22.583 3.179 22.598 /
\plot 3.179 22.598 3.154 22.617 /
\plot 3.154 22.617 3.128 22.642 /
\plot 3.128 22.642 3.101 22.674 /
\plot 3.101 22.674 3.076 22.716 /
\plot 3.076 22.716 3.048 22.769 /
\plot 3.048 22.769 3.020 22.830 /
\plot 3.020 22.830 2.999 22.892 /
\plot 2.999 22.892 2.980 22.953 /
\plot 2.980 22.953 2.963 23.010 /
\plot 2.963 23.010 2.953 23.059 /
\plot 2.953 23.059 2.942 23.103 /
\plot 2.942 23.103 2.934 23.139 /
\plot 2.934 23.139 2.927 23.169 /
\plot 2.927 23.169 2.923 23.197 /
\plot 2.923 23.197 2.919 23.222 /
\plot 2.919 23.222 2.915 23.247 /
\plot 2.915 23.247 2.913 23.275 /
\plot 2.913 23.275 2.908 23.307 /
\plot 2.908 23.307 2.906 23.343 /
\plot 2.906 23.343 2.902 23.385 /
\plot 2.902 23.385 2.900 23.436 /
\plot 2.900 23.436 2.898 23.495 /
\plot 2.898 23.495 2.900 23.556 /
\plot 2.900 23.556 2.902 23.620 /
\plot 2.902 23.620 2.910 23.683 /
\plot 2.910 23.683 2.921 23.738 /
\plot 2.921 23.738 2.936 23.783 /
\plot 2.936 23.783 2.951 23.819 /
\plot 2.951 23.819 2.970 23.846 /
\plot 2.970 23.846 2.989 23.868 /
\plot 2.989 23.868 3.008 23.887 /
\plot 3.008 23.887 3.027 23.899 /
\plot 3.027 23.899 3.046 23.910 /
\plot 3.046 23.910 3.065 23.918 /
\plot 3.065 23.918 3.080 23.925 /
\plot 3.080 23.925 3.092 23.929 /
\plot 3.092 23.929 3.101 23.931 /
\plot 3.101 23.931 3.107 23.933 /
\plot 3.107 23.933 3.109 23.933 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setsolid
{\color[rgb]{0,0,0}\putrule from 7.144 25.241 to 11.906 25.241
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 7.144 23.336 to 11.906 23.336
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 8.572 24.646 to 8.572 23.813
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 8.572 23.813 to 9.404 23.813
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 9.644 23.813 to 10.478 23.813
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.478 23.813 to 10.478 24.646
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.357 24.765 to 9.525 24.765
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 9.525 24.765 to 8.691 24.765
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 9.525 24.765 to 9.525 23.933
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.596 24.765 to 11.906 24.765
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 7.144 23.813 to 8.572 23.813
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\putrule from 7.144 24.765 to 8.452 24.765
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\putrule from 10.596 23.813 to 11.906 23.813
}%
\linethickness=0pt
\putrectangle corners at 0.207 26.105 and 11.953 22.473
\endpicture}
\end{center}
\caption{\label{cap:K5-na-toru}$K_{5}$ na toru a $K_{3,3}$ na Möbiově listu}
\end{figure}
\medskip{}
Lze dokázat zobecnění Kuratowského věty, které zhruba tvrdí: Pro každou
plochu existuje konečný počet ,,zakázaných{}`` grafů takových, že
každý graf $G$ lze namalovat do této plochy bez křížení hran, právě
když $G$ neobsahuje jako podgraf dělení nějakého zakázaného grafu.
Naopak, pro každý graf existuje plocha, do níž je možné jej namalovat
bez křížení hran.
\end{rem*}
\begin{thm}
\textbf{\emph{(Euler)}}
Pro každý konvexní mnohostěn platí:
\hfill{}(počet vrcholů) $-$ (počet hran) $+$ (počet stěn) $=2$\hfill{}~
\end{thm}
Známá Eulerova věta se snadno dokáže pomocí následující věty:
\begin{thm}
\label{thm:hrany-vrcholy-oblasti}Nechť $G=(V,E)$ je souvislý planární
graf. Označme $\Phi(G)$ počet oblastí, na něž se rozpadne rovina
po namalování grafu $G$. Potom platí\[
\# V-\# E+\Phi(G)=2.\]
\end{thm}
\begin{rem*}
Rozmyslete si, zda je $\Phi(G)$ skutečně definováno jednoznačně,
tj. že nezávisí na způsobu namalování grafu $G$.
\end{rem*}
\begin{rem*}
Eulerova věta je přímým důsledkem naší věty. Převod konvexního mnohostěnu
na souvislý planární graf provedeme tak, že odebereme jednu jeho stěnu.
Ze zbytku vnikne zdeformovaná síť mnohostěnu, kterou zobrazíme do
roviny. Odebraná stěna pak představuje vnějšek grafu, jdoucí v rovině
do nekonečna.
\end{rem*}
\begin{proof}
Indukcí podle $\Phi(G)$:
$\Phi(G)=1$ $\Leftrightarrow$ v $G$ není kružnice $\Leftrightarrow$
$G$ je strom. (Je zřejmé, že každý strom lze namalovat do roviny.)
Ve stromu platí $\# E=\# V-1$, takže po dosazení vyjde $\# V-\# E+\Phi(G)=\# V-(\# V-1)+1=2$.
Indukční krok: $\Phi(G)\geq2$ $\Rightarrow$ existuje hrana $e\in E$,
po jejíž stranách leží dvě různé oblasti roviny. Tuto hranu ubereme.
Potom pro graf $G\backslash e$ je $\Phi(G\backslash e)=\Phi(G)-1$.
Počet oblastí se zmenší právě o $1$, neboť dvě oblasti na obou stranách
hrany $e$ se spojí do jedné. Z indukčního předpokladu platí\[
\# V-(\# E-1)+(\Phi(G)-1)=2\]
a z toho už vychází\[
\# V-\# E+\Phi(G)=2.\]
\end{proof}
\begin{rem*}
Věta platí i pro grafy se smyčkami a násobnými hranami, které mají
vliv na $\Phi(G)$. V dalším se však budeme zabývat již pouze grafy
bez násobných hran a smyček.
\end{rem*}
\begin{thm}
\label{thm:podminka-planarity}Nechť $G=(V,E)$ je souvislý planární
graf (bez násobných hran a smyček), nechť $\# V=n\geq3$. Potom\[
\# E\leq3\# V-6.\]
\end{thm}
\begin{proof}
Odhadneme shora i zdola součet\[
\sum_{i=1}^{\Phi(G)}\nu(\Omega_{i}),\]
kde sčítáme přes všechny oblasti roviny a $\nu(\Omega_{i})$ vyjadřuje
počet hran, které tvoří hranici oblasti $\Omega_{i}$. Pro odhad zdola
využijeme, že hranice každé oblasti je tvořena alespoň třemi hranami.
Pro odhad shora naopak použijeme, že každá hrana může tvořit část
hranice jen dvou různých oblastí, a nebo netvoří část žádné hranice.
Proto\[
3\Phi(G)\leq\sum_{i=1}^{\Phi(G)}\nu(\Omega_{i})\leq2\# E.\]
Dosadíme-li nyní z předchozí věty za $\Phi(G)$, dostaneme\begin{eqnarray*}
3(2+\# E-\# V) & \leq & 2\# E\\
\# E & \leq & 3\# V-6.\end{eqnarray*}
\end{proof}
\begin{cor*}
$K_{5}$ není planární.
\end{cor*}
\begin{proof}
$K_{5}$ nesplňuje nerovnost z předchozí věty. Platí pro něj totiž\[
\# E=\binom{5}{2}=10>9=3\cdot5-6=3\# V-6.\]
\end{proof}
\begin{prop*}
$K_{3,3}$ není planární.
\end{prop*}
\begin{proof}
Nyní nemůžeme přímo využít minulou větu, neboť $K_{3,3}$ má $\# V=6,\# E=9$
a nerovnost \ref{thm:podminka-planarity} splňuje. Pomůže nám ale
dodatečný předpoklad. Je-li totiž $G$ bipartitní, tak neobsahuje
liché kružnice, takže hranice každé oblasti v rovině je tvořena nejméně
čtyřmi hranami. Potom lze odvodit přísnější nerovnost:\[
4\Phi(G)\leq\sum_{i=1}^{\Phi(G)}\nu(\Omega_{i})\leq2\# E,\]
z čehož dostaneme\[
2\Phi(G)\leq\# E\]
a po dosazení za $\Phi(G)$ z věty \ref{thm:hrany-vrcholy-oblasti}
máme\[
\# E\leq2\# V-4.\]
Pro bipartitní graf $K_{3,3}$ však platí\[
\# E=9>8=2\cdot6-4=2\# V-4,\]
takže nemůže být planární.
\end{proof}
\subsection{Barevnost planárních grafů}
\begin{thm}
Nechť $G=(V,E)$ je souvislý planární graf (bez násobných hran a smyček).
Potom \[
\delta(G)\leq5.\]
\end{thm}
\begin{proof}
Zřejmě\[
\delta(G)\cdot\# V\leq\sum_{v\in V}d_{G}(v)=2\# E.\]
Z toho plyne\[
\delta(G)\cdot\# V\leq2\# E\leq2(3\# V-6)=6\# V-12\]
\[
\delta(G)\leq\frac{6\# V-12}{\# V}=6-\frac{12}{\# V}\]
a protože $\delta(G)\in\N_{0}$, tak zřejmě $\delta(G)\leq5$.
\end{proof}
\begin{cor}
Je-li $G$ planární, potom $\chi(G)\leq6$.
\end{cor}
\begin{proof}
Indukcí podle počtu vrcholů $\# V$. Vezmeme vrchol $v\in V$, který
má minimální stupeň. Potom\[
d_{G}(v)=\delta(G)\leq5.\]
Graf $G\backslash v$ je z indukčního předpokladu možné obarvit $6$
barvami. Když $v$ opět přidáme, je jasné, že na něj jedna barva ze
šesti vyjde, neboť má nejvýše $5$ sousedů.
\end{proof}
\begin{thm}
Je-li $G=(V,E)$ planární graf, potom $\chi(G)\leq5$.
\end{thm}
\begin{proof}
Sporem. Nechť $\chi(G)>5$, takže podle předchozí věty $\chi(G)=6$.
BÚNO předpokládejme, že $G$ je $6$-kritický. Pokud tomu tak není,
lze z něj ubírat hrany tak dlouho, dokud se $6$-kritickým nestane,
přičemž zřejmě bude stále planární.
Víme, že $k$-kritické grafy jsou souvislé a platí pro ně $\delta(G)\geq k-1$.
V našem případě máme
\begin{itemize}
\item $G$ je planární $\Rightarrow$ $\delta(G)\leq5$,
\item $G$ je $6$-kritický $\Rightarrow$ $\delta(G)\geq5$,
\end{itemize}
takže $\delta(G)=5$. Vezměme $v\in V$ takový, že $d_{G}(v)=5$.
Protože $G$ je $6$-kritický, tak $\chi(G\backslash v)=5$ (z definice
je $\chi(G\backslash v)\leq5$, je ale jasné, že nemůže být $\chi(G\backslash v)<5$)
a navíc při každém vlastním obarvení grafu $G\backslash v$ pomocí
$5$ barev se na $5$ sousedech vrcholu $u$ musí vyskytovat všech
$5$ barev, jinak by i $\chi(G)=5$, což by byl spor.
Nechť má tedy $v$ sousedy $u_{1},...,u_{5}$, kde $u_{i}$ má (při
nějakém pevném vlastním $5$-vrcholovém obarvení $\varphi$) barvu
$i$, a nechť jsou tyto vrcholy při namalování $G$ rozmístěny jako
na obrázku.
\hfill{}
\begin{center}
%Title: planar_barevnost1.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:35:20 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}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 18.098
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.954 18.098
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.430 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.001 20.479
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.001 19.050
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.001 19.050 8.572 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.001 19.050 9.049 18.098 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.001 19.050 10.954 18.098 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.001 19.050 11.430 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.001 19.050 to 10.001 20.479
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{5}$}%
} [lB] at 7.857 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{4}$}%
} [lB] at 8.215 17.979
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{3}$}%
} [lB] at 11.430 17.979
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{2}$}%
} [lB] at 11.906 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{1}$}%
} [lB] at 9.762 21.076
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}%
} [lB] at 9.881 18.337
\linethickness=0pt
\putrectangle corners at 7.825 21.558 and 11.938 17.780
\endpicture}
\end{center}
\hfill{}
Uvažujme podgraf $G[\varphi^{-1}(1)\cup\varphi^{-1}(3)]$ grafu $G$
indukovaný vrcholy s barvou $1$ a $3$. Potom $u_{1}$ a $u_{3}$
jsou ve stejné komponentě tohoto podgrafu. Pokud by tomu tak nebylo,
zaměnili bychom např. v komponentě, ve které je $u_{1}$, barvy $1$
a $3$. Obarvení celého grafu by zůstalo vlastní, ale pak $u_{1}$
by měl také barvu $3$ a sousedé $v$ by neměly $5$ různých barev,
což je spor. Proto existuje cesta z $u_{1}$ do $u_{3}$ pouze po
vrcholech barvy $1$ a $3$. Toto tvrzení si pro účely poznámky za
důkazem označme jako $(\mathbf{*})$.
Ze stejného důvodu existuje cesta z $u_{2}$ do $u_{4}$ pouze po
vrcholech barvy $2$ a $4$. Tyto cesty se musí někde protínat. Protože
$G$ je planární, musí to být v nějakém vrcholu, který pak má barvu
$b\in\{1,3\}\cap\{2,4\}$, což je spor.
\hfill{}
\begin{center}
%Title: planar_barevnost2.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 20:14:08 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}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 3.452 25.838
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 4.405 25.362
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 4.405 23.220
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.261 21.791
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 4.166 21.791
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 5.118 22.981
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 4.642 24.172
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 1.547 23.218
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.452 23.218
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.929 24.646
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 1.071 24.646
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.500 25.599
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.500 24.170
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 3.929 24.646 4.642 24.170 /
\plot 4.642 24.170 5.118 22.981 /
\plot 5.118 22.981 4.166 21.789 /
\putrule from 4.166 21.789 to 2.261 21.789
\plot 2.261 21.789 1.547 23.218 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 2.500 25.599 3.452 25.838 /
\plot 3.452 25.838 4.405 25.362 /
\plot 4.405 25.362 4.642 24.170 /
\plot 4.642 24.170 4.405 23.218 /
\putrule from 4.405 23.218 to 3.421 23.218
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.500 24.170 1.071 24.646 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.500 24.170 1.547 23.218 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.500 24.170 3.452 23.218 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 2.500 24.170 3.929 24.646 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 2.500 24.170 to 2.500 25.599
}%
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3=4}%
} [lB] at 4.822 23.992
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}4}%
} [lB] at 1.844 23.040
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at 2.201 21.374
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}4}%
} [lB] at 4.106 21.372
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at 5.355 22.862
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at 3.808 24.886
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}%
} [lB] at 3.035 23.040
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at 4.346 22.801
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at 4.583 25.243
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}%
} [lB] at 3.391 26.016
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at 2.083 25.421
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{5}$}%
} [lB] at 0.356 24.528
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{4}$}%
} [lB] at 0.713 23.099
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{3}$}%
} [lB] at 3.334 22.502
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{2}$}%
} [lB] at 3.749 24.052
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u_{1}$}%
} [lB] at 2.261 26.196
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}%
} [lB] at 2.379 23.457
\linethickness=0pt
\putrectangle corners at 0.324 26.676 and 5.387 21.340
\endpicture}
\end{center}
\hfill{}~
\end{proof}
\begin{rem*}
Vrchol $v_{5}$ jsme v důkazu vůbec nepoužili. Nabízí se otázka, zda
by tedy stejným způsobem nešlo dokázat $\chi(G)\leq4$.
Zkusíme tedy důkaz sporem. Nechť $\chi(G)>4$, tj. $\chi(G)=5$. Potom
pro $5$-kritický graf dostaneme $\delta(G)\geq4$ a z planarity opět
$\delta(G)\leq5$. Proto $\delta(G)\in\{4,5\}$.
\begin{itemize}
\item Pokud $\delta(G)=4$, pak $\left(\exists v\in V\right)\left(d_{G}(v)=4\right)$.
Platí $\chi(G\backslash v)=4$ a tím pádem při každém vlastním $4$-vrcholovém
obarvení $G\backslash v$ musí být na $4$ sousedech $v$ všechny
$4$ barvy. Důkaz až do konce je pak stejný, dostaneme spor s planaritou.
\item Pokud $\delta(G)=5$, pak $\left(\exists v\in V\right)\left(d_{G}(v)=5\right)$
a situace vypadá přesně jako na prvním obrázku v důkazu věty. Platí
ovšem opět $\chi(G\backslash v)=4$ a tak při každém vlastním $4$-vrcholovém
obarvení $G\backslash v$ musí být na $5$ sousedech $v$ právě $4$
barvy. Právě dva vrcholy z $u_{1},...,u_{5}$ mají tedy stejnou barvu.
Očíslujme si vrcholy tak, že při namalování $G$ jdou čísla opět po
sobě jako na obrázku, a vrchol $u_{5}$ má stejnou barvu jako jeden
z vrcholů $u_{1},...,u_{4}$, které tak mají $4$ různé barvy. Takové
očíslování vždy existuje. Potom nemusí platit $(\mathbf{*})$: Jestliže
totiž $u_{5}$ má barvu $3$ a leží ve stejné komponentě grafu $G[\varphi^{-1}(1)\cup\varphi^{-1}(3)]$
jako $u_{1}$ a zaměníme-li barvy $1$ a $3$ v této komponentě, bude
mít $v$ stále $5$ sousedů s právě $4$ barvami a ke sporu nedojde.
Pokud zaměníme barvy v komponentě, kde leží vrchol $u_{3}$, budou
mít sice $u_{3}$ i $u_{1}$ barvu $1$, ale $u_{5}$ bude mít stále
barvu $3$ a opět ke sporu nedojde.\\
Různé kombinace barvy a umístění vrcholu $u_{5}$ nám v obecném planárním
grafu $G$ nedovolí dokázat tvrzení $(\mathbf{*})$ vždy nejvýše pro
jednu z dvojic vrcholů $u_{1},u_{3}$ a $u_{2},u_{4}$. Celkově tedy
nelze důkaz nerovnosti $\chi(G)\leq4$ tímto způsobem provést.
\end{itemize}
\end{rem*}
\begin{rem*}
I když se nám nepodařilo dokázat $\chi(G)\leq4$ pro každý planární
graf, je známo, že toto tvrzení platí. Všichni jej známe v podobě
,,K obarvení každé politické mapy tak, aby žádné dva stejně barevné
státy neměly společnou hranici (nenulové délky), stačí čtyři barvy.{}``.
Dlouho však bylo uváděno pouze jako domněnka, teprve v roce 1976 jej
dokázali K. Appel a W. Haken. Jeho důkaz si vyžádal použití počítače
poté, co bylo toto tvrzení pro obecný planární graf transformováno
na stejné tvrzení pro desítky speciálních případů, u kterých jej již
bylo možné ověřit ,,hrubou silou{}``. Jen zmíněné transformace prý
vydají na knihu o asi dvou stech stranách...
\end{rem*}
\subsection{Minimální počet křížení v grafu}
\begin{defn}
\textbf{Minimální počet křížení} (angl. \emph{crossing number}) $\crs(G)$
grafu $G$ je minimální počet dvojic hran, které se po namalování
grafu $G$ do roviny kříží.
\end{defn}
\begin{rem*}
$\crs(G)$ není počet průsečíků hran. $G$ je planární právě tehdy,
když $\crs(G)=0$.
\end{rem*}
\begin{rem*}
Jak namalovat $G$ s co nejmenším počtem křížení? Podívejme se na
obrázek \ref{cap:crossing}: %
\begin{figure}
\begin{center}¨
%Title: crossing.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 23:02:00 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}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.144 22.860
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 22.860
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 23.813
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.144 23.813
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.144 25.241
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 25.241
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 26.194
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.144 26.194
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 5.715 23.336
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.810 22.860
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.810 23.813
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 5.715 25.718
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.810 25.241
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.810 26.194
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 0.953 22.860
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 0.953 23.813
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 0.953 25.241
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 0.953 26.194
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
{\color[rgb]{0,0,0}\putrule from 8.096 25.004 to 8.096 24.170
%
% arrow head
%
\plot 7.944 24.678 8.096 24.170 8.249 24.678 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
{\color[rgb]{0,0,0}\putrule from 4.763 25.004 to 4.763 24.170
%
% arrow head
%
\plot 4.610 24.678 4.763 24.170 4.915 24.678 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
{\color[rgb]{0,0,0}\putrule from 1.905 25.004 to 1.905 24.170
%
% arrow head
%
\plot 1.753 24.678 1.905 24.170 2.057 24.678 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 8.572 23.218 9.049 22.860 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.144 22.860 7.620 23.218 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 8.572 23.457 9.049 23.813 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.144 23.813 7.620 23.457 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.620 23.218 7.624 23.213 /
\plot 7.624 23.213 7.635 23.203 /
\plot 7.635 23.203 7.652 23.188 /
\plot 7.652 23.188 7.675 23.167 /
\plot 7.675 23.167 7.705 23.142 /
\plot 7.705 23.142 7.739 23.114 /
\plot 7.739 23.114 7.777 23.086 /
\plot 7.777 23.086 7.819 23.059 /
\plot 7.819 23.059 7.863 23.036 /
\plot 7.863 23.036 7.912 23.015 /
\plot 7.912 23.015 7.967 22.998 /
\plot 7.967 22.998 8.029 22.985 /
\plot 8.029 22.985 8.096 22.981 /
\plot 8.096 22.981 8.164 22.985 /
\plot 8.164 22.985 8.225 22.998 /
\plot 8.225 22.998 8.280 23.015 /
\plot 8.280 23.015 8.329 23.036 /
\plot 8.329 23.036 8.374 23.059 /
\plot 8.374 23.059 8.416 23.086 /
\plot 8.416 23.086 8.454 23.114 /
\plot 8.454 23.114 8.488 23.142 /
\plot 8.488 23.142 8.517 23.167 /
\plot 8.517 23.167 8.541 23.188 /
\plot 8.541 23.188 8.558 23.203 /
\plot 8.558 23.203 8.568 23.213 /
\plot 8.568 23.213 8.572 23.218 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.620 23.457 7.624 23.461 /
\plot 7.624 23.461 7.635 23.472 /
\plot 7.635 23.472 7.652 23.487 /
\plot 7.652 23.487 7.675 23.508 /
\plot 7.675 23.508 7.705 23.533 /
\plot 7.705 23.533 7.739 23.561 /
\plot 7.739 23.561 7.777 23.588 /
\plot 7.777 23.588 7.819 23.616 /
\plot 7.819 23.616 7.863 23.639 /
\plot 7.863 23.639 7.912 23.660 /
\plot 7.912 23.660 7.967 23.677 /
\plot 7.967 23.677 8.029 23.690 /
\plot 8.029 23.690 8.096 23.694 /
\plot 8.096 23.694 8.164 23.690 /
\plot 8.164 23.690 8.225 23.677 /
\plot 8.225 23.677 8.280 23.660 /
\plot 8.280 23.660 8.329 23.639 /
\plot 8.329 23.639 8.374 23.616 /
\plot 8.374 23.616 8.416 23.588 /
\plot 8.416 23.588 8.454 23.561 /
\plot 8.454 23.561 8.488 23.533 /
\plot 8.488 23.533 8.517 23.508 /
\plot 8.517 23.508 8.541 23.487 /
\plot 8.541 23.487 8.558 23.472 /
\plot 8.558 23.472 8.568 23.461 /
\plot 8.568 23.461 8.572 23.457 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.144 25.241 7.146 25.245 /
\plot 7.146 25.245 7.152 25.254 /
\plot 7.152 25.254 7.163 25.269 /
\plot 7.163 25.269 7.178 25.290 /
\plot 7.178 25.290 7.199 25.322 /
\plot 7.199 25.322 7.226 25.358 /
\plot 7.226 25.358 7.260 25.402 /
\plot 7.260 25.402 7.296 25.451 /
\plot 7.296 25.451 7.336 25.502 /
\plot 7.336 25.502 7.383 25.555 /
\plot 7.383 25.555 7.430 25.607 /
\plot 7.430 25.607 7.480 25.660 /
\plot 7.480 25.660 7.531 25.711 /
\plot 7.531 25.711 7.588 25.758 /
\plot 7.588 25.758 7.648 25.804 /
\plot 7.648 25.804 7.709 25.845 /
\plot 7.709 25.845 7.777 25.880 /
\plot 7.777 25.880 7.849 25.912 /
\plot 7.849 25.912 7.927 25.936 /
\plot 7.927 25.936 8.009 25.950 /
\plot 8.009 25.950 8.096 25.957 /
\plot 8.096 25.957 8.183 25.950 /
\plot 8.183 25.950 8.266 25.936 /
\plot 8.266 25.936 8.344 25.912 /
\plot 8.344 25.912 8.416 25.880 /
\plot 8.416 25.880 8.484 25.845 /
\plot 8.484 25.845 8.545 25.804 /
\plot 8.545 25.804 8.604 25.758 /
\plot 8.604 25.758 8.661 25.711 /
\plot 8.661 25.711 8.712 25.660 /
\plot 8.712 25.660 8.763 25.607 /
\plot 8.763 25.607 8.812 25.555 /
\plot 8.812 25.555 8.856 25.502 /
\plot 8.856 25.502 8.896 25.451 /
\plot 8.896 25.451 8.932 25.402 /
\plot 8.932 25.402 8.966 25.358 /
\plot 8.966 25.358 8.994 25.322 /
\plot 8.994 25.322 9.015 25.290 /
\plot 9.015 25.290 9.030 25.269 /
\plot 9.030 25.269 9.040 25.254 /
\plot 9.040 25.254 9.047 25.245 /
\plot 9.047 25.245 9.049 25.241 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.144 26.194 7.146 26.190 /
\plot 7.146 26.190 7.152 26.181 /
\plot 7.152 26.181 7.163 26.166 /
\plot 7.163 26.166 7.178 26.145 /
\plot 7.178 26.145 7.199 26.113 /
\plot 7.199 26.113 7.226 26.077 /
\plot 7.226 26.077 7.260 26.033 /
\plot 7.260 26.033 7.296 25.986 /
\plot 7.296 25.986 7.336 25.936 /
\plot 7.336 25.936 7.383 25.883 /
\plot 7.383 25.883 7.430 25.828 /
\plot 7.430 25.828 7.480 25.777 /
\plot 7.480 25.777 7.531 25.726 /
\plot 7.531 25.726 7.588 25.677 /
\plot 7.588 25.677 7.648 25.633 /
\plot 7.648 25.633 7.709 25.593 /
\plot 7.709 25.593 7.777 25.557 /
\plot 7.777 25.557 7.849 25.525 /
\plot 7.849 25.525 7.927 25.502 /
\plot 7.927 25.502 8.009 25.487 /
\plot 8.009 25.487 8.096 25.480 /
\plot 8.096 25.480 8.183 25.487 /
\plot 8.183 25.487 8.266 25.502 /
\plot 8.266 25.502 8.344 25.525 /
\plot 8.344 25.525 8.416 25.557 /
\plot 8.416 25.557 8.484 25.593 /
\plot 8.484 25.593 8.545 25.633 /
\plot 8.545 25.633 8.604 25.677 /
\plot 8.604 25.677 8.661 25.726 /
\plot 8.661 25.726 8.712 25.777 /
\plot 8.712 25.777 8.763 25.828 /
\plot 8.763 25.828 8.812 25.883 /
\plot 8.812 25.883 8.856 25.936 /
\plot 8.856 25.936 8.896 25.986 /
\plot 8.896 25.986 8.932 26.033 /
\plot 8.932 26.033 8.966 26.077 /
\plot 8.966 26.077 8.994 26.113 /
\plot 8.994 26.113 9.015 26.145 /
\plot 9.015 26.145 9.030 26.166 /
\plot 9.030 26.166 9.040 26.181 /
\plot 9.040 26.181 9.047 26.190 /
\plot 9.047 26.190 9.049 26.194 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.286 23.218 4.290 23.216 /
\plot 4.290 23.216 4.299 23.209 /
\plot 4.299 23.209 4.316 23.199 /
\plot 4.316 23.199 4.341 23.184 /
\plot 4.341 23.184 4.373 23.163 /
\plot 4.373 23.163 4.413 23.139 /
\plot 4.413 23.139 4.462 23.112 /
\plot 4.462 23.112 4.513 23.080 /
\plot 4.513 23.080 4.570 23.051 /
\plot 4.570 23.051 4.627 23.019 /
\plot 4.627 23.019 4.688 22.989 /
\plot 4.688 22.989 4.750 22.962 /
\plot 4.750 22.962 4.815 22.934 /
\plot 4.815 22.934 4.881 22.911 /
\plot 4.881 22.911 4.949 22.892 /
\plot 4.949 22.892 5.019 22.875 /
\plot 5.019 22.875 5.093 22.864 /
\plot 5.093 22.864 5.165 22.858 /
\plot 5.165 22.858 5.239 22.860 /
\plot 5.239 22.860 5.315 22.871 /
\plot 5.315 22.871 5.381 22.892 /
\plot 5.381 22.892 5.440 22.917 /
\plot 5.440 22.917 5.486 22.947 /
\plot 5.486 22.947 5.529 22.981 /
\plot 5.529 22.981 5.563 23.017 /
\plot 5.563 23.017 5.592 23.057 /
\plot 5.592 23.057 5.618 23.097 /
\plot 5.618 23.097 5.641 23.139 /
\plot 5.641 23.139 5.660 23.180 /
\plot 5.660 23.180 5.675 23.220 /
\plot 5.675 23.220 5.690 23.254 /
\plot 5.690 23.254 5.698 23.283 /
\plot 5.698 23.283 5.707 23.307 /
\plot 5.707 23.307 5.711 23.324 /
\plot 5.711 23.324 5.713 23.332 /
\plot 5.713 23.332 5.715 23.336 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.286 23.457 4.290 23.459 /
\plot 4.290 23.459 4.299 23.465 /
\plot 4.299 23.465 4.316 23.476 /
\plot 4.316 23.476 4.341 23.491 /
\plot 4.341 23.491 4.373 23.512 /
\plot 4.373 23.512 4.413 23.535 /
\plot 4.413 23.535 4.462 23.563 /
\plot 4.462 23.563 4.513 23.592 /
\plot 4.513 23.592 4.570 23.624 /
\plot 4.570 23.624 4.627 23.654 /
\plot 4.627 23.654 4.688 23.683 /
\plot 4.688 23.683 4.750 23.713 /
\plot 4.750 23.713 4.815 23.738 /
\plot 4.815 23.738 4.881 23.762 /
\plot 4.881 23.762 4.949 23.783 /
\plot 4.949 23.783 5.019 23.798 /
\plot 5.019 23.798 5.093 23.810 /
\plot 5.093 23.810 5.165 23.815 /
\plot 5.165 23.815 5.239 23.813 /
\plot 5.239 23.813 5.315 23.802 /
\plot 5.315 23.802 5.381 23.781 /
\plot 5.381 23.781 5.440 23.755 /
\plot 5.440 23.755 5.486 23.726 /
\plot 5.486 23.726 5.529 23.692 /
\plot 5.529 23.692 5.563 23.656 /
\plot 5.563 23.656 5.592 23.616 /
\plot 5.592 23.616 5.618 23.575 /
\plot 5.618 23.575 5.641 23.533 /
\plot 5.641 23.533 5.660 23.493 /
\plot 5.660 23.493 5.675 23.453 /
\plot 5.675 23.453 5.690 23.419 /
\plot 5.690 23.419 5.698 23.389 /
\plot 5.698 23.389 5.707 23.366 /
\plot 5.707 23.366 5.711 23.349 /
\plot 5.711 23.349 5.713 23.340 /
\plot 5.713 23.340 5.715 23.336 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 3.810 22.860 4.286 23.218 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 3.810 23.813 4.286 23.457 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.286 25.718 4.290 25.715 /
\plot 4.290 25.715 4.297 25.709 /
\plot 4.297 25.709 4.310 25.698 /
\plot 4.310 25.698 4.329 25.684 /
\plot 4.329 25.684 4.354 25.665 /
\plot 4.354 25.665 4.388 25.639 /
\plot 4.388 25.639 4.426 25.612 /
\plot 4.426 25.612 4.470 25.578 /
\plot 4.470 25.578 4.517 25.544 /
\plot 4.517 25.544 4.570 25.510 /
\plot 4.570 25.510 4.623 25.474 /
\plot 4.623 25.474 4.678 25.438 /
\plot 4.678 25.438 4.733 25.404 /
\plot 4.733 25.404 4.792 25.372 /
\plot 4.792 25.372 4.851 25.343 /
\plot 4.851 25.343 4.911 25.315 /
\plot 4.911 25.315 4.974 25.292 /
\plot 4.974 25.292 5.038 25.271 /
\plot 5.038 25.271 5.105 25.256 /
\plot 5.105 25.256 5.173 25.245 /
\plot 5.173 25.245 5.239 25.241 /
\plot 5.239 25.241 5.315 25.248 /
\plot 5.315 25.248 5.381 25.262 /
\plot 5.381 25.262 5.440 25.284 /
\plot 5.440 25.284 5.486 25.313 /
\plot 5.486 25.313 5.529 25.347 /
\plot 5.529 25.347 5.563 25.383 /
\plot 5.563 25.383 5.592 25.423 /
\plot 5.592 25.423 5.618 25.466 /
\plot 5.618 25.466 5.641 25.510 /
\plot 5.641 25.510 5.660 25.552 /
\plot 5.660 25.552 5.675 25.593 /
\plot 5.675 25.593 5.690 25.631 /
\plot 5.690 25.631 5.698 25.662 /
\plot 5.698 25.662 5.707 25.686 /
\plot 5.707 25.686 5.711 25.703 /
\plot 5.711 25.703 5.713 25.713 /
\plot 5.713 25.713 5.715 25.718 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.286 25.718 4.290 25.720 /
\plot 4.290 25.720 4.297 25.726 /
\plot 4.297 25.726 4.310 25.737 /
\plot 4.310 25.737 4.329 25.751 /
\plot 4.329 25.751 4.354 25.770 /
\plot 4.354 25.770 4.388 25.796 /
\plot 4.388 25.796 4.426 25.823 /
\plot 4.426 25.823 4.470 25.857 /
\plot 4.470 25.857 4.517 25.891 /
\plot 4.517 25.891 4.570 25.925 /
\plot 4.570 25.925 4.623 25.961 /
\plot 4.623 25.961 4.678 25.997 /
\plot 4.678 25.997 4.733 26.031 /
\plot 4.733 26.031 4.792 26.063 /
\plot 4.792 26.063 4.851 26.092 /
\plot 4.851 26.092 4.911 26.120 /
\plot 4.911 26.120 4.974 26.143 /
\plot 4.974 26.143 5.038 26.164 /
\plot 5.038 26.164 5.105 26.179 /
\plot 5.105 26.179 5.173 26.190 /
\plot 5.173 26.190 5.239 26.194 /
\plot 5.239 26.194 5.315 26.187 /
\plot 5.315 26.187 5.381 26.173 /
\plot 5.381 26.173 5.440 26.151 /
\plot 5.440 26.151 5.486 26.122 /
\plot 5.486 26.122 5.529 26.088 /
\plot 5.529 26.088 5.563 26.052 /
\plot 5.563 26.052 5.592 26.012 /
\plot 5.592 26.012 5.618 25.969 /
\plot 5.618 25.969 5.641 25.925 /
\plot 5.641 25.925 5.660 25.883 /
\plot 5.660 25.883 5.675 25.842 /
\plot 5.675 25.842 5.690 25.804 /
\plot 5.690 25.804 5.698 25.773 /
\plot 5.698 25.773 5.707 25.749 /
\plot 5.707 25.749 5.711 25.732 /
\plot 5.711 25.732 5.713 25.722 /
\plot 5.713 25.722 5.715 25.718 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.286 25.718 3.810 25.241 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 3.810 26.194 4.286 25.718 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 1.429 23.336 to 1.422 23.336
\putrule from 1.422 23.336 to 1.410 23.336
\plot 1.410 23.336 1.393 23.334 /
\plot 1.393 23.334 1.369 23.330 /
\plot 1.369 23.330 1.342 23.321 /
\plot 1.342 23.321 1.310 23.309 /
\plot 1.310 23.309 1.276 23.290 /
\plot 1.276 23.290 1.236 23.260 /
\plot 1.236 23.260 1.190 23.218 /
\plot 1.190 23.218 1.156 23.182 /
\plot 1.156 23.182 1.126 23.146 /
\plot 1.126 23.146 1.099 23.110 /
\plot 1.099 23.110 1.073 23.074 /
\plot 1.073 23.074 1.050 23.038 /
\plot 1.050 23.038 1.031 23.004 /
\plot 1.031 23.004 1.012 22.972 /
\plot 1.012 22.972 0.995 22.940 /
\plot 0.995 22.940 0.980 22.913 /
\plot 0.980 22.913 0.967 22.892 /
\plot 0.967 22.892 0.959 22.875 /
\plot 0.959 22.875 0.955 22.864 /
\plot 0.955 22.864 0.953 22.860 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 0.953 23.813 0.955 23.808 /
\plot 0.955 23.808 0.959 23.798 /
\plot 0.959 23.798 0.967 23.783 /
\plot 0.967 23.783 0.980 23.760 /
\plot 0.980 23.760 0.995 23.732 /
\plot 0.995 23.732 1.012 23.702 /
\plot 1.012 23.702 1.031 23.669 /
\plot 1.031 23.669 1.050 23.635 /
\plot 1.050 23.635 1.073 23.601 /
\plot 1.073 23.601 1.099 23.565 /
\plot 1.099 23.565 1.126 23.529 /
\plot 1.126 23.529 1.156 23.493 /
\plot 1.156 23.493 1.190 23.457 /
\plot 1.190 23.457 1.236 23.415 /
\plot 1.236 23.415 1.276 23.385 /
\plot 1.276 23.385 1.310 23.366 /
\plot 1.310 23.366 1.342 23.353 /
\plot 1.342 23.353 1.369 23.345 /
\plot 1.369 23.345 1.393 23.340 /
\plot 1.393 23.340 1.410 23.338 /
\plot 1.410 23.338 1.422 23.336 /
\putrule from 1.422 23.336 to 1.429 23.336
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 0.953 26.194 0.955 26.192 /
\plot 0.955 26.192 0.961 26.185 /
\plot 0.961 26.185 0.974 26.175 /
\plot 0.974 26.175 0.991 26.160 /
\plot 0.991 26.160 1.016 26.137 /
\plot 1.016 26.137 1.050 26.109 /
\plot 1.050 26.109 1.090 26.075 /
\plot 1.090 26.075 1.137 26.035 /
\plot 1.137 26.035 1.190 25.988 /
\plot 1.190 25.988 1.247 25.940 /
\plot 1.247 25.940 1.310 25.887 /
\plot 1.310 25.887 1.376 25.832 /
\plot 1.376 25.832 1.444 25.777 /
\plot 1.444 25.777 1.513 25.722 /
\plot 1.513 25.722 1.583 25.667 /
\plot 1.583 25.667 1.655 25.612 /
\plot 1.655 25.612 1.725 25.559 /
\plot 1.725 25.559 1.795 25.510 /
\plot 1.795 25.510 1.865 25.461 /
\plot 1.865 25.461 1.935 25.417 /
\plot 1.935 25.417 2.004 25.377 /
\plot 2.004 25.377 2.072 25.339 /
\plot 2.072 25.339 2.140 25.307 /
\plot 2.140 25.307 2.203 25.279 /
\plot 2.203 25.279 2.267 25.258 /
\plot 2.267 25.258 2.326 25.245 /
\plot 2.326 25.245 2.381 25.241 /
\plot 2.381 25.241 2.428 25.245 /
\plot 2.428 25.245 2.468 25.258 /
\plot 2.468 25.258 2.502 25.279 /
\plot 2.502 25.279 2.529 25.307 /
\plot 2.529 25.307 2.553 25.339 /
\plot 2.553 25.339 2.570 25.372 /
\plot 2.570 25.372 2.584 25.411 /
\plot 2.584 25.411 2.595 25.453 /
\plot 2.595 25.453 2.603 25.495 /
\plot 2.603 25.495 2.610 25.538 /
\plot 2.610 25.538 2.614 25.582 /
\plot 2.614 25.582 2.616 25.626 /
\plot 2.616 25.626 2.618 25.673 /
\putrule from 2.618 25.673 to 2.618 25.718
\putrule from 2.618 25.718 to 2.618 25.762
\plot 2.618 25.762 2.616 25.809 /
\plot 2.616 25.809 2.614 25.853 /
\plot 2.614 25.853 2.610 25.897 /
\plot 2.610 25.897 2.603 25.940 /
\plot 2.603 25.940 2.595 25.982 /
\plot 2.595 25.982 2.584 26.024 /
\plot 2.584 26.024 2.570 26.063 /
\plot 2.570 26.063 2.553 26.096 /
\plot 2.553 26.096 2.529 26.128 /
\plot 2.529 26.128 2.502 26.156 /
\plot 2.502 26.156 2.468 26.177 /
\plot 2.468 26.177 2.428 26.190 /
\plot 2.428 26.190 2.381 26.194 /
\plot 2.381 26.194 2.326 26.190 /
\plot 2.326 26.190 2.267 26.177 /
\plot 2.267 26.177 2.203 26.156 /
\plot 2.203 26.156 2.140 26.128 /
\plot 2.140 26.128 2.072 26.096 /
\plot 2.072 26.096 2.004 26.058 /
\plot 2.004 26.058 1.935 26.018 /
\plot 1.935 26.018 1.865 25.974 /
\plot 1.865 25.974 1.795 25.925 /
\plot 1.795 25.925 1.725 25.876 /
\plot 1.725 25.876 1.655 25.823 /
\plot 1.655 25.823 1.583 25.768 /
\plot 1.583 25.768 1.513 25.713 /
\plot 1.513 25.713 1.444 25.658 /
\plot 1.444 25.658 1.376 25.603 /
\plot 1.376 25.603 1.310 25.548 /
\plot 1.310 25.548 1.247 25.495 /
\plot 1.247 25.495 1.190 25.447 /
\plot 1.190 25.447 1.137 25.400 /
\plot 1.137 25.400 1.090 25.360 /
\plot 1.090 25.360 1.050 25.326 /
\plot 1.050 25.326 1.016 25.298 /
\plot 1.016 25.298 0.991 25.275 /
\plot 0.991 25.275 0.974 25.260 /
\plot 0.974 25.260 0.961 25.250 /
\plot 0.961 25.250 0.955 25.243 /
\plot 0.955 25.243 0.953 25.241 /
}%
\linethickness=0pt
\putrectangle corners at 0.817 26.327 and 9.184 22.727
\endpicture}
\end{center}
\caption{\label{cap:crossing}Zbytečné křížení hran a jeho odstranění}
\end{figure}
\begin{itemize}
\item Jedna hrana se nemusí křížit sama se sebou.
\item Dvě hrany, které mají společný vrchol, se nemusejí křížit.
\item Žádná dvojice hran se nemusí křížit více než jednou.
\end{itemize}
\end{rem*}
\begin{thm}
Nech\'{t} $G=(V,E)$ je graf. Potom platí\[
\# E-3\# V+6\leq\crs(G).\]
\end{thm}
\begin{proof}
Namalujme graf $G$ tak, že počet křížení v obrázku je právě $\crs(G)$.
Na místě každého kžížení přidáme vrchol. Tím za každé křížení přibude
$1$ nový vrchol a $2$ nové hrany. Dostaneme planární graf s počtem
vrcholů $\# V+\crs(G)$ a počtem hran $\# E+2\crs(G)$. Pro planární
graf platí věta \ref{thm:podminka-planarity}, tj. $\# E\leq3\# V-6$.
Po dosazení našich hodnot máme\[
\# E+2\crs(G)\leq3(\# V+\crs(G))-6\]
a z toho už\[
\# E-3\# V+6\leq\crs(G).\]
\end{proof}
\begin{example*}
Pro $G=K_{6}$ platí $\# E=15,\# V=6$, takže vychází nerovnost $3\leq\crs(G)$.
Podle obrázku \ref{cap:crossingK6} jsme schopni tří křížení dosáhnout,
takže $\crs(G)=3$. %
\begin{figure}
\begin{center}
%Title: crossingK6.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:27:52 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=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\ellipticalarc axes ratio 0.207:0.207 360 degrees
from 10.446 19.289 center at 10.238 19.289
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\ellipticalarc axes ratio 0.207:0.207 360 degrees
from 10.446 20.508 center at 10.238 20.508
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\ellipticalarc axes ratio 0.207:0.207 360 degrees
from 10.446 22.236 center at 10.238 22.236
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 13.335 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.430 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.383 21.431
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.144 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.096 21.431
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.144 20.003 7.146 19.998 /
\plot 7.146 19.998 7.150 19.990 /
\plot 7.150 19.990 7.159 19.973 /
\plot 7.159 19.973 7.173 19.947 /
\plot 7.173 19.947 7.192 19.911 /
\plot 7.192 19.911 7.218 19.865 /
\plot 7.218 19.865 7.247 19.808 /
\plot 7.247 19.808 7.286 19.740 /
\plot 7.286 19.740 7.328 19.666 /
\plot 7.328 19.666 7.374 19.583 /
\plot 7.374 19.583 7.425 19.497 /
\plot 7.425 19.497 7.480 19.406 /
\plot 7.480 19.406 7.537 19.312 /
\plot 7.537 19.312 7.595 19.221 /
\plot 7.595 19.221 7.654 19.130 /
\plot 7.654 19.130 7.713 19.044 /
\plot 7.713 19.044 7.775 18.959 /
\plot 7.775 18.959 7.834 18.879 /
\plot 7.834 18.879 7.893 18.802 /
\plot 7.893 18.802 7.952 18.733 /
\plot 7.952 18.733 8.009 18.665 /
\plot 8.009 18.665 8.069 18.603 /
\plot 8.069 18.603 8.128 18.546 /
\plot 8.128 18.546 8.187 18.493 /
\plot 8.187 18.493 8.249 18.445 /
\plot 8.249 18.445 8.310 18.400 /
\plot 8.310 18.400 8.374 18.358 /
\plot 8.374 18.358 8.439 18.320 /
\plot 8.439 18.320 8.507 18.284 /
\plot 8.507 18.284 8.579 18.250 /
\plot 8.579 18.250 8.653 18.218 /
\plot 8.653 18.218 8.716 18.193 /
\plot 8.716 18.193 8.782 18.167 /
\plot 8.782 18.167 8.852 18.146 /
\plot 8.852 18.146 8.922 18.125 /
\plot 8.922 18.125 8.996 18.104 /
\plot 8.996 18.104 9.072 18.085 /
\plot 9.072 18.085 9.150 18.068 /
\plot 9.150 18.068 9.231 18.051 /
\plot 9.231 18.051 9.313 18.034 /
\plot 9.313 18.034 9.400 18.021 /
\plot 9.400 18.021 9.487 18.009 /
\plot 9.487 18.009 9.576 17.998 /
\plot 9.576 17.998 9.667 17.987 /
\plot 9.667 17.987 9.760 17.979 /
\plot 9.760 17.979 9.855 17.973 /
\plot 9.855 17.973 9.950 17.966 /
\plot 9.950 17.966 10.046 17.962 /
\plot 10.046 17.962 10.143 17.960 /
\putrule from 10.143 17.960 to 10.240 17.960
\putrule from 10.240 17.960 to 10.336 17.960
\plot 10.336 17.960 10.433 17.962 /
\plot 10.433 17.962 10.528 17.966 /
\plot 10.528 17.966 10.624 17.973 /
\plot 10.624 17.973 10.719 17.979 /
\plot 10.719 17.979 10.812 17.987 /
\plot 10.812 17.987 10.903 17.998 /
\plot 10.903 17.998 10.992 18.009 /
\plot 10.992 18.009 11.079 18.021 /
\plot 11.079 18.021 11.165 18.034 /
\plot 11.165 18.034 11.248 18.051 /
\plot 11.248 18.051 11.328 18.068 /
\plot 11.328 18.068 11.407 18.085 /
\plot 11.407 18.085 11.483 18.104 /
\plot 11.483 18.104 11.557 18.125 /
\plot 11.557 18.125 11.627 18.146 /
\plot 11.627 18.146 11.697 18.167 /
\plot 11.697 18.167 11.762 18.193 /
\plot 11.762 18.193 11.828 18.218 /
\plot 11.828 18.218 11.900 18.250 /
\plot 11.900 18.250 11.972 18.284 /
\plot 11.972 18.284 12.040 18.320 /
\plot 12.040 18.320 12.105 18.358 /
\plot 12.105 18.358 12.169 18.400 /
\plot 12.169 18.400 12.230 18.445 /
\plot 12.230 18.445 12.291 18.493 /
\plot 12.291 18.493 12.351 18.546 /
\plot 12.351 18.546 12.410 18.603 /
\plot 12.410 18.603 12.469 18.665 /
\plot 12.469 18.665 12.526 18.733 /
\plot 12.526 18.733 12.586 18.802 /
\plot 12.586 18.802 12.645 18.879 /
\plot 12.645 18.879 12.704 18.959 /
\plot 12.704 18.959 12.766 19.044 /
\plot 12.766 19.044 12.825 19.130 /
\plot 12.825 19.130 12.884 19.221 /
\plot 12.884 19.221 12.941 19.312 /
\plot 12.941 19.312 12.998 19.406 /
\plot 12.998 19.406 13.053 19.497 /
\plot 13.053 19.497 13.104 19.583 /
\plot 13.104 19.583 13.151 19.666 /
\plot 13.151 19.666 13.193 19.740 /
\plot 13.193 19.740 13.231 19.808 /
\plot 13.231 19.808 13.261 19.865 /
\plot 13.261 19.865 13.286 19.911 /
\plot 13.286 19.911 13.305 19.947 /
\plot 13.305 19.947 13.320 19.973 /
\plot 13.320 19.973 13.329 19.990 /
\plot 13.329 19.990 13.333 19.998 /
\plot 13.333 19.998 13.335 20.003 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 13.335 20.003 13.333 20.000 /
\plot 13.333 20.000 13.329 19.996 /
\plot 13.329 19.996 13.322 19.988 /
\plot 13.322 19.988 13.310 19.975 /
\plot 13.310 19.975 13.293 19.956 /
\plot 13.293 19.956 13.269 19.933 /
\plot 13.269 19.933 13.242 19.903 /
\plot 13.242 19.903 13.208 19.867 /
\plot 13.208 19.867 13.168 19.829 /
\plot 13.168 19.829 13.125 19.784 /
\plot 13.125 19.784 13.075 19.738 /
\plot 13.075 19.738 13.022 19.689 /
\plot 13.022 19.689 12.965 19.638 /
\plot 12.965 19.638 12.903 19.586 /
\plot 12.903 19.586 12.840 19.535 /
\plot 12.840 19.535 12.770 19.482 /
\plot 12.770 19.482 12.700 19.431 /
\plot 12.700 19.431 12.624 19.382 /
\plot 12.624 19.382 12.545 19.334 /
\plot 12.545 19.334 12.463 19.289 /
\plot 12.463 19.289 12.374 19.247 /
\plot 12.374 19.247 12.281 19.207 /
\plot 12.281 19.207 12.181 19.171 /
\plot 12.181 19.171 12.073 19.137 /
\plot 12.073 19.137 11.959 19.107 /
\plot 11.959 19.107 11.836 19.084 /
\plot 11.836 19.084 11.707 19.065 /
\plot 11.707 19.065 11.572 19.054 /
\plot 11.572 19.054 11.430 19.050 /
\plot 11.430 19.050 11.303 19.054 /
\plot 11.303 19.054 11.178 19.063 /
\plot 11.178 19.063 11.055 19.078 /
\plot 11.055 19.078 10.935 19.097 /
\plot 10.935 19.097 10.818 19.120 /
\plot 10.818 19.120 10.706 19.145 /
\plot 10.706 19.145 10.598 19.177 /
\plot 10.598 19.177 10.494 19.209 /
\plot 10.494 19.209 10.395 19.245 /
\plot 10.395 19.245 10.298 19.281 /
\plot 10.298 19.281 10.202 19.321 /
\plot 10.202 19.321 10.111 19.363 /
\plot 10.111 19.363 10.022 19.406 /
\plot 10.022 19.406 9.936 19.450 /
\plot 9.936 19.450 9.851 19.494 /
\plot 9.851 19.494 9.768 19.539 /
\plot 9.768 19.539 9.688 19.586 /
\plot 9.688 19.586 9.612 19.632 /
\plot 9.612 19.632 9.538 19.677 /
\plot 9.538 19.677 9.468 19.721 /
\plot 9.468 19.721 9.402 19.763 /
\plot 9.402 19.763 9.341 19.804 /
\plot 9.341 19.804 9.284 19.840 /
\plot 9.284 19.840 9.233 19.873 /
\plot 9.233 19.873 9.188 19.905 /
\plot 9.188 19.905 9.152 19.931 /
\plot 9.152 19.931 9.121 19.952 /
\plot 9.121 19.952 9.095 19.969 /
\plot 9.095 19.969 9.076 19.983 /
\plot 9.076 19.983 9.064 19.992 /
\plot 9.064 19.992 9.055 19.998 /
\plot 9.055 19.998 9.051 20.000 /
\plot 9.051 20.000 9.049 20.003 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.144 20.003 7.146 20.000 /
\plot 7.146 20.000 7.150 19.996 /
\plot 7.150 19.996 7.156 19.988 /
\plot 7.156 19.988 7.169 19.975 /
\plot 7.169 19.975 7.186 19.956 /
\plot 7.186 19.956 7.209 19.933 /
\plot 7.209 19.933 7.237 19.903 /
\plot 7.237 19.903 7.271 19.867 /
\plot 7.271 19.867 7.311 19.829 /
\plot 7.311 19.829 7.353 19.784 /
\plot 7.353 19.784 7.404 19.738 /
\plot 7.404 19.738 7.457 19.689 /
\plot 7.457 19.689 7.514 19.638 /
\plot 7.514 19.638 7.576 19.586 /
\plot 7.576 19.586 7.639 19.535 /
\plot 7.639 19.535 7.709 19.482 /
\plot 7.709 19.482 7.779 19.431 /
\plot 7.779 19.431 7.855 19.382 /
\plot 7.855 19.382 7.933 19.334 /
\plot 7.933 19.334 8.016 19.289 /
\plot 8.016 19.289 8.105 19.247 /
\plot 8.105 19.247 8.198 19.207 /
\plot 8.198 19.207 8.297 19.171 /
\plot 8.297 19.171 8.405 19.137 /
\plot 8.405 19.137 8.520 19.107 /
\plot 8.520 19.107 8.642 19.084 /
\plot 8.642 19.084 8.771 19.065 /
\plot 8.771 19.065 8.907 19.054 /
\plot 8.907 19.054 9.049 19.050 /
\plot 9.049 19.050 9.176 19.054 /
\plot 9.176 19.054 9.301 19.063 /
\plot 9.301 19.063 9.423 19.078 /
\plot 9.423 19.078 9.544 19.097 /
\plot 9.544 19.097 9.660 19.120 /
\plot 9.660 19.120 9.773 19.145 /
\plot 9.773 19.145 9.881 19.177 /
\plot 9.881 19.177 9.984 19.209 /
\plot 9.984 19.209 10.084 19.245 /
\plot 10.084 19.245 10.181 19.281 /
\plot 10.181 19.281 10.276 19.321 /
\plot 10.276 19.321 10.367 19.363 /
\plot 10.367 19.363 10.456 19.406 /
\plot 10.456 19.406 10.543 19.450 /
\plot 10.543 19.450 10.628 19.494 /
\plot 10.628 19.494 10.710 19.539 /
\plot 10.710 19.539 10.791 19.586 /
\plot 10.791 19.586 10.867 19.632 /
\plot 10.867 19.632 10.941 19.677 /
\plot 10.941 19.677 11.011 19.721 /
\plot 11.011 19.721 11.077 19.763 /
\plot 11.077 19.763 11.138 19.804 /
\plot 11.138 19.804 11.195 19.840 /
\plot 11.195 19.840 11.246 19.873 /
\plot 11.246 19.873 11.290 19.905 /
\plot 11.290 19.905 11.326 19.931 /
\plot 11.326 19.931 11.358 19.952 /
\plot 11.358 19.952 11.383 19.969 /
\plot 11.383 19.969 11.402 19.983 /
\plot 11.402 19.983 11.415 19.992 /
\plot 11.415 19.992 11.424 19.998 /
\plot 11.424 19.998 11.428 20.000 /
\plot 11.428 20.000 11.430 20.003 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 12.383 21.431 to 12.380 21.431
\plot 12.380 21.431 12.376 21.433 /
\plot 12.376 21.433 12.366 21.438 /
\plot 12.366 21.438 12.353 21.444 /
\plot 12.353 21.444 12.332 21.452 /
\plot 12.332 21.452 12.304 21.465 /
\plot 12.304 21.465 12.268 21.480 /
\plot 12.268 21.480 12.224 21.499 /
\plot 12.224 21.499 12.173 21.520 /
\plot 12.173 21.520 12.112 21.546 /
\plot 12.112 21.546 12.044 21.575 /
\plot 12.044 21.575 11.966 21.607 /
\plot 11.966 21.607 11.881 21.641 /
\plot 11.881 21.641 11.790 21.679 /
\plot 11.790 21.679 11.690 21.719 /
\plot 11.690 21.719 11.587 21.759 /
\plot 11.587 21.759 11.477 21.804 /
\plot 11.477 21.804 11.362 21.846 /
\plot 11.362 21.846 11.244 21.893 /
\plot 11.244 21.893 11.123 21.937 /
\plot 11.123 21.937 10.998 21.982 /
\plot 10.998 21.982 10.871 22.026 /
\plot 10.871 22.026 10.744 22.070 /
\plot 10.744 22.070 10.615 22.113 /
\plot 10.615 22.113 10.484 22.155 /
\plot 10.484 22.155 10.353 22.195 /
\plot 10.353 22.195 10.221 22.233 /
\plot 10.221 22.233 10.088 22.269 /
\plot 10.088 22.269 9.957 22.303 /
\plot 9.957 22.303 9.823 22.335 /
\plot 9.823 22.335 9.690 22.365 /
\plot 9.690 22.365 9.557 22.390 /
\plot 9.557 22.390 9.421 22.411 /
\plot 9.421 22.411 9.286 22.430 /
\plot 9.286 22.430 9.152 22.445 /
\plot 9.152 22.445 9.015 22.458 /
\plot 9.015 22.458 8.879 22.464 /
\putrule from 8.879 22.464 to 8.744 22.464
\plot 8.744 22.464 8.611 22.460 /
\plot 8.611 22.460 8.477 22.451 /
\plot 8.477 22.451 8.346 22.435 /
\plot 8.346 22.435 8.219 22.413 /
\plot 8.219 22.413 8.096 22.384 /
\plot 8.096 22.384 7.963 22.341 /
\plot 7.963 22.341 7.840 22.293 /
\plot 7.840 22.293 7.728 22.236 /
\plot 7.728 22.236 7.628 22.172 /
\plot 7.628 22.172 7.540 22.106 /
\plot 7.540 22.106 7.459 22.035 /
\plot 7.459 22.035 7.389 21.960 /
\plot 7.389 21.960 7.328 21.882 /
\plot 7.328 21.882 7.277 21.802 /
\plot 7.277 21.802 7.231 21.719 /
\plot 7.231 21.719 7.192 21.634 /
\plot 7.192 21.634 7.161 21.550 /
\plot 7.161 21.550 7.135 21.461 /
\plot 7.135 21.461 7.114 21.370 /
\plot 7.114 21.370 7.099 21.279 /
\plot 7.099 21.279 7.087 21.188 /
\plot 7.087 21.188 7.078 21.095 /
\plot 7.078 21.095 7.072 21.004 /
\plot 7.072 21.004 7.070 20.911 /
\putrule from 7.070 20.911 to 7.070 20.820
\plot 7.070 20.820 7.072 20.729 /
\plot 7.072 20.729 7.074 20.642 /
\plot 7.074 20.642 7.080 20.557 /
\plot 7.080 20.557 7.087 20.477 /
\plot 7.087 20.477 7.093 20.400 /
\plot 7.093 20.400 7.099 20.331 /
\plot 7.099 20.331 7.108 20.267 /
\plot 7.108 20.267 7.114 20.210 /
\plot 7.114 20.210 7.120 20.159 /
\plot 7.120 20.159 7.127 20.117 /
\plot 7.127 20.117 7.131 20.083 /
\plot 7.131 20.083 7.135 20.055 /
\plot 7.135 20.055 7.140 20.034 /
\plot 7.140 20.034 7.142 20.019 /
\putrule from 7.142 20.019 to 7.142 20.009
\plot 7.142 20.009 7.144 20.005 /
\putrule from 7.144 20.005 to 7.144 20.003
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 8.096 21.431 to 8.098 21.431
\plot 8.098 21.431 8.103 21.433 /
\plot 8.103 21.433 8.113 21.438 /
\plot 8.113 21.438 8.126 21.444 /
\plot 8.126 21.444 8.147 21.452 /
\plot 8.147 21.452 8.175 21.465 /
\plot 8.175 21.465 8.211 21.480 /
\plot 8.211 21.480 8.255 21.499 /
\plot 8.255 21.499 8.306 21.520 /
\plot 8.306 21.520 8.367 21.546 /
\plot 8.367 21.546 8.435 21.575 /
\plot 8.435 21.575 8.513 21.607 /
\plot 8.513 21.607 8.598 21.641 /
\plot 8.598 21.641 8.689 21.679 /
\plot 8.689 21.679 8.788 21.719 /
\plot 8.788 21.719 8.892 21.759 /
\plot 8.892 21.759 9.002 21.804 /
\plot 9.002 21.804 9.116 21.846 /
\plot 9.116 21.846 9.235 21.893 /
\plot 9.235 21.893 9.356 21.937 /
\plot 9.356 21.937 9.481 21.982 /
\plot 9.481 21.982 9.608 22.026 /
\plot 9.608 22.026 9.735 22.070 /
\plot 9.735 22.070 9.864 22.113 /
\plot 9.864 22.113 9.995 22.155 /
\plot 9.995 22.155 10.126 22.195 /
\plot 10.126 22.195 10.257 22.233 /
\plot 10.257 22.233 10.391 22.269 /
\plot 10.391 22.269 10.522 22.303 /
\plot 10.522 22.303 10.655 22.335 /
\plot 10.655 22.335 10.789 22.365 /
\plot 10.789 22.365 10.922 22.390 /
\plot 10.922 22.390 11.057 22.411 /
\plot 11.057 22.411 11.193 22.430 /
\plot 11.193 22.430 11.326 22.445 /
\plot 11.326 22.445 11.464 22.458 /
\plot 11.464 22.458 11.599 22.464 /
\putrule from 11.599 22.464 to 11.735 22.464
\plot 11.735 22.464 11.868 22.460 /
\plot 11.868 22.460 12.002 22.451 /
\plot 12.002 22.451 12.133 22.435 /
\plot 12.133 22.435 12.260 22.413 /
\plot 12.260 22.413 12.383 22.384 /
\plot 12.383 22.384 12.516 22.341 /
\plot 12.516 22.341 12.639 22.293 /
\plot 12.639 22.293 12.751 22.236 /
\plot 12.751 22.236 12.850 22.172 /
\plot 12.850 22.172 12.939 22.106 /
\plot 12.939 22.106 13.020 22.035 /
\plot 13.020 22.035 13.089 21.960 /
\plot 13.089 21.960 13.151 21.882 /
\plot 13.151 21.882 13.202 21.802 /
\plot 13.202 21.802 13.248 21.719 /
\plot 13.248 21.719 13.286 21.634 /
\plot 13.286 21.634 13.318 21.550 /
\plot 13.318 21.550 13.343 21.461 /
\plot 13.343 21.461 13.365 21.370 /
\plot 13.365 21.370 13.379 21.279 /
\plot 13.379 21.279 13.392 21.188 /
\plot 13.392 21.188 13.401 21.095 /
\plot 13.401 21.095 13.407 21.004 /
\plot 13.407 21.004 13.409 20.911 /
\putrule from 13.409 20.911 to 13.409 20.820
\plot 13.409 20.820 13.407 20.729 /
\plot 13.407 20.729 13.405 20.642 /
\plot 13.405 20.642 13.399 20.557 /
\plot 13.399 20.557 13.392 20.477 /
\plot 13.392 20.477 13.386 20.400 /
\plot 13.386 20.400 13.379 20.331 /
\plot 13.379 20.331 13.371 20.267 /
\plot 13.371 20.267 13.365 20.210 /
\plot 13.365 20.210 13.358 20.159 /
\plot 13.358 20.159 13.352 20.117 /
\plot 13.352 20.117 13.348 20.083 /
\plot 13.348 20.083 13.343 20.055 /
\plot 13.343 20.055 13.339 20.034 /
\plot 13.339 20.034 13.337 20.019 /
\putrule from 13.337 20.019 to 13.337 20.009
\plot 13.337 20.009 13.335 20.005 /
\putrule from 13.335 20.005 to 13.335 20.003
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 12.383 21.431 11.430 20.003 /
\plot 11.430 20.003 8.096 21.431 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 8.096 21.431 to 12.383 21.431
\plot 12.383 21.431 13.335 20.003 /
\putrule from 13.335 20.003 to 7.144 20.003
\plot 7.144 20.003 8.096 21.431 /
\plot 8.096 21.431 9.049 20.003 /
\plot 9.049 20.003 12.383 21.431 /
}%
\linethickness=0pt
\putrectangle corners at 7.008 22.511 and 13.470 17.913
\endpicture}
\end{center}
\caption{\label{cap:crossingK6}Minimální počet křížení v grafu $K_{6}$}
\end{figure}
\end{example*}
\begin{thm}
\label{thm:odhad-poctu-krizeni}Nechť $G=(V,E)$ je graf, $m=\# E,n=\# V$
a nechť $m\geq4n$. Potom platí\[
\crs(G)\geq\frac{1}{64}\frac{m^{3}}{n^{2}}.\]
\end{thm}
\begin{rem*}
Pro velký počet hran, tj. $m\approx n^{2}$ (nejvýše je $m=\binom{n}{2}=\frac{n^{2}-n}{2}$)
tato věta dává mnohem silnější odhad $\crs(G)$:\[
\crs(G)\geq konst\cdot\frac{n^{6}}{n^{2}}=konst\cdot n^{4}\approx konst\cdot m^{2},\]
což je odhad kvadratický v počtu hran $m$.
\end{rem*}
\begin{proof}
Provedeme tzv. \emph{pravděpodobnostní} důkaz tohoto tvrzení. Tento
typ důkazu se nám bude ještě mnohokrát hodit v druhé kapitole.
Namalujeme $G$ tak, aby počet křížení byl $\crs(G)$. Vezmeme zatím
blíže neurčené $p\in[0,1]$ a pro každý vrchol se nezávisle rozhodujeme,
zda jej necháme v obrázku: Vrchol ponecháme s pravděpodobností $p$
a odstraníme jej s pravděpodobností $1-p$. Každá hrana zůstane v
obrázku, pokud v něm zůstanou oba její koncové vrcholy. Stejně tak
křížení zůstane v obrázku, pokud v něm zůstanou obě hrany, které jej
tvoří. Výsledkem je obrázek nového grafu $G_{p}\subset G$. Označme
si následující náhodné veličiny:
\begin{lyxlist}{00.00.0000}
\item [$n_{p}$]počet ponechaných vrcholů, tj. počet vrcholů v $G_{p}$,
\item [$m_{p}$]počet hran v $G_{p}$,
\item [$X$]počet křížení v obrázku $G_{p}$.
\end{lyxlist}
$X$ nemusí být rovno $\crs(G_{p})$, protože obrázek $G_{p}$ vznikl
jen odebráním některých částí obrázku původního grafu $G$. Proto
podle předchozí věty platí\[
X\geq\crs(G_{p})\geq m_{p}-3n_{p}+6.\]
Z toho plyne, že i pro střední hodnoty platí (jestliže na pravé straně
zanedbáme konstantu $6$)\begin{equation}
\E X\geq\E m_{p}-3\E n_{p}.\label{eq:nerovnost-pro-crG}\end{equation}
Střední hodnoty jednotlivých veličin vyjádříme následovně. Pro každé
$v\in V$ označíme elementární náhodnou veličinu\[
x_{v}=\begin{cases}
1 & v\in V(G_{p})\\
0 & v\notin V(G_{p})\end{cases},\]
tj. $x_{v}$ je indikátor jevu $v\in V(G_{p})$. Potom $\forall v\in V$
platí \[
\E x_{v}=1\cdot\Pr\left(v\in V(G_{p})\right)+0\cdot\Pr\left(v\notin V(G_{p})\right)=1\cdot p+0\cdot(1-p)=p\]
a protože $n_{p}=\sum_{v\in V}x_{v}$, tak\[
\E n_{p}=\sum_{v\in V}\E x_{v}=np.\]
Analogicky zavedeme indikátor $y_{e}$ jevu $e\in E(G_{p})$ pro každou
$e\in E$. Potom $\forall e\in E$ platí $\E y_{e}=p^{2}$ a tak\[
\E m_{p}=mp^{2}.\]
Konečně totéž provedeme i pro křížení, přičemž podle konstrukce obrázku
$G_{p}$ v něm zůstává každé konkrétní křížení s pravděpodobností
$p^{4}$, takže $\E X=\crs(G)\cdot p^{4}$. Po dosazení do (\ref{eq:nerovnost-pro-crG})
máme\begin{eqnarray*}
\crs(G)\cdot p^{4} & \geq & mp^{2}-3np\\
\crs(G) & \geq & \frac{m}{p^{2}}-\frac{3n}{p^{3}},\end{eqnarray*}
což musí platit pro každé $p\in[0,1]$. Pokud nyní zvolíme $p=\frac{4n}{m}\leq1$,
dostaneme\[
\crs(G)\geq\frac{m}{p^{2}}-\frac{3n}{p^{3}}=\frac{m^{3}}{16n^{2}}-3\frac{m^{3}}{4^{3}n^{2}}=\frac{m^{3}}{n^{2}}\left(\frac{4}{4^{3}}-\frac{3}{4^{3}}\right)=\frac{1}{64}\frac{m^{3}}{n^{2}}.\]
\end{proof}
