Materialien GK/LK Informatik Stufe Q2/13:

Graphen, Adjazenzmatrix und -liste
am Beispiel Milchkannen-Umfüllen

Aufgabe:

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.

 

Weitere Materialien:


© 2006 Ziemke .:. Letzte Aktualisierung am 5. Februar 2006 durch den WebMaster