Vorstellung des Problems

Einige der im Folgenden recht häufig verwendeten Begriffe werden hier vorab kurz erläutert:

• Hamilton-Pfad

  Ein Hamilton-Pfad ist ein Weg in einem Graphen, der jeden Knoten genau einmal besucht.

• Hamilton-Zyklus

  Ein Hamilton-Zyklus ist ein Rundweg (endet also am Ausgangspunkt) in einem Graphen, der jeden Knoten genau einmal besucht.

• Euler-Tour

  Eine Euler-Tour ist eine Runde durch einen Graphen, welche jede Kante genau einmal enthält.

Der Einstieg in die Stunde erfolgt über die Präsentation des folgenden Problems:

Der Geschäftsmann Peter Müller möchte gerne von seinem Firmensitz in Aachen aus seine Schwester in Berlin besuchen. Allerdings möchte er vorher noch bei seinen Kunden in Frankfurt und Köln vorbeischauen. Nun bietet die Fluggesellschaft "GünstigAir" für die Strecken Aachen-Köln, Köln-Aachen, Aachen-Berlin, Köln-Frankfurt, Köln-Berlin und Frankfurt-Berlin, Flüge für jeweils 20 € an. Herr Müller würde nun gerne diese günstigen Flüge nutzen. Wie kann er am besten fliegen?

Daraufhin wird ein Aufgabenblatt verteilt, das die Schülerinnen und Schüler in Partnerarbeit bearbeiten. Ihre Aufgabe ist es, einen Weg zur Lösung des Problems zu beschreiben und diesen so aufzubereiten, dass er an der Tafel anschaulich präsentiert werden kann.

Bei der anschließenden Besprechung des Arbeitsblattes präsentieren zwei bis drei Gruppen ihre Ergebnisse an der Tafel (Zeichnung). Das Problem wird anschließend formalisiert:

Gesucht ist in der Schemazeichnung ein Weg, der von Aachen nach Berlin führt, mit Zwischenstopps in Köln und Frankfurt (also ein Hamilton-Pfad von Aachen nach Berlin).

Die Schülerinnen und Schüler notieren die Problemformulierung und zeichnen die Grafik ab, damit sie diese in den folgenden Stunden immer zur Hand haben. Für die Probleminstanz wurde ganz bewusst ein geringer Schwierigkeitsgrad gewählt. Um die Frage zu klären, ob man mit DNA überhaupt rechnen kann, sollte man mit einem einfachen Problem beginnen. Wenn sich dann zeigen sollte, dass das Problem schnell gelöst wird, können auch größere Instanzen bewältigt werden.