 |
 |
 |
 |
 |
 |
Startseite » Forum » Springerproblem
Springerproblem
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|
|---|---|
|
Hi, ich habe in einem Aufgabe, ein Schachbrett der Größe 4x4 gegeben und soll dazu beweisen, dass es für einen Springer kein Hamiltonkreis gibt. Dazu habe ich mir einen solchen Graphen gezeichnet und folgenden Beweis formuliert. A1|B1|C1|D1 A2|B2|C2|D2 A3|B3|C3|D3 A4|B4|C4|D4(kann leider nicht den Graph hier zeichen^^) Es gibt keinen Hamiltonkreis, da in einem Kreis jeder Knoten genau Grad 2 hat. In meinem konstruierten Graphen sind A1 und D4 genau vom Grad 2 und sind beide zu den gleichen Knoten adjazent. Damit bilden sie miteinander einen Kreis der nicht alle Knoten enthält. Daraus folgt, dass der Graph keinen Hamiltonkreis enthält. Außerdem soll ich nun das gleiche für ein 8x8 Schachbrett zeigen. Hatte erst überlegt ob ich den Beweis für das 4x4 Schachbrett übertragen kann allerdings finde ich keine Möglichkeit dafür. Ich würde gerne wissen ob mein Beweis für das 4x4 Brett richtig ist und wie ich den Beweis für ein 8x8 Brett führen könnte. Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
| |
anonymous 12:23 Uhr, 17.01.2013 |
|
|
Ehrlich gesagt, ahne ich höchstens, was ein Hamiltonkreis ist. Meine Vermutung in meinen Worten: Ein Hamiltonkreis auf einem n*n-Schachbrett wäre eine Folge von Springerzügen, mit denen man alle Felder des Schachbretts genau einmal berührt. Falls ja: Für ein Schachbrett gibt es eine solche Folge. Ich erinnere mich, dass in einem Pascal-Kompiler ein Demo-Algorithmus angeboten wurde, der genau diese Folge iterativ suchte und ausgab. Ein Beispiel für eine solche Folge wäre ja grundsätzlich ein Beweis für die Existenz. Falls dir so eine Beweisführung genügte, dann müsste man nur eine dieser Beispielfolgen (über Züge) benennen. (Um es vorweg zu nehmen: falls du mich nach einer derartigen Folge fragen solltest, auf meinem heutigen Computer habe ich leider kein Pascal mehr. ) |
|
 |
|
|
Äh ja genau ein Hamiltonkreis ist ein Kreis auf dem alle Knoten eines Graphen liegen. zuerst wollte ich halt wissen ob mein Beweis für das 4x4 Feld stimmt. ...und dann hab ich leider die Sache für das 8x8 Feld falsch formuliert. Ich sollte bestimmen ob eines für ein 8x8 Feld existiert. Da ich ungern solange probieren möchte bis ich eines finde würde ich gerne eine Methode oder einen Ansatz für einen allgemeinen Beweis haben. |
|
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1065988
1065950