Modellierung von Problemen mit Graphen

Die Modellbildung ist ein in der Informatik entscheidender Vorgang, dem im Bildungsplan durch die prozessbezogene Kompetenz "2.2 Modellieren und Implementieren" Rechnung getragen wird. Die SuS sollen "vorliegende Informationen für die Lösung geeignet aufbereiten (zum Beispiel durch Filtern, Reduktion, Kategorisieren)" und "charakteristische und verallgemeinerbare Bestandteile herausarbeiten (Abstraktion)".

Um von einem Problem zu einer sinnvollen Modellierung zu kommen, muss also als erstes entschieden werden, welche Informationen der Problemstellung relevant sind und welche nicht. Dies wird als Methode der Abstraktion bezeichnet: "Die Verwendung von Abstraktion als Methode befreit uns von dem Zwang, bei der Darstellung der Wirklichkeit auch Dinge zu repräsentieren, die uns nicht interessieren. Abstraktion verwenden wir immer auch dann, wenn die Realität zu komplex oder zu umfangreich ist, um sie zu erfassen oder zu manipulieren. Realität bedeutet in diesem Fall gebaute oder geplante Architektur. Jeder Versuch, die Wirklichkeit zu repräsentieren, ist bereits eine Abstraktion. Die einzige vollständige Repräsentation der Wirklichkeit ist das Objekt selbst. Abstraktion wird damit zu einer wichtigen Eigenschaft der Repräsentation."⁹

Gallenbacher stellt dies in seinem Buch "Abenteuer Informatik"¹⁰ am Beispiel des Dijkstra-Algorithmus schön dar. Er beginnt mit einer Landkarte und lässt den Leser überlegen, welche der folgenden Informationen relevant sind: Name der Städte, Position der Städte, Größe der Städte, Länge der Straße, Verlauf der Straße usw. Man stellt fest, dass nur wenige Informationen wirklich notwendig sind. Dabei stellt man fest, dass z.B. die Position der Städte und der Verlauf der Straßen völlig unerheblich sind. Auf Ebene der Graphen formuliert: Man darf den Graph isomorph umformen, ohne dass sich etwas am Ergebnis der Berechnung des kürzesten Weges ändert.

Als zweiten Schritt schlägt Gallenbacher noch vor, die Methode der Gleichformung anzuwenden, um Spezialfälle zu vermeiden und sie möglichst auf den Standardfall zurückzuführen. Bei der Routenplanung hat man zunächst die Idee, die Städte als Knoten eines Graphen zu definieren. Nicht jede Straße verbindet aber genau zwei Städte. Meist gibt es Kreuzungen dazwischen mit Abzweigungen zu anderen Städten. Sinnvoll ist es hier, auch die Kreuzungen wie Städte als Knoten zu modellieren. Es wird zwar vermutlich nie jemand diese Kreuzungen als Start- oder Zielort wählen, aber es vereinfacht den Algorithmus erheblich, wenn keine Spezialfälle auftreten.

Graphen als Modelle

Die Einheit Graphen ist bestens geeignet, Modellbildung zu üben, da Graphen für eine große Bandbreite verschiedener Anwendungen geeignet sind. Die Bedeutung von Knoten und Kanten wechselt je nach Anwendungsfeld und muss immer wieder aufs Neue herausgearbeitet werden. Am Ende steht immer ein Graph, der eine sehr abstrakte Darstellung wesentlicher Informationen darstellt:

Die Knoten repräsentieren eine Menge gleichartiger, diskreter Objekte; jede der Kanten repräsentiert eine Beziehung zwischen je zwei Objekten, die sie verbindet. Solche Graphen sind also 2-stellige Relationen über der Knotenmenge. Ungerichtete Graphen können dabei nur symmetrische Beziehungen und Relationen modellieren (wie "sind befreundet", "sind benachbart". "sind verbunden"), gerichtete Graphen modellieren asymmetrische Beziehungen und Relationen (wie "ist abhängig von", "impliziert", "muss vorher ausgeführt werden", "ist besser als").

