DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000
Gefährliche Tiere
Der Zirkusdirektor war grün vor Ärger.
Der neue Wärter hatte die wilden Tiere sämtlich
in die falsche Käfige gesteckt.
"Sofort bringen Sie die Tiere wieder in ihre eigenen
Käfige", befahl der Direktor,
"aber passen Sie auf, daß sich die Bestien nicht gegenseitig
zerreissen. Auf keinen Fall dürfen zwei Tiere in einen
Käfig gesperrt werden."
Beachten Sie, daß es zwischen eng aneinanderstehenden
Käfigen Türen gibt. In welcher Minimalzahl von einzelnen
Operationen kann der Wärter den Befehl ausführen, und in welcher
Reihenfolge müssen die Operationen ausgeführt werden?
(nach "99 Logeleien von Zweistein, Hamburg 1968")
Was hat das mit Graphen zu tun? Natürlich gibt es
den Verbindungsgraphen G der Käfige, der schematisch
rechts abgebildet ist. Dabei sind die Ecken gleich mit
den Imagenummern diser HTML-Seite nummeriert, d.h.
V(G)={1,2,4,6,7,8}.
Ein Zustand ist jede zulässige (keine zwei Tiere
in demselben Käfig) Belegung der Tiere auf die Käfige.
D.h. ein Zustand ist eine injektive Abbildung
f:{T,B,L,N,F} ® {1,2,4,6,7,8}.
Zwei Zustände f,g sind benachbart, wenn einer aus dem
anderen durch eine direkte Tierbewegung erreichbar ist,
d.h. wenn f(x)=g(x) für alle bis auf ein Element
y aus {T,B,L,N,F} gilt, und wenn f(y) und g(y) für dieses y
in G benachbart sind.
Damit haben wir einen Graphen H auf der Eckenmenge
aller 6*5*4*3*2 = 720 Zustände definiert. In diesem Graphen
kann man Abstände berechnen, etwa mit dem Algorithmus von
Dijkstra, was das Javascript Programm tut.
H ist übrigens zusammenhängend und hat Durchmesser
(d.h. größten auftretenden Abstand) 16.
Die Methode ist leider nur für kleine zugrundeliegende Graphen
praktikabel. Beim bekannten 4 × 4 Schieberätsel
hat H 16! = 16*15*14*...*2, etwa 20 Billionen Ecken.
Im obigen Rätsel haben wir Symmetrie zwischen den Tieren,
aber das leere-Käfig-Feld hat eine Sonderrolle.
Deshalb gibt es vier Typen von Zuständen:
Zustände mit leerem oberen Feld, leerem Mittelfeld,
leerem oberen seitlichen Feld, bzw. leeren seitlichen unteren
Feld. Während der Abstand von Typ 3 (wie oben rechts)
zu jedem anderen Zustand höchstens 14 beträgt,
kommt zwischen Zuständen gewissen (welchen?) anderen
Typs Abstand 16 vor.
Zurück zu den Graphen
Erich Prisner
erstellt im Mai 2000.
