Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 22/kontrolle
- Hamiltonkreise
Da in einem Kreis ein Punkt höchstens einmal vorkommt, kommt in einem Hamiltonkreis jeder Punkt genau einmal vor. Ein 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.
Ein Graph heißt hamiltonsch, wenn es in ihm einen Hamiltonkreis gibt.
Der folgende Satz heißt Satz von Ore.
Es sei ein Graph mit mindestens drei Elementen, der die Bedingung
für je zwei nicht adjazente Knoten erfüllt.
Dann ist hamiltonsch.
Wir argumentieren bei einer fixierten Knotenmenge absteigend über die Kantenmenge. Für einen 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 ein Graph, für den es einen Hamiltonkreis gibt, und es sei die Kante, die wir herausnehmen. Es sei der verkleinerte Graph. Wenn es in einen Hamiltonkreis gibt, in dem nicht vorkommt, so ist dies direkt ein Hamiltonkreis für . Es sei also (alle beziehen sich auf )
mit ein Hamiltonkreis von . Wir betrachten die Mengen
und
Dabei ist (in der Definition von ) als zu interpretieren und die Nachbarschaften beziehen sich auf . Aufgrund der Voraussetzung über die Grade ( und sind nicht adjazent und ist so groß wie ) ist
Das Element gehört nicht zur Vereinigung , da ein Knotenpunkt nicht mit sich selbst benachbart ist. Daher gibt es nach der Siebformel ein Element
Es gibt also die Verbindungskanten und und somit den Hamiltonkreis
der ohne die Kante auskommt und daher ein Hamiltonkreis in ist.