Aktuální verze z 15. 1. 2012, 13:34

Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\section{Hamiltonovské kružnice a grafy}
 
\begin{defn}
Řekneme, že kružnice v grafu $G=(V,E)$ je \textbf{hamiltonovská}
(angl. \emph{Hamilton cycle}), jestliže má délku $n=\# V$. Řekneme,
že cesta v $G$ je hamiltonovská (angl. \emph{Hamilton path}), jestliže
má délku $n-1$. Graf $G$ se nazývá hamiltonovský (angl. \emph{hamiltonian}),
jestliže obsahuje hamiltonovskou kružnici.
\end{defn}
\begin{rem*}
Půjdeme-li po hamiltonovské cestě, projdeme každým vrcholem grafu
právě jednou. Půjdeme-li po hamiltonovské kružnici, vrátíme se navíc
do vrcholu, z nějž jsme vyšli. Každý hamiltonovský graf obsahuje hamiltonovskou
cestu.
\end{rem*}
 
 
\begin{rem*}
Problém existence hamiltonovské kružnice v obecném grafu je NP-úplný.
To zhruba znamená, že jej není možné řešit algoritmem s lepší než
exponenciální složitostí%
\footnote{Uvedeme bez detailů jednu z mnoha definic NP-úplnosti (viz. \cite{tslo}):
Problém je otázka, na niž očekáváme odpověď ANO/NE. Problém je třídy
NP, existuje-li nedeterministický algoritmus s nejvýše polynomiální
složitostí, který jej rozhoduje. Problém $P_{0}$ je NP-těžký, lze-li
na něj polynomiálně transformovat libovolný problém $P$ třídy NP,
tj. jednoznačná transformace zadání $P$ na zadání $P_{0}$ má nejvýše
polynomiální složitost. Problém je NP-úplný, jestliže je NP-těžký
a je třídy NP.
 
Jsou známy desítky NP-úplných problémů. Přitom, vzhledem k definici
NP-úplnosti, najde-li se deterministický algoritmus rozhodující jeden
z těchto problémů s polynomiální složitostí, bude možné rozhodnout
každý NP-úplný problém s polynomiální složitostí. Dosud se však takový
algoritmus nenašel a proto se věří, že NP-úplné problémy nelze řešit
v polynomiálním čase. Není to však dokázáno.
 
Konečně, každý nedeterministický algoritmus s polynomiální složitostí
lze snadno převést na deterministický algoritmus s exponenciální složitostí,
což odůvodňuje formulaci naší poznámky.%
}.
\end{rem*}
\begin{thm}
\textbf{\emph{(Chvátal, 1972)}}
 
Nechť $G=(V,E)$ je graf a $x,y$ dva jeho vrcholy takové, že $d_{G}(x)+d_{G}(y)\geq n$
a přitom $\{ x,y\}\notin E$. Potom $G$ je hamiltonovský právě tehdy,
když $G'=(V,E\cup\{ x,y\})$ je hamiltonovský.
\end{thm}
\begin{proof}
$\boxed{{\Leftarrow:}}$ Zřejmé.
 
$\boxed{{\Rightarrow:}}$
 
Důkaz provedeme sporem. Nechť $G'$ je hamiltonovský a $G$ není.
Označme si hamiltonovskou kružnici jako\[
x=v_{1},v_{2},...,v_{n-1},v_{n}=y,\]
tj. jako na obrázku:
 
