Schachaufgabe 4*4 mit Graphen und Hamilton lösen?

Question

Hallo :-)

Ich habe folgende Aufgabe:

Zeige: Es ist nicht möglich, einen Springer auf einem 4×4-Schachbrett so zu ziehen, dass jedes Feld genau einmal besucht wird.

Ansatz/Problem:

Ich habe bereits recherchiert und habe erfahren, dass man diese Aufgabe mit Graphen und Hamiltonkreis (?) zeigen kann.

Ich weiß aber nicht wie ich das mir mit Graphen veranschaulichen soll und was mir der Hamiltonsatz oder Kreis bringt.

Kurz gesagt ich weiß nicht wie ich diese Aufgabe zeigen soll. :-(

Kann mir jemand helfen ?

:-)

Answer 1

Zeichne einen Graphen mit 16 Knoten, die den Feldern auf dem Schachbrett

entsprechen,

          1                2                 3                    4

           5                 6                 7                   8

          9                  10               11                12

         13                  14              15                16

Verbinde jetzt jeden Knoten mit denen, die ein Sringer

von dort erreichen könnte, also z.B

die 2 mit 9, 11 und 8  und

die   3  mit 5 , 10 und 12 .

Dann sind das schon mal zwei Knoten, die eine ungerade

Zahl von Kanten bei sich ankommen haben.

Sie können also höchstens Anfangsknoten oder

Endknoten einer Rundreise über alle Knoten sein.

Nun haben aber z.B. die  14 und die 15 auch jeweils nur 3

Kanten . Da es aber nur einen Anfangs- und einen Endknoten

geben kann (ohne welche auszulassen oder mehrfach zu

berühren) kann es einen solchen Weg nicht gegen.

(s.auch: Problem der Königsberger Brücken)

Comments

Genau! Und wenn ich es mit dem Hamilton Weg begründen möchte, dann verstößt es gegen den Satz vom Hamilton Weg, also man kann nicht jeden Knoten erreichen ohne einen anderen Knoten nur einmal berührt zu haben, richtig ? Bzw. man berührt einen Knoten mehrmals, richtig ?

Vielen Dank für die Hilfe :-)

---

Du solltest dir nochmal ein gutes Buch über diskrete Mathematik durchlesen, beispielweise das von Steger. Ob die Kantenanzahl gerade oder ungerade ist, interessiert uns bei Eulertouren (das Königsberger Brückenproblem ist ein typisches Beispiel hierfür), aber dies sind Pfade, die alle Kanten genau einmal verwenden und haben nichts zu tun mit Hamiltonkreisen/-pfaden, die alle Knoten genau einmal besuchen...

Answer 2

Die Graphentheorie ist bei dieser Aufgabe eher zweitrangig, es geht um die mathematische Argumentation. Nimm zunächst an, eine Springertour existiert. Du kannst begründen, was dann (bis auf Symmetrie) die ersten vier Felder deiner Tour sein müssten, und was die letzten vier Felder deiner Tour sein müssten. Warum kriegst du jetzt ein Problem? (Mehr kann ich dir nicht verraten, Abgabe ist schließlich erst morgen.)

Comments

Alles gut, hab die Aufgabe gestern verstanden, aber vielen dank für die Hilfe :-)