Maximum Flow
What is a Maximum Flow in a graph?
Let G be a directed graph, s and t
nodes of G, and cap a non-negative function
on the edges of G. For an edge e of G
cap(e) is called the capacity of e. A
flow from s to t must satisfy the capacity
constraints, i.e., the flow over an edge must not exceed its capacity,
and the flow conservation constraints, i.e., the flow out of s
must be the same as the flow into t. In a maximum flow
the flow out of s is maximum among all flows from s to t.
Intuition: We think of the graph as a flow network. Material is
coursing through the system from a source s, where the material
is produced, to a sink t, where the material is consumed.
Each directed edge is a conduit for the material and each conduit has
a stated capacity. The maximum flow problem then asks for the greatest
rate at which material can be shipped from the source to the sink without
violating the capacity constraints.
LEDA Functions for Maximum Flow
|
See also:
Graph Algorithms
Graphs and Related Data Types
Minimum Cost Flow
Minimum Cut
Manual Entries:
Maximum Flow
|