Euler-Kreis

Begriffe: Graph, Kartengraph, Knoten, Kante, Pfad, Zyklus, Kreis, Zusammenhang, Breitensuche, Tiefensuche

Als Einstieg in das Thema Graphen bietet es sich an, mit einem Beispiel zum Euler-Zug zu beginnen. Der Euler-Kreis (Achtung: eigentlich falsche Bezeichnung³ !) wurde schon in IMP in Klasse 8 eingeführt, bietet sich aber für eine vertiefte Behandlung in der Kursstufe an. In Klasse 8 wurde die Voraussetzung besprochen, dass der Grad aller Knoten gerade sein muss, damit es einen geschlossenen Euler-Zug gibt. Die zweite (offensichtliche) Bedingung, dass der Graph zusammenhängend sein muss, kann in der 8. Klassenstufe nur schwer problematisiert werden. In der Kursstufe wiederum kann genau dies den Einstieg in eine für die Implementation eines Algorithmus notwendige Sicht auf Graphen darstellen. Die Schülerinnen und Schüler müssen sich in die Froschperspektive begeben: Nur wenige globale Eigenschaften des Graphen (Anzahl Knoten, Anzahl Kanten) sind verfügbar, ansonsten kann nur auf einen einzigen Knoten (aktueller Knoten) und seine Nachbarn zugegriffen werden. In dieser Sicht ist die Zusammenhang- Eigenschaft eines Graphen alles andere als offensichtlich.

Eine Möglichkeit diesen Zusammenhang zu testen, besteht darin per Tiefen- oder Breitensuche alle von einem Knoten aus erreichbaren Knoten durchzuzählen und mit der Gesamtzahl der Knoten zu vergleichen. Tiefen- und Breitensuche sollte den Schülern von Bäumen bekannt sein, wenn dies vorher behandelt wurde. Die Erweiterung auf allgemeine Graphen mit Zyklen erfordert eine Markierung der schon der ToDo-Liste hinzugefügten und schon abgearbeiteten Knoten.

Der Unterricht kann mit einem Einstiegsbeispiel (Schiffsrouten - kopiervorlagen/01_eulerzug.odt, Seite 1) starten. Bei diesem ersten Beispiel sollte die Modellierung des Problems als Graph gemeinsam mit den Schülerinnen und Schülern durchgeführt werden (praesentation/03_eulerzug.odp, Folie 2).

Die Begriffsbildung sollte gleich von Anfang durch das Anlegen eines Glossars (kopiervorlagen/01_glossar.odt) unterstützt werden. Es ist wichtig, den Wissensvorsprung durch den Besuch von IMP an dieser Stelle auszugleichen, da das Thema Graphen im Brückenkurs nicht vorkommt und daher nicht allen Schülerinnen und Schülern die Begriffe bekannt sind. Alle Begriffe sind in der Präsentation praesentationen/01_grundbegriffe.odp erläutert. Diese ist nicht als fortlaufende Präsentation gedacht. Sie sollten die für ihren Unterricht notwendigen Folien an den passenden Stellen heraussuchen. Die für das Einstiegsbeispiel "Schiffsrouten" relevanten Begriffe werden in der Präsentation 03_eulerkreis.odp auf den Folien 3-6 herausgesucht.

Der Perspektivwechsel von der Adler- zur Froschperspektive ist bei der Überprüfung des Grades der Knoten einfach, da man ohnehin jeden einzelnen Knoten betrachten muss (Folie 7). Beim Zusammenhang des Graphen (Folie 8) sind sieben Abbildungen vorhanden, auf denen je einer der sieben Knoten fokussiert und in Froschperspektive dargestellt ist. Hier ist nicht offensichtlich, wie man nur mit diesen Bildern feststellen kann, ob der Graph zusammenhängend ist. Der Algorithmus kann nun auf die oben beschriebenen Weisen im Unterricht erörtert werden:

• Selbstentdeckend: DieSchülerundSchülerinnenbekommeneineListemitFähigkeiten des Froschs und müssen damit einen Algorithmus entwerfen. Dabei reicht es nicht aus, die sieben Bilder zu haben, da man nicht weiß, welches Bild zu einem Nachbarknoten gehört. Daher kann hier entweder die unplugged-Version oder der Experimentiermodus des Graphen-Testers zum Einsatz kommen (03_zusammenhang_beispiel1.csv und 04_zusammenhang_beispiel2.csv).
• Der Pseudocode oder die textuelle Beschreibung wird vorgegeben und die Schüler vollziehen das Verfahren unplugged oder im Graphentester nach. Beides kann auch als gestufte Hilfe verwendet werden, wenn mit der selbstentdeckenden Variante gestartet wird. (kopiervorlagen/01_eulerkreis.odt, Seite 4 und 5).
• Die Schüler sollen im Simulationsmodus des Graphentesters den Algorithmus für Breiten- und/oder Tiefensuche auf die Beispieldateien anwenden, den Algorithmus beschreiben und überlegen, wie man diesen Algorithmus nutzen kann, um herauszufinden, ob der Graph zusammenhängend ist. Das Hilfefenster des Graphentesters kann schwächeren Schülern bei der Beschreibung helfen. Den Abschluss könnte die Kommentierung des Quelltextes des Algorithmus bilden. (kopiervorlagen/ 01_eulerkreis.odt, Seite 6).

Die fertige Implementation des Algorithmus zum Nachweis der Existenz eines Euler-Zuges sollte als Abschluss der Stunde gezeigt werden.

Weiterführende Fragen können Sie als Vertiefung einsetzen und beispielsweise auch als Hausaufgaben verwenden.

GFS

Der Unterrichtsentwurf behandelt nur einen Algorithmus, um die Existenz eines Euler-Zuges nachzuweisen. Damit ist noch nicht klar, wie der Euler-Zug gefunden werden kann. Die Algorithmen von Hierholzer oder Fleury lösen dieses Problem. Dies wäre eine mögliche Ergänzung, die sich gut für eine GFS eignet:

• Der Algorithmus von Hierholzer (Eulerkreisproblem)https://www.youtube.com/watch?v=aAKDDW4gUGs (Sep. 2020)
• Der Algorithmus von Fleury (Eulerkreisproblem) https://www.youtube.com/watch?v=I_6ODtkaDwo

³ Im allgemeinen Sprachgebrauch wird das Problem des geschlossenen Euler-Zuges oft als Euler-Kreis bezeichnet, obwohl ein Kreis jeden Knoten nur einmal enthalten darf und in einem Euler-Zug im Allgemeinen die Knoten mehrfach besucht werden. Daher wird hier nur der Begriff Euler-Zug verwendet.

Unterrichtsverlauf: Herunterladen [odt][298 KB]

Weiter zu Problem der topologischen Sortierung (optional)