Zur Hauptnavigation springen [Alt]+[0] Zum Seiteninhalt springen [Alt]+[1]

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 bestand1 . 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ögen2 ). […] Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.“3

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.:

Graphen

Ein Graph ist eine geometrische Figur aus endlich vielen Knotenpunkten und Kanten, die einige dieser Punkte verbinden. Die Kanten müssen nicht geradlinig verlaufen und können sich überkreuzen. Mehrfachkanten, Schlingen und isolierte Knoten sind ebenfalls zugelassen.

oder auch knapper:

Graphen

Ein Graph ist ein Gebilde, das aus Knotenpunkten4 und Kanten besteht. Jede Kante verbindet 2 Knotenpunkte.

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."5 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 hat6 :

Das Haus des Nikolaus wird schrittweise zu topologisch äquivalenten Graphen „verformt.“

Abbildung 1: Das Haus des Nikolaus wird schrittweise zu topologisch äquivalenten Graphen „verformt.“ ZPG Informatik [CC BY-SA 4.0 DE], aus 1_graphen_hintergrund.odt

 

Matrix topologisch äquivalenter Graphen

Tabelle: Matrix topologisch äquivalenter Graphen ZPG Informatik [CC BY-SA 4.0 DE], aus 1_graphen_hintergrund.odt

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.

 

 

 

 

 

 

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

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

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

4 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.

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

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

 

Hintergrundinformationen: Herunterladen [odt][990 KB]

 

Weiter zu Eigenschaften eines Graphen