\hfill{}
\begin{center}
%Title: chvatal.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:42: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.182}}} at 12.319 20.631
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at 13.064 20.631
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at 10.454 20.631
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at  9.709 20.631
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at  7.844 20.631
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.182}}} at  7.099 20.631
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\plot  7.099 20.631  7.097 20.633 /
\plot  7.097 20.633  7.095 20.637 /
\plot  7.095 20.637  7.093 20.642 /
\plot  7.093 20.642  7.089 20.650 /
\plot  7.089 20.650  7.082 20.661 /
\plot  7.082 20.661  7.076 20.673 /
\plot  7.076 20.673  7.070 20.688 /
\plot  7.070 20.688  7.061 20.705 /
\plot  7.061 20.705  7.051 20.726 /
\plot  7.051 20.726  7.042 20.750 /
\plot  7.042 20.750  7.034 20.773 /
\plot  7.034 20.773  7.025 20.800 /
\plot  7.025 20.800  7.017 20.828 /
\plot  7.017 20.828  7.010 20.858 /
\plot  7.010 20.858  7.006 20.889 /
\plot  7.006 20.889  7.002 20.919 /
\putrule from  7.002 20.919 to  7.002 20.951
\plot  7.002 20.951  7.006 20.985 /
\plot  7.006 20.985  7.013 21.016 /
\plot  7.013 21.016  7.023 21.048 /
\plot  7.023 21.048  7.038 21.082 /
\plot  7.038 21.082  7.057 21.114 /
\plot  7.057 21.114  7.082 21.145 /
\plot  7.082 21.145  7.114 21.177 /
\plot  7.114 21.177  7.154 21.209 /
\plot  7.154 21.209  7.199 21.241 /
\plot  7.199 21.241  7.254 21.273 /
\plot  7.254 21.273  7.319 21.302 /
\plot  7.319 21.302  7.394 21.334 /
\plot  7.394 21.334  7.478 21.364 /
\plot  7.478 21.364  7.576 21.393 /
\plot  7.576 21.393  7.686 21.421 /
\plot  7.686 21.421  7.806 21.446 /
\plot  7.806 21.446  7.938 21.471 /
\plot  7.938 21.471  8.052 21.491 /
\plot  8.052 21.491  8.172 21.505 /
\plot  8.172 21.505  8.293 21.520 /
\plot  8.293 21.520  8.416 21.535 /
\plot  8.416 21.535  8.537 21.546 /
\plot  8.537 21.546  8.655 21.556 /
\plot  8.655 21.556  8.769 21.565 /
\plot  8.769 21.565  8.879 21.573 /
\plot  8.879 21.573  8.985 21.579 /
\plot  8.985 21.579  9.087 21.586 /
\plot  9.087 21.586  9.182 21.592 /
\plot  9.182 21.592  9.271 21.596 /
\plot  9.271 21.596  9.358 21.598 /
\plot  9.358 21.598  9.438 21.603 /
\plot  9.438 21.603  9.514 21.605 /
\plot  9.514 21.605  9.588 21.607 /
\plot  9.588 21.607  9.656 21.609 /
\putrule from  9.656 21.609 to  9.724 21.609
\plot  9.724 21.609  9.787 21.611 /
\putrule from  9.787 21.611 to  9.851 21.611
\putrule from  9.851 21.611 to  9.912 21.611
\putrule from  9.912 21.611 to  9.974 21.611
\putrule from  9.974 21.611 to 10.033 21.611
\putrule from 10.033 21.611 to 10.094 21.611
\putrule from 10.094 21.611 to 10.158 21.611
\plot 10.158 21.611 10.224 21.609 /
\putrule from 10.224 21.609 to 10.289 21.609
\plot 10.289 21.609 10.359 21.607 /
\plot 10.359 21.607 10.433 21.605 /
\plot 10.433 21.605 10.509 21.603 /
\plot 10.509 21.603 10.592 21.598 /
\plot 10.592 21.598 10.679 21.596 /
\plot 10.679 21.596 10.770 21.592 /
\plot 10.770 21.592 10.865 21.586 /
\plot 10.865 21.586 10.969 21.579 /
\plot 10.969 21.579 11.074 21.573 /
\plot 11.074 21.573 11.187 21.565 /
\plot 11.187 21.565 11.303 21.556 /
\plot 11.303 21.556 11.424 21.546 /
\plot 11.424 21.546 11.546 21.535 /
\plot 11.546 21.535 11.671 21.520 /
\plot 11.671 21.520 11.796 21.505 /
\plot 11.796 21.505 11.921 21.491 /
\plot 11.921 21.491 12.040 21.471 /
\plot 12.040 21.471 12.177 21.446 /
\plot 12.177 21.446 12.304 21.421 /
\plot 12.304 21.421 12.418 21.393 /
\plot 12.418 21.393 12.522 21.364 /
\plot 12.522 21.364 12.613 21.334 /
\plot 12.613 21.334 12.696 21.302 /
\plot 12.696 21.302 12.766 21.273 /
\plot 12.766 21.273 12.829 21.241 /
\plot 12.829 21.241 12.882 21.209 /
\plot 12.882 21.209 12.929 21.177 /
\plot 12.929 21.177 12.967 21.145 /
\plot 12.967 21.145 12.998 21.114 /
\plot 12.998 21.114 13.026 21.082 /
\plot 13.026 21.082 13.049 21.048 /
\plot 13.049 21.048 13.066 21.016 /
\plot 13.066 21.016 13.079 20.985 /
\plot 13.079 20.985 13.089 20.951 /
\plot 13.089 20.951 13.096 20.919 /
\plot 13.096 20.919 13.100 20.889 /
\plot 13.100 20.889 13.102 20.858 /
\putrule from 13.102 20.858 to 13.102 20.828
\putrule from 13.102 20.828 to 13.102 20.800
\plot 13.102 20.800 13.098 20.773 /
\plot 13.098 20.773 13.096 20.750 /
\plot 13.096 20.750 13.092 20.726 /
\plot 13.092 20.726 13.085 20.705 /
\plot 13.085 20.705 13.081 20.688 /
\plot 13.081 20.688 13.077 20.673 /
\plot 13.077 20.673 13.075 20.661 /
\plot 13.075 20.661 13.070 20.650 /
\plot 13.070 20.650 13.068 20.642 /
\plot 13.068 20.642 13.066 20.637 /
\plot 13.066 20.637 13.064 20.633 /
\putrule from 13.064 20.633 to 13.064 20.631
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.2032cm>
{\color[rgb]{0,0,0}\plot 10.454 20.631 12.319 20.631 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot  7.844 20.631  9.709 20.631 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setsolid
{\color[rgb]{0,0,0}\putrule from 12.319 20.631 to 13.064 20.631
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  9.709 20.631 to 10.454 20.631
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  7.099 20.631 to  7.844 20.631
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}$\{x,y\}$}%
} [lB] at 13.064 21.378
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y$}%
} [lB] at 13.062 20.074
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{n-1}$}%
} [lB] at 12.040 21.006
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k+1}$}%
} [lB] at 10.268 21.006
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  9.614 20.074
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at  7.749 20.074
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x$}%
} [lB] at  6.911 20.074
\linethickness=0pt
\putrectangle corners at  6.879 22.003 and 13.172 19.876
\endpicture}
\end{center}
 
 
\hfill{}
 
