Max_Flow.md

Max Flow

We consider connected graphs that are weighted and undirected, with two distinguished vertices:

• the source usually called s
• the sink usually called t

The weights are positive.

Table of Content

• Definitions
• Flow in a graph
  • Settings
    • Correct Flow
    • Incorrect Flow
  • Conditions
• Ford-Fulkerson algorithm
  • Complexity
  • Residual network
  • Improving path
  • Pseudo code
  • Examples with steps
    • Steps
  • Improvement of the Pseudo Code - Edmond-Karp Algo
    • Complexity:
• Minimum Cut in a graph
  • Minimum cut
    • The maximum flow and its residual graph
    • The minimum cut discriminated

Definitions

• Connected graph: A connected graph is graph that is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph

• Undirected: An edge can be traversed in both ways

• Source: Starting point of the flow

• Sink: Ending point of the flow

• Network: Other name of a graph

• Capacity: Weight of an edge

• Pipes: Other name for edge

• Value: The value of a flow f in a graph is the quantity outgoing from s, which is equal to the quantity incoming to t

• Improving path: An improving path in a network is a path from s to t. Its minValue is the minimum weight of its edges.

Flow in a graph

Settings

• the water/data can go either way in an edge
• it cannot exceed the capacity of the edge
• except for s and t, the incoming flow must be equal to the outgoing flow. Only outgoing from s, only incoming to t

Correct Flow

This is a correct flow passing through the graph

Incorrect Flow

This is an incorrect flow passing through the graph

Conditions

Let $C(x—y)$ denote the capacity of the edge $x—y$:

• Antisymmetry: $f(x → y) = −f(y → x)$: Meaning that a flow going from x to y with flow of 3, means there is a negative flow of -3 going from y to x;
• Capacity: $−C(x – y) ≤ f(x → y) ≤ C(x – y)$: By the previous conditions ;
• flow conservation: $\Sigma y∈V f(x → y) = 0$, for $x \neq s$ and $x \neq t$.
• Outgoing flow are positive, and incoming ones are negative

Ford-Fulkerson algorithm

The Ford-Fulkerson algorithm allow to find the maximal flow in a network. Take note that there may be one solution among many others. The result is not always the same.

Complexity

The complexity is hard to express as it depends on the result and on the minValue

Residual network

The residual network of a network allows a different representation of the flow, it depict to us how the flow can be directed to find augmented path.

With an edge x—y, you can materialize the residual graph by creating 2 edges with their own weight

• x→y: weight = C(x—y) - f(x→y)
• y→x: weight = C(x—y) - f(y→x)

• The flow $x—y$ weight 2 is changed to 1. It represent the flow that can pass through x to y
  • $f(x → y) = 2 ⇒ x — 1 → y, as C(x – y) − f(x → y) = 3 − 2 = 1$
• The flow $y—x$ weight -2 is changed to 5. It represent the flow that can pass through y to x as you can remove 2 from the actual flow going from x to y and add 3
  • $f(y → x) = −2 ⇒ y — 5 → x, as C(y – x) − f(y → x) = 3 − (−2) = 5$

Example:

Improving path

Let Gf be the residual network associated to the flow f

2 Theorems:

• If there is no improving path, then f is a maximum flow
• If there is an improving path P of minValue λ, then adding λ to every edge of P results in a flow, whose value is increased by λ

Example:

Pseudo code

def FordFulkerson(G, s, p):
    f = null flow (0 for all edge)
    while there is an improving path do :
        P = improving path of Gf
        λ = minvalue of P
        update f by adding λ on edges in P
    return f

Examples with steps

Steps

Theses steps is giving you the idea. Every times, you find a path, you take the minValue of the path, and you update the graph

Between every steps, you create a new residual network

Improvement of the Pseudo Code - Edmond-Karp Algo

Edmonds-Karp algorithm is an improvement on Ford-Fulkerson, where the improving path is computed using a BFS

def EdmondKarp(G, s, p):
    f = null flow (0 for all edge)
    while there is an improving path do :
        P = improving path of Gf with a BFS
        λ = minvalue of P
        update f by adding λ on edges in P
    return f

Complexity:

The complexity of Edmond Karp alogithm has a complexity of $O(|V| × |E|^2)$

Minimum Cut in a graph

In the same settings, a cut in a graph is a collection of edges whose removal disconnect s from t

Minimum cut

The minimum cut is the cut that minimizes the sum of the weights

Theorem: value of the minimum cut = value of the maximum flow

To find the minimum cut, nothing more easy !

Take the residual network of the maximum flow, and take every edges that separated them

The maximum flow and its residual graph

The minimum cut discriminated