GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/MaxFlow

GraphTheory

  

MaxFlow

 

Calling Sequence

Parameters

Description

Examples

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 On2m where n=|V| is the number of vertices of G and m=|E| is the number of edges.

Examples

withGraphTheory:

AMatrix0,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

A010400001030010001003010000104000000

(1)

NDigraphA,weighted

NGraph 1: a directed weighted graph with 6 vertices and 10 arc(s)

(2)

IsNetworkN

1,6

(3)

DrawNetworkN

MaxFlowN,1,6

4,010300000020010001002010000003000000

(4)

See Also

FlowPolynomial

IsCutSet

IsNetwork

WeightMatrix