Gewichtete Graphen bzw. Kanten mit Zusatzinformation werden notwendig, wenn weitere Informationen über die Beziehungen wichtig sind: z.B. die Entfernung zwischen zwei Orten, die Leitungskapazität von Rohrleitungen oder das Übergangssymbol bei Automaten.

Das Einsatzgebiet von Graphen ist dadurch beschränkt, dass nur eine endliche Anzahl diskreter Objekte in Form von Knoten repräsentiert werden können:

Es können also nicht unendliche viele Knoten existieren. Z.B. können für Umgießrätsel drei verschiedene Füllhöhen in einem Gefäß als Knoten modelliert werden, aber nicht beliebige Füllhöhen.
Die Beziehungen in einem Graph bestehen immer nur zwischen zwei Knoten¹¹ : Man kann also nicht ausdrücken, dass drei Personen einen Freundeskreis bilden, sondern nur, dass jeweils zwei von ihnen untereinander befreundet sind und alle drei eine Clique bilden (d.h. einen vollständigen Teilgraph). Genauso lässt sich ein Bussystem im Computer, bei dem viele Geräte an eine Leitung angeschlossen sind, nicht abbilden, ohne zusätzliche „Verzweigungsknoten“ einzuführen.

Diese Beschränkungen sind der Preis für die Einfachheit der Darstellung und die damit verbundene Zugänglichkeit der Algorithmen.

Anwendungsgebiet: Matching-Probleme

Ein Graph kann verwendet werden, um auszudrücken, dass bestimmte Objekte zueinander passen. Dabei kann es sich um lauter gleichartige Objekte handeln, z.B. Kinder, die angeben, neben wem sie im Bus sitzen wollen, oder auch um zwei Typen von Objekten, z.B. Männer und Frauen, die zu Tanzpaaren gruppiert werden sollen. Im zweiten Fall ist der Graph dann auf jeden Fall bipartit, da es keine Beziehungen innerhalb einer Gruppe von Objekten geben kann (ja, es könnten auch Männer mit Männern und Frauen mit Frauen tanzen...).

Ein Matching ist dann ein Teilgraph mit der Eigenschaft, dass keine zwei Kanten einen gemeinsamen Knoten haben, d.h. jedes Objekt wird maximal einem Matching-Paar zugeordnet.

Typische Fragestellungen sind dann:

Wie erreicht man möglichst viele Paarungen?
Ist es möglich, alle Objekte zu matchen (perfektes Matching)?
Wenn der Graph gewichtet ist (z.B. um anzugeben, wie gerne sich zwei Personen mögen), kann man versuchen, eine maximale Bewertung des Matching zu erreichen.

Anwendungsbeispiele:

Piloten sollen auf Flugzeuge verteilt werden, wobei jeder Pilot nur bestimmte Flugzeuge fliegen darf, da er nur für deren Typ eine Lizenz hat.
Ampelschaltung: Es gibt verschiedene Verkehrsflüsse an einer Kreuzung (Rechtsabbieger, Fußgänger usw.). Manche können die Kreuzung gleichzeitig überqueren. Gesucht sind möglichst große Cliquen, da diese gleichzeitig grün bekommen können.

Im Bildungsplan:

Matching-Probleme kommen im Bildungsplan nicht vor.

Anwendungsgebiet: Unverträglichkeitsgraphen

Das ist im Prinzip das Gegenteil des Matching-Problems. Hier drückt eine Kante des Graphs aus, dass zwei Objekte nicht zueinander passen: z.B. geben Schüler und Schülerinnen an, mit wem sie auf gar keinen Fall bei einer Klassenfahrt in einem Zimmer übernachten wollen. Manche Probleme kann man entweder als Matching-Graph oder als Unverträglichkeitsgraph darstellen. Daraus ergeben sich dann unterschiedliche Lösungsansätze des Problems.

Typische Fragestellungen sind dann:

Finde eine Aufteilung in k Teilgruppen, so dass keine Unverträglichkeiten auftreten.
Ist es möglich, die Knoten in k Teilgruppen aufzuteilen, so dass innerhalb einer Teilgruppe keine Kante, also keine Unverträglichkeit, existiert? Dies bedeutet, dass der Graph k-partit ist.
Wie viele Teilgruppen werden mindestens benötigt, damit keine Unverträglichkeiten auftreten?

