Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 22/latex
\setcounter{section}{22}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller2.jpg} }
\end{center}
\bildtext {Hier hat Vorli die Fragebögen von Dr. Eisenbeis zerfetzt. Zum Glück hatte Dr. Eisenbeis alles schon digital abgespeichert.} }
\bildlizenz { Waeller2.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
\zwischenueberschrift{Hamiltonkreise}
\inputdefinition
{}
{
Ein \definitionsverweis {Kreis}{}{} in einem \definitionsverweis {Graphen}{}{} $(V,E)$ heißt \definitionswort {Hamiltonkreis}{,} wenn in ihm jeder Knotenpunkt vorkommt.
}
Da in einem Kreis ein Punkt höchstens einmal vorkommt, kommt in einem Hamiltonkreis jeder Punkt genau einmal vor. Ein \stichwort {Hamiltonscher Pfad} {} ist ein Kantenzug, bei dem jeder Knoten genau einmal durchlaufen wird, die Enden müssen aber nicht wie bei einem Hamiltonkreis notwendigerweise durch eine Kante verbunden sein.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Hamiltonian Dodecahedron Graph.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Hamiltonian Dodecahedron Graph.svg } {} {Zorgit} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Ein \definitionsverweis {Graph}{}{} $(V,E)$ heißt \definitionswort {hamiltonsch}{,} wenn es in ihm einen \definitionsverweis {Hamiltonkreis}{}{} gibt.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Knight's tour anim 2.gif} }
\end{center}
\bildtext {Der Schachpferdgraph: Die Knoten sind die Schachfelder und zwei Felder sind durch eine Kante miteinander verbunden, wenn man durch einen Pferdsprung von einem Feld zum andern kommen kann. Die Animation zeigt einen hamiltonschen Pfad, der kein Hamiltonkreis ist. Gibt es einen Hamiltonkreis?} }
\bildlizenz { Knight's tour anim 2.gif } {} {Ilmari Karonen} {Commons} {gemeinfrei} {}
Der folgende Satz heißt Satz von Ore.
\inputfaktbeweis
{Graph/Gradbedingung/Ore/Hamiltonkreis/Fakt}
{Satz}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}}
\faktvoraussetzung {mit mindestens drei Elementen, der die Bedingung
\mavergleichskettedisp
{\vergleichskette
{d(u) + d(v)
}
{ \geq} { { \# \left( V \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für je zwei nicht adjazente Knoten $u,v$ erfüllt.}
\faktfolgerung {Dann ist $G$
\definitionsverweis {hamiltonsch}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir argumentieren bei einer fixierten Knotenmenge absteigend über die Kantenmenge. Für einen
\definitionsverweis {vollständigen Graphen}{}{}
ist die Aussage richtig. Wir müssen zeigen, dass die Aussage richtig bleibt, wenn man aus einem Graphen, für den die Aussage gilt, eine Kante herausnimmt. Es sei also $G$ ein Graph, für den es einen Hamiltonkreis gibt, und es sei
\mavergleichskette
{\vergleichskette
{L
}
{ = }{ \{x,y\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Kante, die wir herausnehmen. Es sei $H$ der verkleinerte Graph. Wenn es in $G$ einen Hamiltonkreis gibt, in dem $L$ nicht vorkommt, so ist dies direkt ein Hamiltonkreis für $H$. Es sei also
\zusatzklammer {alle $\sim$ beziehen sich auf $G$} {} {}
\mavergleichskettedisp
{\vergleichskette
{ x
}
{ =} { v_1
}
{ \sim} {v_2
}
{ \sim \ldots \sim} {v_{n-1}
}
{ \sim} { v_n
}
}
{
\vergleichskettefortsetzung
{ =} {y
}
{ } {}
{ } {}
{ } {}
}{}{}
mit
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ { \# \left( V \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Hamiltonkreis von $G$. Wir betrachten die Mengen
\mavergleichskettedisp
{\vergleichskette
{A
}
{ =} { { \left\{ v_i \mid x \text{ und } v_{i+1} \text{ sind benachbart} \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{B
}
{ =} { { \left\{ v_i \mid y \text{ und } v_i \text{ sind benachbart} \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dabei ist
\zusatzklammer {in der Definition von $A$} {} {}
$v_{n+1}$ als $v_1$ zu interpretieren und die Nachbarschaften beziehen sich auf $H$. Aufgrund der Voraussetzung über die Grade
\zusatzklammer {$x$ und $y$ sind nicht adjazent und $A$ ist so groß wie $N(x)$} {} {}
ist
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( A \right) } + { \# \left( B \right) }
}
{ \geq} {n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Das Element $y$ gehört nicht zur Vereinigung
\mathl{A \cup B}{,} da ein Knotenpunkt nicht mit sich selbst benachbart ist. Daher gibt es
nach der Siebformel
ein Element
\mavergleichskettedisp
{\vergleichskette
{v_k
}
{ \in} {A \cap B
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es gibt also die Verbindungskanten
\mathkor {} {\{ x,v_{k+1}\}} {und} {\{ y,v_k\}} {}
und somit den Hamiltonkreis
\mavergleichskettedisp
{\vergleichskette
{ x
}
{ \sim} {v_2
}
{ \sim \ldots \sim} { v_{k-1}
}
{ \sim} { v_k
}
{ \sim} {y
}
}
{
\vergleichskettefortsetzung
{ \sim} {v_{n-1}
}
{ \sim \ldots \sim} { v_{k+1}
}
{ } {}
{ } {}
}{}{,}
der ohne die Kante $L$ auskommt und daher ein Hamiltonkreis in $H$ ist.