|
GraphTheory[MaxFlow]
|
|
Calling Sequence
|
|
MaxFlow(G, s, t)
|
|
|
Parameters
|
|
|
G
|
-
|
weighted graph
|
|
s
|
-
|
vertex of the graph (source)
|
|
t
|
-
|
vertex of the graph (sink)
|
|
|
|
|
|
Description
|
|
|
•
|
The MaxFlow command returns the optimal value for the max flow problem along with an optimal flow (as a Matrix).
|
|
•
|
The algorithm used is the Push-Relabel (Push-Preflow) algorithm of Goldberg et al. (see Introduction to Algorithms, Cormen, Leiserson, Rivest, 2nd edition). The complexity is  where n=|V| is the number of vertices of G and m=|E| is the number of edges.
|
|
|
|
Examples
|
|
|
>
|
|
|
>
|
![A := Matrix([[0, 1, 0, 4, 0, 0], [0, 0, 1, 0, 3, 0], [0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 1, 0], [0, 0, 0, 1, 0, 4], [0, 0, 0, 0, 0, 0]])](/support/helpjp/helpview.aspx?si=6098/file01852/math82.png)
|
|
![A := Matrix([[0, 1, 0, 4, 0, 0], [0, 0, 1, 0, 3, 0], [0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 1, 0], [0, 0, 0, 1, 0, 4], [0, 0, 0, 0, 0, 0]])](/support/helpjp/helpview.aspx?si=6098/file01852/math85.png)
| (1) |
|
>
|
|
|
| (2) |
|
>
|
|
|
| (3) |
|
>
|
|
|
>
|
|
|
![4, Matrix([[0, 1, 0, 3, 0, 0], [0, 0, 0, 0, 2, 0], [0, 1, 0, 0, 0, 1], [0, 0, 2, 0, 1, 0], [0, 0, 0, 0, 0, 3], [0, 0, 0, 0, 0, 0]])](/support/helpjp/helpview.aspx?si=6098/file01852/math115.png)
| (4) |
|
|
Download Help Document
Was this information helpful?