Anwendungsbeispiele:

Kartenfärbeproblem: Eine Karte soll so gefärbt werden, dass aneinander angrenzende Länder nicht die gleiche Farbe haben.
Frequenzproblem: Die Frequenzen von Sendemasten mit teilweise überlappenden Sendebereichen sollen so verteilt werden, dass keine Interferenzen auftreten.
Fische im Zoo: Möglichst viele Fischsorten sollen in zehn Aquarien präsentiert werden, wobei es Fischarten gibt, die nicht miteinander untergebracht werden dürfen.
Ampelschaltungen: Es gibt verschiedene Verkehrsflüsse an einer Kreuzung (Rechtsabbieger, Fußgänger usw.). Manche schließen sich gegenseitig aus Sicherheitsgründen aus. Gesucht sind möglichst wenige Teilgruppen, die verträglich sind.
Stundenplanung Oberstufe: Welche Kurse können auf eine Schiene gelegt werden?
Sudoku: In jedem Feld soll eine Zahl stehen, die nicht schon in einem anderen Feld derselben Zeile, Spalte oder demselben Block steht.

Im Bildungsplan:

3.3.2.2 Algorithmen auf Datenstrukturen (12) "Strategien (zum Beispiel Greedy) zur Bestimmung von Näherungslösungen in polynomieller Laufzeit beschreiben und an geeigneten Problemstellungen (zum Beispiel 4-Farben-Problem, Dominating Sets) von Hand durchführen".

Anwendungsgebiet: Topologische Sortierung

Bei vielen Dingen ist eine Sortierung bezüglich messbaren Größen eindeutig möglich: z.B. Menschen nach Gewicht, Städte nach Einwohnerzahl. Bei anderen Dingen gelingt dies nicht so einfach. Sollen z.B. Aktionen in eine Reihenfolge gebracht werden, bei denen nur bei einigen Schritten festgelegt ist, dass sie vor anderen Schritten ausgeführt werden müssen, dann ist nicht von vornherein klar, ob eine Reihenfolge existiert. Die Beziehungen zwischen den Schritten können als gerichteter Graph dargestellt werden.

Typische Fragestellungen:

Existiert eine topologische Sortierung, d.h. eine Reihenfolge, so dass keine Abhängigkeit verletzt wird? Dies ist gleichbedeutend mit der Frage, ob der Graph keinen Zyklus hat.
Finde eine topologische Sortierung. Diese ist nicht notwendig eindeutig.

Anwendungsbeispiele:

Das Anziehen von Kleidungsstücken legt gewisse Reihenfolgen fest: z.B. Schuhe nach den Socken, lässt aber doch viele Freiheiten. Gesucht ist eine topologische Sortierung.
Verklemmungen bei parallelen Prozessen: Wenn die Prozesse A, B, C usw. auf Ressourcen warten, die von anderen Prozessen belegt sind, kann es zu gegenseitigen Blockaden kommen. Dies ist der Fall, wenn es keine topologische Sortierung gibt.
Erstellung einer To-Do-Liste mit gegenseitigen Abhängigkeiten.

Im Bildungsplan:

3.3.1.2 Datenstrukturen (5) "Begriffe aus der Graphentheorie (unter anderem Knoten, Kanten, Knotengrad, Kreis/Zyklus) und Eigenschaften von Graphen (unter anderem gerichtet/ungerichtet, gewichtet/ungewichtet, zyklisch/azyklisch) verwenden".

Anwendungsgebiet: Wegeprobleme

Die Kanten des Graph beschreiben hier die direkte Verbindung von zwei "Orten" (durch eine Straße, eine Brücke, eine Leitung usw.). Ein Weg über mehrere Kanten verbindet auch Knoten, die nicht direkt benachbart sind. Kantengewichte können dabei Entfernungen oder Zeitbedarf ausdrücken.

Typische Fragestellungen:

