 |
 |
 |
 |
 |
 |
Startseite » Forum » Dirac
Dirac
Universität / Fachhochschule
Sonstiges
Tags: Dirac
 
|
  |
|---|
|
Hallo, ich schreibe in Kürze eine Klausur in Geometrie und irgendwie verstehe ich den Satz von Dirac nicht. Also der Prof hat es sehr komplziert veranschaulich und formuliert. Kennt denn von euch jemand den Satz und wie könnte man es einfach beweisen. Hab schon sehr oft im Internet recherchiert aber es gibt keinen verständlichen Beweis. Ich hoffe, dass mir jemand helfen kann. Gruß yasin85 |
|
 |
|
Am besten mit dem Lemma von Bondy und Chvátal: Seien nicht benachbart in G. Sei . entstehe aus durch Hinzufügen einer Kante . habe einen Hamiltonkreis. Dann hat auch einen Hamiltonkreis. Beweis: Entweder nutzt der Hamiltonkreis von die Kante gar nicht aus und wir sind fertig. Ansonsten ergibt sich aus ihm durch Fortlassen von ein Hamiltonpfad. Auf diesem Pfad liegen die Nachbarn von . Betrachte die Nachfolger hiervon (also indem man entlang des Pfades eienn Schritt weiter geht). Da kein Nachbar von ist, hat in der Tat jeder Nachbar von einen solchen Nachfolger; das sind also auch ) Stück (und ist nicht unter ihnen). Obendrein haben wir die Nachbarn vno (zu denen ebenfalls nicht zählt). Diese beiden Mengen tummeln sich also innerhalb von Ecken (nämlich den cken ohne . Dann müssen sie wegen aber einen Punkt gemeinsam haben. Diese Ecke ist sowohl Nachbar von als auch Pfad-Nachfolger einer Ecke die Nachbar von ist. Ein Hamiltonkreis ergibt sich wie folgt: Starte bei folge dem Pfad bis gehe zu folge dem Pfad rückwärts bis gehe zu fertig. Zurück zum Satz von Dirac: Haben wir einen Graph mit den genannten Voraussetzungen, so erfüllen je zwei unverbundene Ecken die Bedingung des Lemmas. Hätte also keinen Hamiltonkreis, so auch der um eine Kante erweiterte Graph nicht. Dieser erfüllt auch die Voraussetzung von Dirac, so dass wir also wieder eine Kante ergänzen können suw., bis wir scließlich den vollständigen Graphen erhaöten. Dieser hat aber einen Hamiltonkreis, so dass wir einen Widerspruch erhalten! Also hat auch einen Hamiltonkreis. |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
523534
523325