0 Daumen
937 Aufrufe

Aufgabe:

Gegeben sei ein Schachbrett mit \( n \times n \) Feldern. Ein Springer bewegt sich auf dem Schachbrett indem er zwei Felder in eine Richtung und dann ein Feld zur Seite zieht (wie im normalen Schachspiel). Ist es mōglich, dass der Springer auf einem beliebigen Feld startet, alle Felder des Schachbrettes genau einmal besucht und am Schluss wieder auf seinem Ausgangsfeld steht?

a) Modellieren Sie das Problem als Hamiltonkreisproblem über einem geeigneten Graphen \( G \) -

b) Existiert ein solcher Kreis in einem Schachbrett mit \( 4 \times 4 \) Feldern? Geben Sie einen Hamiltonkreis an oder beweisen Sie, dass kein solcher exisiert

c) Existiert ein Hamiltonkreis für das normale Schachbrett mit \( 8 \times 8 \) Feldern?

von

1 Antwort

0 Daumen
Für c) wollen die Tutoren einfach nur das man googled (https://de.wikipedia.org/wiki/Springerproblem).

a) und b) lassen auf dieselbe weise mit einem 4x4 Feld lösen, also mit Diagonalen.

Und für b) kann man noch den Tipp Zusammenhangskomponenten geben.
von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community