\noindent Označme $E'=E\cup\{ x,y\}$ a dále definujme množiny\[
T=\left\{ \left.i\right|\{ x,v_{i+1}\}\in E'\right\} ,\]
\[
S=\left\{ \left.j\right|\{ y,v_{j}\}\in E'\right\} .\]
Potom paltí, že $S\cap T=\emptyset$. Kdyby totiž existovalo $k\in S\cap T$,
nastala by tato situace:
 
\hfill{}
\begin{center}
%Title: chvatal2.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:40: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.186}}} at 12.266 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.186}}} at 13.022 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.186}}} at 10.374 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.186}}} at  9.616 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.186}}} at  7.726 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.186}}} at  6.968 20.955
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\putrule from  9.616 20.955 to 10.374 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.374 20.955 to 12.266 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  7.726 20.955 to  9.616 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  9.616 20.955  9.618 20.953 /
\plot  9.618 20.953  9.622 20.949 /
\plot  9.622 20.949  9.633 20.940 /
\plot  9.633 20.940  9.648 20.927 /
\plot  9.648 20.927  9.669 20.911 /
\plot  9.669 20.911  9.694 20.887 /
\plot  9.694 20.887  9.728 20.860 /
\plot  9.728 20.860  9.768 20.828 /
\plot  9.768 20.828  9.813 20.792 /
\plot  9.813 20.792  9.864 20.752 /
\plot  9.864 20.752  9.919 20.712 /
\plot  9.919 20.712  9.978 20.667 /
\plot  9.978 20.667 10.041 20.623 /
\plot 10.041 20.623 10.107 20.578 /
\plot 10.107 20.578 10.177 20.536 /
\plot 10.177 20.536 10.249 20.491 /
\plot 10.249 20.491 10.323 20.451 /
\plot 10.323 20.451 10.401 20.411 /
\plot 10.401 20.411 10.484 20.373 /
\plot 10.484 20.373 10.569 20.337 /
\plot 10.569 20.337 10.660 20.305 /
\plot 10.660 20.305 10.757 20.276 /
\plot 10.757 20.276 10.859 20.250 /
\plot 10.859 20.250 10.964 20.229 /
\plot 10.964 20.229 11.079 20.212 /
\plot 11.079 20.212 11.197 20.201 /
\plot 11.197 20.201 11.318 20.197 /
\plot 11.318 20.197 11.438 20.201 /
\plot 11.438 20.201 11.557 20.212 /
\plot 11.557 20.212 11.671 20.229 /
\plot 11.671 20.229 11.777 20.250 /
\plot 11.777 20.250 11.881 20.276 /
\plot 11.881 20.276 11.976 20.305 /
\plot 11.976 20.305 12.067 20.337 /
\plot 12.067 20.337 12.152 20.373 /
\plot 12.152 20.373 12.234 20.411 /
\plot 12.234 20.411 12.313 20.451 /
\plot 12.313 20.451 12.389 20.491 /
\plot 12.389 20.491 12.461 20.536 /
\plot 12.461 20.536 12.529 20.578 /
\plot 12.529 20.578 12.596 20.623 /
\plot 12.596 20.623 12.658 20.667 /
\plot 12.658 20.667 12.719 20.712 /
\plot 12.719 20.712 12.774 20.752 /
\plot 12.774 20.752 12.825 20.792 /
\plot 12.825 20.792 12.869 20.828 /
\plot 12.869 20.828 12.910 20.860 /
\plot 12.910 20.860 12.941 20.887 /
\plot 12.941 20.887 12.969 20.911 /
\plot 12.969 20.911 12.990 20.927 /
\plot 12.990 20.927 13.005 20.940 /
\plot 13.005 20.940 13.013 20.949 /
\plot 13.013 20.949 13.020 20.953 /
\plot 13.020 20.953 13.022 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  6.968 20.955  6.970 20.957 /
\plot  6.970 20.957  6.974 20.961 /
\plot  6.974 20.961  6.985 20.970 /
\plot  6.985 20.970  7.000 20.983 /
\plot  7.000 20.983  7.021 20.999 /
\plot  7.021 20.999  7.046 21.023 /
\plot  7.046 21.023  7.080 21.050 /
\plot  7.080 21.050  7.120 21.082 /
\plot  7.120 21.082  7.165 21.118 /
\plot  7.165 21.118  7.216 21.158 /
\plot  7.216 21.158  7.271 21.198 /
\plot  7.271 21.198  7.330 21.243 /
\plot  7.330 21.243  7.394 21.287 /
\plot  7.394 21.287  7.459 21.332 /
\plot  7.459 21.332  7.529 21.374 /
\plot  7.529 21.374  7.601 21.419 /
\plot  7.601 21.419  7.675 21.459 /
\plot  7.675 21.459  7.753 21.499 /
\plot  7.753 21.499  7.836 21.537 /
\plot  7.836 21.537  7.921 21.573 /
\plot  7.921 21.573  8.012 21.605 /
\plot  8.012 21.605  8.109 21.634 /
\plot  8.109 21.634  8.211 21.660 /
\plot  8.211 21.660  8.316 21.681 /
\plot  8.316 21.681  8.431 21.698 /
\plot  8.431 21.698  8.549 21.709 /
\plot  8.549 21.709  8.670 21.713 /
\plot  8.670 21.713  8.791 21.709 /
\plot  8.791 21.709  8.909 21.698 /
\plot  8.909 21.698  9.023 21.681 /
\plot  9.023 21.681  9.129 21.660 /
\plot  9.129 21.660  9.233 21.634 /
\plot  9.233 21.634  9.328 21.605 /
\plot  9.328 21.605  9.419 21.573 /
\plot  9.419 21.573  9.504 21.537 /
\plot  9.504 21.537  9.586 21.499 /
\plot  9.586 21.499  9.665 21.459 /
\plot  9.665 21.459  9.741 21.419 /
\plot  9.741 21.419  9.813 21.374 /
\plot  9.813 21.374  9.881 21.332 /
\plot  9.881 21.332  9.948 21.287 /
\plot  9.948 21.287 10.010 21.243 /
\plot 10.010 21.243 10.071 21.198 /
\plot 10.071 21.198 10.126 21.158 /
\plot 10.126 21.158 10.177 21.118 /
\plot 10.177 21.118 10.221 21.082 /
\plot 10.221 21.082 10.262 21.050 /
\plot 10.262 21.050 10.293 21.023 /
\plot 10.293 21.023 10.321 20.999 /
\plot 10.321 20.999 10.342 20.983 /
\plot 10.342 20.983 10.357 20.970 /
\plot 10.357 20.970 10.365 20.961 /
\plot 10.365 20.961 10.372 20.957 /
\plot 10.372 20.957 10.374 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 12.266 20.955 to 13.022 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  6.968 20.955 to  7.726 20.955
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y$}%
} [lB] at 13.020 20.388
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{n-1}$}%
} [lB] at 11.985 21.332
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k+1}$}%
} [lB] at 10.183 21.332
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  9.521 20.388
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at  7.628 20.388
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x$}%
} [lB] at  6.778 20.388
\linethickness=0pt
\putrectangle corners at  6.746 21.814 and 13.132 20.151
\endpicture}
\end{center}
\hfill{}
 
