In einer vollen Milchkanne sind 8 Liter
Milch. Mit Hilfe zweier leerer Kannen, in die 3 und 5 Liter passen,
sollen 4 Liter abgemessen werden.
Es darf keine Milch verschüttet
werden, ein Gefäß kann durch Umfüllen immer nur
komplett geleert oder komplett gefüllt werden.
Diese scheinbare einfache Aufgabe soll mittels geeigneter Graphen gelöst werden.
a) Zum tieferen Verständnis der Aufgabe können Sie [hier] versuchen, das Umfüllproblem interaktiv zu lösen
b) Erstellen Sie das Schaubild eines volllständigen Graphen.
Alle möglichen Füllzustände müssen als Knoten
dokumentiert sein, gerichtete Kanten geben an, welche Umfüllungen
durchführbar sind.
Seien A, F und D die drei Kannen und
a, f und d deren momentane Füllmengen. Dann kann jeder Füllzustand
als dreiziffrige 'Zahl' afd dargestellt werden: der Knoten 800 (gesprochen:
acht null null) zeigt den Anfangszustand.
c) Sind alle denkbaren Zielzustände 440, 431, 422, 413, 341, 242 und143, die eine Vierliterfüllung repräsentieren, durch Umfüllen auch erreichbar? Begründen Sie Ihre Antwort.
d) Reduzieren Sie das Graphenschaubild aus b) zu einem Mehrwegebaum, in dem nur für die Lösung zielgerichtete Umfüllungen notiert sind; 800-350-800 ist in diesem Sinne nicht zielgerichtet.
e) Wieviele Wege im Baum führen zu einem Zielzustand? Berechnen Sie die mittlere Länge zu einem Zielfüllzustand.
f) Notieren Sie zu diesem Mehrwegebaum die Adjazenzmatrix und die Adjazenzliste.