Finde einen möglichst kurzen Weg von A nach B.
Finde einen möglichst kurzen Weg, der an allen Knoten verbindet (ohne einen doppelt zu besuchen).
Existiert ein Weg, der jeden Knoten genau einmal besucht? (Hamiltonkreis)
Existiert ein Kantenzug, der jede Kante genau einmal benutzt? (Euler-Zug)
Mit welcher Wahrscheinlichkeit gelangt man zu welchem Knoten, wenn man sich zufällig durch den Graphen bewegt?
Welches ist der längste Weg (kritischer Weg) durch einen gerichteten Graphen?

Anwendungsbeispiele

Routenplanung bei einem Navigationsgerät. Dabei kann zwischen schnellster und kürzester Strecke gewechselt werden.
Haus vom Nikolaus: Finde einen Kantenzug, um es in einem Zug zu zeichnen.
Königsberger Brückenproblem
Bei der Projektplanung können Knoten Zwischenstufen darstellen und gerichtete, gewichtete Kanten die benötigte Zeit, um diese Stufe zu erreichen. Da manche Prozesse auch parallel ablaufen können, ergibt sich ein verzweigter Graph. Der kritische Pfad legt die Dauer des gesamten Projekts fest.
Schaltungselektronik: Jedes elektronische Bauteil hat eine gewisse Verzögerung. Der kritische Pfad in einer elektronischen Schaltung gibt damit die minimale Taktzeit vor.

Im Bildungsplan:

3.3.2.2 Algorithmen auf Datenstrukturen (10) "einen Algorithmus [...] zur Lösung des Problems des kürzesten Pfades (zum Beispiel Dijkstra, Bellman-Ford) beschreiben und an Beispielen von Hand durchführen".

Anwendungsgebiet: Verbindungsprobleme

Ähnlich wie bei Wegeproblemen beschreibt der Graph Orte und ihre direkte Verbindungen. Man untersucht aber nicht Wege, d.h. Folgen von Kanten (ohne Verzweigung), sondern interessiert sich für den Zusammenhang eines Graphen. Es sollen beispielsweise je zwei beliebige Knoten untereinander über mindestens einen Weg miteinander verbunden sein.

Typische Fragestellungen:

Finde eine Teilmenge der Kanten, die den Graphen zu einem zusammenhängenden Graph machen, und deren Gesamtgewicht möglichst klein ist. (Minimal spanning tree)
Ist der Graph noch zusammenhängend, wenn man eine Kante/Knoten entfernt? Dies ist wichtig für Ausfallsicherheit.
Bestimme die maximale "Durchflussmenge" durch einen gerichteten, gewichteten Graphen.

Anwendungsbeispiele:

In einer Stadt soll eine Straße/eine Kreuzung gesperrt werden. Sind dann trotzdem noch alle Straßen erreichbar?
Eine Gas-/Wasserversorgung soll für eine Stadt geplant werden. Wie sollten die Leitungen verlegt werden?
In einer Großstadt werden zur Rushhour einige Straßen zu Einbahnstraßen erklärt. Sind trotzdem noch alle Straßen erreichbar?
Planung von Schifffahrtsrouten zwischen den Inseln einer Inselgruppe.
Verkehrsplanung: Wie viele Autos können durch das Straßennetz maximal pro Zeitschritt von A nach B fahren, wenn alle Straßen so gut wie möglich genutzt werden? Das kann z.B. für die Planung der Anfahrtrouten bei Großveranstaltungen wichtig sein.

Im Bildungsplan:

3.3.2.2 Algorithmen auf Datenstrukturen (10) "einen Algorithmus (zum Beispiel Prim, Kruskal) zur Bestimmung eines Minimum Spanning Tree [...] beschreiben und an Beispielen von Hand durchführen".

⁹ Schmitt G.N. (1993) Methode: Abstraktion und Modellbildung. In: Architectura et Machina. Vieweg+Teubner Verlag, https://link.springer.com/chapter/10.1007/978-3-322-83972-5_10 (Abgerufen 06.05.2020)

¹⁰ Gallenbacher, Jens (2008), Abenteuer Informatik, Spektrum Verlag

¹¹ Es gibt auch sogenannte Hypergraphen, die mehr als zwei Knoten bei einer Kante zulassen. Die sollen hier aber nicht berücksichtigt werden.

Hintergrundinformationen: Herunterladen [odt][990 KB]

Weiter zu Algorithmen mit optimaler Lösung