\noindent Jinými slovy, existovala by hamiltonovská kružnice i v původním
grafu $G$, bez přidání hrany $\{ x,y\}$. Díky tomu platí\[
\#(S\cup T)=\# S+\# T\]
 a navíc zřejmě \begin{eqnarray*}
\# S & = & d_{G}(y),\\
\# T & = & d_{G}(x).\end{eqnarray*}
Snadno si ověříme, že $0\notin T$ a hlavně $n\notin S\cup T$. Proto
\[
n>\#(S\cup T)=\# S+\# T=d_{G}(y)+d_{G}(x),\]
což je ovšem spor s předpokladem věty.
\end{proof}
Chvátalova věta nás opravňuje k následující definici :
 
\begin{defn}
Uzávěrem grafu $G=(V,E)$ rozumíme minimální nadgraf $C(G)=(V,\tilde{E})$
grafu $G$ takový, že pro každé $x,y\in V,x\neq y$ platí\[
\{ x,y\}\notin E\Rightarrow d_{C(G)}(x)+d_{C(G)}(y)<n\left(=\# V\right).\]
 
\end{defn}
\begin{rem}
Uzávěr grafu je definován jednoznačně.
\end{rem}
\begin{proof}
Korektnost (tedy jednoznačnost) definice dokážeme tak, že popíšeme
algoritmus konstrukce $C(G)$:
\begin{enumerate}
\item Označíme $G^{(0)}:=G$. Dále nechť $i:=0$.
\item \label{enu:next_step}Používejme označení $G^{(i)}=(V,E^{(i)})$.
Přiřadíme $E^{(i+1)}:=E^{(i)}$.
\item Procházíme všechny dvojice vrcholů $x,y$ grafu $G^{(i)}=\left(V,E^{(i)}\right)$,
které nejsou v hraně, a pokud platí $d_{G^{(i)}}(x)+d_{G^{(i)}}(y)\geq n$,
přidáme hranu $\{ x,y\}$ do $E^{(i+1)}$. Poté, co projdeme všechny
takové dvojice, vznikne nový graf $G^{(i+1)}$, v němž díky přidaým
hranám mohly vzniknout další dvojice, kde $d_{G^{(i+1)}}(x)+d_{G^{(i+1)}}(y)\geq n$.
\item $i:=i+1$. Jdeme na krok \ref{enu:next_step}, dokud nenastane $G^{(i+1)}=G^{(i)}$,
tj. nebylo již nutné nic přidávat. V krajním případě to nastane teprve
tehdy, když $G^{(i)}$ je už úplný graf.
\item $C(G):=G^{(i)}$.
\end{enumerate}
\end{proof}
\begin{cor}
Graf $G$ je hamiltonovský, právě když $C(G)$ je hamiltonovský.
\end{cor}
\begin{proof}
Postupné přidávání takových hran do $G$, pro které součet stupňů
jejich koncových vrcholů je alespoň $n$, podle Chvátalovy věty nemění
,,hamiltonovskost{}`` grafu $G$.
\end{proof}
Triviálním důsledkem předchozího tvrzení je i věta, kterou však nezávisle
na Chvátalovi formuloval Dirac (mladší) již v roce 1952:
 
\begin{thm}
\textbf{\emph{(Dirac, 1952)}}
 
Nechť $G=(V,E)$ je graf, $n=\# V$. Jestliže $\delta\geq\frac{n}{2}$,
potom $G$ je hamiltonovský.
\end{thm}
\begin{proof}
Podmínka $\delta\geq\frac{n}{2}$ zřejmě vynucuje, aby $C(G)$ byl
úplný graf, který je samozřejmě hamiltonovský. Proto i $G$ je hamiltonovský.
\end{proof}
Lze tedy shrnout, že postačující podmínkou pro to, aby graf byl hamiltonovský,
je ,,dostatek{}`` hran.
 
\begin{thm}
\label{thm:postac_podm_hamilt}Nechť $G=(V,E)$ je graf se skóre $d_{1}\leq d_{2}\leq...\leq d_{n}$.
Jestliže skóre $G$ má vlastnost\[
\left(\forall k<\frac{n}{2}\right)\left(d_{k}\leq k\Rightarrow d_{n-k}\geq n-k\right),\]
pak $G$ je hamiltonovský.
\end{thm}
\begin{proof}
Stejně jako v důkazu Diracovy věty se ukáže, že uvedená podmínka již
implikuje $C(G)=K_{n}$.
\end{proof}
\begin{thm}
\label{thm:hamilt_cesta_a_kruz}Nechť $G=(V,E)$, $x\notin V$. Označme
$G'=\left(V\cup\{ x\},E\cup\left\{ \left.\{ x,v\}\right|v\in V\right\} \right)$.
Potom $G$ obsahuje hamiltonovskou cestu, právě když $G'$ je hamiltonovský.
\end{thm}
\begin{proof}
je téměř zřejmý.
\end{proof}
\begin{thm}
Každý samokomplementární graf obsahuje hamiltonovskou cestu.
\end{thm}
\begin{proof}
Nechť $G=(V,E)$ je samokomplementární graf, s vrcholy uspořádanými
tak, že jejich stupně (skóre grafu $G$) splňují $d_{1}\leq d_{2}\leq...\leq d_{n}$.
Potom jeho doplněk má skóre\[
\underbrace{n-1-d_{1}}_{d_{n}}\geq\underbrace{n-1-d_{2}}_{d_{n-1}}\geq...\geq\underbrace{n-1-d_{n}}_{d_{1}}.\]
 $G$ je ovšem samokomplementární, tj. $G\sim\bar{G}$, neboli oba
grafy jsou až na označení vrcholů stejné. Vzhledem k vzestupnému uspořádání
vcholů grafu $G$ podle velikosti jejich stupňů pak musí platit vztah
naznačený svorkami:\[
\boxed{\left(\forall i\in\hat{n}\right)\left(d_{i}=n-1-d_{n+1-i}\right)}\]
Nyní z $G$ utvoříme graf $G'=\left(V\cup\{ x\},E\cup\left\{ \left.\{ x,v\}\right|v\in V\right\} \right)$
kde $x\notin V$ a o něm ukážeme, že je hamiltonovský. Uděláme to
tak, že ověříme podmínku věty \ref{thm:postac_podm_hamilt}. Potom
z věty \ref{thm:hamilt_cesta_a_kruz} již plyne dokazované tvrzení. 
 
Označme si $d'_{i}$ stupně vrcholů grafu $G'$. Potom zřejmě pro
všechna $i\in\hat{n}$ platí $d'_{i}=d_{i}+1$ a $d'_{n+1}=n$. Zvolme
nyní $k<\frac{n+1}{2}$ a ověřme zmíněnou podmínku. Postupně platí\[
d'_{k}\leq k\ \Leftrightarrow\  d_{k}+1\leq k\ \Leftrightarrow\ \left(n-1-d_{n+1-k}\right)+1\leq k\ \Leftrightarrow\]
\[
\Leftrightarrow\  n-k\leq d_{n+1-k}\ \Leftrightarrow\ (n+1)-k<\left(d_{n+1-k}+1\right)\ \Leftrightarrow\ (n+1)-k\leq d'_{(n+1)-k}.\]
 
\end{proof}