Hamiltonkreis Springerproblem < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:24 So 12.01.2014 | | Autor: | rsprsp |
| Aufgabe | Gegeben ist ein Schachbrett n x n und ein Springer der darauf springt.
Die Frage ist ob es ein Hamiltonkreis gibt fuer das Schachbrett 4x4 ? |
Ich weiss aufjeden Fall, dass es keinen gibt, denn bei diesen Versuch n>4 sein muss. Ich komme aber nicht auf den Beweis, nicht mal auf ein Ansatz.
|
|
| |
|
Hallo rsprsp,
> Gegeben ist ein Schachbrett n x n und ein Springer der
> darauf springt.
>
> Die Frage ist ob es ein Hamiltonkreis gibt fuer das
> Schachbrett 4x4 ?
Nein, gibt es nicht.
> Ich weiss aufjeden Fall, dass es keinen gibt, denn bei
> diesen Versuch n>4 sein muss. Ich komme aber nicht auf den
> Beweis, nicht mal auf ein Ansatz.
Einen etwas allgemeineren Fall findest Du auf ![[]](/images/popup.gif) Wikipedia; allgemeiner insofern, als auf keinem (rechteckigen) Feld ein Springer-Hamiltonkreis besteht, wenn eine der beiden Kantenlängen 4 beträgt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:47 So 12.01.2014 | | Autor: | rsprsp |
Ja das ist mir schon klar. Ich habe jetzt eine Aufgabe bei der ich das jetzt beweisen soll und habe dafuer kein Ansatz.
|
|
|
| |
|
Hallo nochmal,
hm. Was soll ich jetzt damit anfangen?
> Ja das ist mir schon klar. Ich habe jetzt eine Aufgabe bei
> der ich das jetzt beweisen soll und habe dafuer kein
> Ansatz.
Für das [mm] $4\times{4}$-Brett [/mm] gibt es übrigens eine sehr viel einfachere Variante. Betrachte zwei gegenüberliegende Ecken und die Felder, die man von dort erreichen kann...
Grüße
reverend
|
|
|
|
