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

• Maximum Flow Algorithms
• Checking the Result of Maximum Flow Algorithms
• Generators for Maximum Flow Problems: See the Manual Page of Maximum Flow for a list of available generators.

See also:

Graph Algorithms

Graphs and Related Data Types

Minimum Cost Flow

Minimum Cut

Manual Entries:

Maximum Flow