Maximum Flow

Definition

• The capacity constrain indicate that a given capacity must not be exceed by the flow from one vertex to another.
• The skew symmetry (a notational convenience) indicate that the flow from vertex to vertex is the negative of the flow in the reverse direction.
• The flow-conservation property indicate that the total flow out of a vertex other than the source or sink is 0
• The total positive flow leaving a vertex is defined symmetrically
• The total positive flow leaving the vertex minus the total positive flow entering a vertex is the  total net-flow at a vertex
• The total positive flow entering a vertex other than the source or sink must be equal to the positive flow leaving that vertex.

Examples

• The Ford-Fulkerson Method
• The Edmonds-Karp Algorithm

© 2015, Alejandro G. Carlstein Ramos Mejia. All rights reserved.