Hamiltonwege und -kreise
Das Virus-Rätsel
In einem Forschungslabor in der Arktis ist ein Virus ausgebrochen. Das Labor besteht aus 4 × 4 Räumen, die durch Luftschleusen mit ihren Nachbarn links, rechts, oben und unten verbunden sind. Du betrittst das Labor im Eingangsraum oben links – er ist nicht verseucht – und musst es durch den Raum unten rechts verlassen.
Jeden verseuchten Raum musst du betreten, denn dort löst du die Notverriegelung aus: Der Raum füllt sich hinter dir mit Beton. Einen betonierten Raum kannst du nie wieder betreten.
Empfohlen: Schau das Video (englisch) bis zur Aufgabenstellung – es hält bei 1:44 automatisch an. Danach löst du das Rätsel hier selbst.
Das Video liegt bei YouTube. Erst wenn du es lädst, werden Daten an YouTube (Google) übertragen.
Zustimmung zurücknehmen:
Warum ist das Rätsel unlösbar, wenn man auch den Eingangsraum nur einmal betreten darf? Nutze das Schachbrettmuster.
Definition: Hamiltonweg und Hamiltonkreis
Ein einfacher Weg heißt Hamiltonweg (Hamilton'scher Weg), wenn er alle Knoten des Graphen genau einmal enthält. Seine Länge ist die Anzahl der Knoten minus 1; Startknoten ≠ Endknoten.
Ein Kreis heißt Hamiltonkreis, wenn er alle Knoten des Graphen genau einmal enthält – außer dem Start-/Zielknoten. Startknoten = Endknoten.
Zeige auf die Begriffe: Im Graphen erscheint ein Beispiel mit nummerierten Schritten.
G = (V, E)
V = {A, B, C, D, E}
E = {{A,B}, {B,C}, {C,D}, {D,E}, {E,A}, {B,E}, {C,E}}
Auf der Kirmes
Die Kirmes hat sieben Attraktionen. Du möchtest alle besuchen, vom Riesenrad zur Achterbahn, aber keine zweimal.
Aufgabe 3: Abstrahiere die Kirmes als Graphen. Die Knoten sind gesetzt (Kürzel wie auf der Karte).
Aufgabe 3: Abstrahiere die Kirmes als Graphen. Die Knoten sind gesetzt (Kürzel wie auf der Karte).
Aufgabe 4: Welche besondere Eigenschaft hat der Weg RSZHKWA?