 |
 |
 |
 |
 |
 |
Startseite » Forum » Zeigen, dass ein Graph nicht hamiltonsch ist
Zeigen, dass ein Graph nicht hamiltonsch ist
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie, Hamilton, Hamiltonkreis
 
|
  |
|---|
|
Hey Leute, ich habe keine spezifische Frage sondern eher allgemein und zwar wollte ich wissen, wie man begründen kann, dass ein Graph nicht hamiltonsch ist. Ich kenne zwar den Satz von Ore, aber der ist ja kein richtiges Kriterium dafür. Zum Beispiel bei diesem Graph hier wie würde man hier zeigen, dass er keinen Hamiltonkreis besitzt.  Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Der Graph scheint ja extra so designt zu sein, dass die einfachen Kung-Fu-Tricks nicht greifen. Schön - um für diesen schlimmen Fall der NP-vollständigen Hamiltonkreisproblematik dennoch etwas anderes als "alles ausprobieren" (Brute Force) anbieten zu können, schreiben wir dann halt einfach ein kleines Gedicht: Symmetrie. Wir denken uns das Gebilde räumlich, bilde die obere Ebene, die untere. Nun wünschen wir uns einen Hamiltonkreis, den wir somit "abschreitend (re-)konstruieren" könnten. Wir dürfen auf ihm beginnen, wo wir wollen und starten also irgendwo auf der oberen Ebene. Irgendwo müssen wir nach unten, wegen der Symmetrie darf das OBdA die Strecke von 3 nach 5 sein (die Argumentation greift analog für die anderen drei Möglichkeiten). Bei 5 angekommen dürfen wir auf keinen Fall sofort wieder nach oben zu weil es dann unmöglich ist, die untere Ebene abzugrasen, wir müssen also auf der unteren Ebene nach 7 oder 8 abbiegen und müssen daher auch zwingend darauf bei 6 wieder hoch. Das bedeutet aber, dass wir davor unten nur die 7 oder (exklusives Oder die 8 erwischen können und nochmal runter geht es nicht mehr und 6 schon benutzt), Schach Matt ! |
|
|
|
Eine andere Erklärung: Gäbe es einen Hamiltonkreis, so gehörten zum ihm zwingend die Segmente und . Die lassen sich aber nur zu den zwei disjunkten Kreisen und zusammensetzen, weshalb schon ein Hamiltonkreis unmöglich ist. |
 |
|
Ah so geht man so eine Aufgabe also an, vielen Dank für diese ausführlichen Erklärungen. Die Symmetrie ist also mein Freund für solche Aufgaben. |
|
|
|
Na ja, ich hab halt was gedichtet. Es gibt wohl mannigfaltige Wege, das zu zeigen. Auf meinem zweiten Tipp fußend könnte man auch eine allgemeine Regel formulieren (die es vermutlich auch schon gibt). Ich bin dafür grad nicht fit genug in der Terminologie, von wegen Pfad, Zug, Kreis und was es da alles so gibt, also bleibt es vorerst bei einer kleinen Anwendung... |
|
|
|
Dein Gedicht war mir auf jeden Fall schlüssiger als die zweite Erklärung, ich verstehe Sachen schneller wenn sie nicht so fachlich erklärt werden. Bleib daher bitte bei deinen abstrakten Erklärung :-D). |
1559521
1559452