Einleitung

Mit Einführung des neuen Bildungsplans ist das Thema "Graphen" neu hinzugekommen. Graphen vervollständigen die Sammlung von Datenstrukturen, die bisher aus Listen und Bäumen bestand¹ . Graphen sind für eine Vielzahl von Anwendungen eine geeignete Modellierung, für die viele Standardalgorithmen zur Verfügung stehen. Der Bildungsplan sieht vor, diese Algorithmen "von Hand" durchzuführen oder im Leistungsfach auch mit Hilfe einer geeigneten Bibliothek zu implementieren.

Im Folgenden werden zunächst grundlegende Eigenschaften von Graphen erläutert. Dann wird untersucht, für welche Anwendungen Graphen eingesetzt werden können und welche Lösungsansätze existieren. Das Laufzeitverhalten dieser Lösungsansätze wird analysiert. Den Abschluss bilden spezielle Probleme, für die diese verschiedenen Lösungsansätze vorgestellt werden.

Graphen

„Ein Graph […] ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert. Die mathematischen Abstraktionen der Objekte werden dabei Knoten (Vertex/Vertices, auch Ecken oder Knotenpunkte) des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen Kanten (Edge, manchmal auch Bögen² ). […] Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.“³

Im Bildungsplan der Kursstufe werden die Begriffe Knoten und Kante explizit genannt. In IMP (Mathematik Klasse 8) wird allerdings Knotenpunkt und Kante eingeführt. Im Folgenden werden die Begriffe aus der Kursstufe eingesetzt.

In Klasse 8 wurde eine didaktisch reduzierte Definition empfohlen, die einen anschaulichen Zugang ermöglicht, z.B.:

oder auch knapper:

Diese Definition ist auch für die Kursstufe präzise genug.

Wichtig ist, dass "ein Graph eine Struktur bezeichnet und ein topologischer Begriff ist, da es auf die Länge der Kanten oder die Winkel zwischen den Kanten nicht ankommt."⁵ Daher ist die Position der Knoten und der gezeichnete Verlauf der Kanten irrelevant und keine Eigenschaft des Graphen. Das bekannte „Haus des Nikolaus“ kann gut als Ausgangspunkt dienen, um zu veranschaulichen, dass man beim Zeichnen eines Graphen viele Freiheiten hat⁶ :

 

Diese Repräsentationen von Graphen lassen sich durch elastische Verformungen ineinander überführen, sie sind topologisch äquivalent. Die gemeinsamen Eigenschaften (Beziehungen zwischen Knoten und Kanten) lassen sich dabei übersichtlich in einer Tabelle bzw. Matrix darstellen, die dann jeweils eine Klasse topologisch äquivalenter Graphen repräsentiert.

 

 

 

 

 

 

¹ Eigentlich sind natürlich Listen und Bäume spezielle Graphen.

² Bögen werden bisweilen auch als gerichtete Kanten aufgefasst.

³ Wikipedia: siehe Seite „Graph (Graphentheorie)“, URL: https://de.wikipedia.org/wiki/Graph_(Graphentheorie) (abgerufen: 28.03.2018)

⁴ Der im Bildungsplan verwendete Begriff Knotenpunkt kann hilfreich sein, wenn man die Visualisierung als Punkt betonen möchte, ansonsten ist die Bezeichnung Knoten üblich. Im Unterricht bietet sich auch ein Rückgriff auf die Bezeichnung „Verkehrsknotenpunkt“ in Straßen- oder Bahnnetzen an.

⁵ Eintrag Graph, in: „Schülerduden Die Mathematik I“, Dudenverlag, 1990, 5. Auflage, S.162

⁶ vgl. Nitzsche: „Graphen für Einsteiger“, Vieweg+Teubner, Wiesbaden, 2009, 3. Auflage, S.5

 

Hintergrundinformationen: Herunterladen [odt][990 KB]

 

Weiter zu Eigenschaften eines Graphen