Digraph.max_flow

zur Berechnung eines maximalen Flusses

q r s u t

Funktionsübersicht

.random .complete .plot .degree .degree_in .degree_out .incidence_matrix .adjacency_matrix .is_simple .is_connected .shortest_path .distance .max_flow

Beschreibung

Die Funktion besitzt folgende Argumente:

E	Kantenmenge als -Matrix
a	Index des Startknotens (Quelle)
b	Index des Zielknotens (Senke)
w	Gewichtung der Kanten als -Vektor (optional)

Es wird ein maximaler Fluss von nach bestimmt. Falls keine Gewichtung der Kanten übergeben wird, werden alle Kantengewichte gleich 1 gesetzt.

Zurückgegeben werden folgende Daten, welchen den maximalen Fluss repräsentieren:

E	Kantenmenge als Matrix
w	Gewichtung der Kanten als Vektor

Beispiel

Im folgenden Beispiel wird ein zufälliger Graph mit 5 Knoten erzeugt. Anschließend wird ein maximaler Fluss von Knoten 0 zu Knoten 4 berechnet, welcher die Gewichtung der Kanten berücksichtigt. Die Ergebnisse werden graphisch dargestellt.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot1" style="display:inline-block;"></div>
<div id="plot2" style="display:inline-block;"></div>
<script>

var G = Digraph.random(5);
var F = Digraph.max_flow(G.E, 0, 4, G.w);

Digraph.plot("plot1", G.E, G.w, "large", 300);
Digraph.plot("plot2", F.E, F.w, "large", 300);

</script>
</body>
</html>

Vorschau aktualisieren

Impressum und Kontakt

Datenschutzerklärung

Rechtliche Hinweise