taramath
Maximale Flüsse
in gerichteten Graphen
Beschreibung
In diesem Anwendungsbeispiel soll demonstriert werden, wie ein maximaler Flüss zwischen zwei Knoten eines gerichteten Graphen berechnet werden kann. Zudem wird eine Möglichkeit zur Veranschaulichung des Ergebnisses vorgestellt.
Beispiel 1
Im folgenden Beispiel wird ein gerichteter Graph definiert sowie ein maximaler Fluss von Knoten 0 nach Knoten 11 berechnet. Die Gewichtung der Kanten wird dabei aus der jeweiligen Länge der Kanten bestimmt und auf einen ganzzahligen Wert gerundet. Anschließend wird das Ergebnis entsprechend graphisch dargestellt: Kantengewichte sind in den schwarzen Rechtecken und der Fluss ist in den blauen Rechtecken zu sehen. Vorschau aktualisieren