Modellierung durch Graphen
Definition
Grob gesagt: Ein Graph wird beschrieben durch seine Knoten und Kanten, d. h. "Ecken" und Verbindungen zwischen diesen. Im allgemeinen werden Graphen benutzt, um Flüsse durch Netzwerke zu beschreiben oder Wege zu finden. Je nach Anwendungsfall benutzt man
ungerichtete Graphen: eine Kante verläuft sozusagen "symmetrisch", Anfangs- und Endknoten sind gleichberechtigt.
gerichtete Graphen: die Kanten unterscheiden zwischen Anfangs- und Endknoten; ein Fluß durch das Netzwerk kann die Kante nur in einer Richtung durchfließen.
ungewichtete Graphen: Eine Kante ist entweder da oder nicht.
gewichtete Graphen: Jede Kante besitzt ein gewisse Maximalkapazität oder ein Kostenmaß. Dadurch kann ein Algorithmus auf diesem Graphen beispielsweise maximale Durchsatzraten in einem Graphen, in dem ein Start- und ein Zielknoten ausgezeichnet sind, bestimmen. Über ein Kostenmaß können die Wege als verschieden "teuer" angesehen werden, so daß ein Algorithmus zur kürzesten Wegfindung auf einer kompakten Darstellung eines Verkehrsnetzes arbeiten kann.
Algorithmen
Die wichtigsten Algorithmenklassen auf Graphen sind Wegfindungs-Algorithmen und der Max-Flow-Min-Cut-Algorithmus.
Wegfindung
Zu vorgegebenem Start- und Zielknoten ist eine kürzeste Verbindung gesucht. Die "Länge" eines Wegs wird dabei als Summe der Kantengewichte modelliert; bei ungewichteten Graphen werden einfach die einzelnen Kanten gezählt (entspricht Gewichtung mit 1).
Max-Flow-Min-Cut
Im Graphen seien ein Anfangs- und ein Endknoten ausgezeichnet. Nach dem (relativ berühmten) Max-Flow-Min-Cut-Theorem von Ford und Fulkerson sind die folgenden Probleme äquivalent:
Max Flow: Finde einen Verbindung maximaler Durchsatzrate durch den Graphen. Dabei wird für jede Kante festgehalten, "wie viel" auf ihr transportiert werden soll (limitiert durch ihre Kapazität, d. h. ihr Kantengewicht), an den Knoten kann jeweils von einkommenden Kanten auf auslaufende umverteilt werden.
Min Cut: Finde einen Schnitt durch den Graphen (d. h. eine Auflistung von zu löschenden Kanten), so daß Anfangs- und Endknoten hinterher unverbunden sind und die summierten Kantengewichte aller gelöschten Kanten minimal wird.
Beispiele
Praktisch
Das Straßenverkehrsnetz eines begrenzten Raums, beispielsweise einer Stadt. Als (ungerichtete) Knoten wählen wir die Gabelungspunkte der Straßen, als Gewichte (hier Kostenmaße) die Länge der Wegstücke. Ein Wegfindungsalgorithmus könnte hierauf Wege minimaler Länge zwischen einzelnen Gabelungspunkten finden.
Verbesserung: Als Gewicht wird nicht die Weglänge zwischen den Gabelungen, sondern die Fahr-/Gehzeit benutzt. Dabei wird es wahrscheinlich passieren, daß zwei Richtungen einer Straße unterschiedlich stark befahren sind. Hier kann man entweder einen Mittelwert aus beiden Richtungen benutzen oder zu einem gerichteten Graphen übergehen. Invarianz des Aufwand/Nutzen-Verhältnisses: Mit steigender Modellgenauigkeit erschwert sich das Modell und die Algorithmen zur Problemlösung.
Computernetzwerke: Knoten sind die einzelnen Rechner, Kanten die Netzwerkverbindungen zwischen ihnen, Kantengewichte die maximale Kapazität einer Verbindung. Auf diesem Modell kann der Max-Flow-Algorithmus einen Weg finden, der eine maximale Durchsatzrate zwischen zwei ausgewählten Knoten im Netzwerk bestimmen kann.
Theoretisch
- Jedes Gitter kann als Graph verstanden werden, bei dem jede Zelle als ein Knoten verstanden wird; Kanten gehen von ihm zu all seinen Nachbarn aus. Da alle Wege gleich lang sind (diagonale Verbindungen vielleicht einmal ausgenommen), können die Kanten ungewichtet bleiben. Werden jetzt einzelne Felder als "unpassierbar" definiert, also aus dem Graphen entfernt, so wird damit Navigation mit Hindernissen modelliert; ein Wegfindungsalgorithmus könnte diese umgehen.
- Ein Graustufen-Bitmap kann ebenfalls als Gitter, also Graph, verstanden werden. Eine Kante werde hoch gewichtet, wenn die durch sie verbundenen Pixel gleiche bzw. sehr ähnliche Helligkeit besitzen, und umso schwächer, je stärker sich die Helligkeiten unterscheiden. Nun wird ein heller Knoten als Anfangs-, ein dunkler als Zielknoten definiert. Eine minimaler Schnitt (min. cut) durch diesen Graphen erzeugt automatisch eine Separation in einen hellen und einen dunklen Bereich.
Vorteile
- schnelle, allgemein verfügbare Algorithmen für o. g. Standardprobleme
Nachteile
- nur auf Gleichgewichtszustand ausgerichtet, nicht ohne weiteres zeitliche Entwicklung modellierbar.
KategorieKnotenUndKanten (bitte diese Kategorie auf alle zum Knoten-und-Kanten-Wiki zugehörigen Seiten setzen)