Flow Graph- Max Flow and Min Cut

 

Flow Graph (Network Flow Graph)

A flow graph (in algorithms) is a directed graph used to model movement of some quantity such as:

• water in pipes

• traffic in roads

• data in networks

• resources in supply chains

Each edge has a capacity = maximum amount that can pass through it.

---

🟦 Components of a Flow Graph

A flow network consists of:

🔹 Vertices (Nodes)

Represent locations (cities, routers, tanks, etc.)

🔹 Directed Edges

Show allowed direction of flow.

🔹 Capacity ${𝑢}_{𝑒}$

Maximum flow allowed on each edge.

🔹 Source $𝑠$

Starting node where flow originates.

🔹 Sink $𝑡$

Destination node where flow ends.

---

🟦 What is a Flow?

A flow assigns a number ${𝑓}_{𝑒}$ to each edge such that:

✅ Capacity constraint

$$0\le {𝑓}_{𝑒}\le {𝑢}_{𝑒}$$

✅ Conservation constraint

At every node except source and sink:

$$\text{incoming flow}=\text{outgoing flow}$$

---

🟦 Goal

Compute the maximum total flow from source $𝑠$ to sink $𝑡$.

As your uploaded notes explain:

• Flow must respect capacities

• Total flow leaving $𝑠$ equals total flow entering $𝑡$
  

---

✅ 2. Maximum Flow Problem

🟦 Problem Definition

Given:

• directed graph $𝐺(𝑉,𝐸)$
  

• source $𝑠$
  

• sink $𝑡$
  

• capacity ${𝑢}_{𝑒}$ on each edge

Find:

$$\mathbf{\text{Maximum}}\mathbf{\text{possible}}\mathbf{\text{flow}}\mathbf{\text{from}}𝑠\to 𝑡$$

---

🟦 Intuition Example

✅ Naive Greedy Algorithm for Maximum Flow

🟦 Idea (Intuition)

• Start with zero flow

• Repeatedly find any path from source $𝑠$ to sink $𝑡$
  where all edges still have remaining capacity

• Push as much flow as possible along that path

• Stop when no such path exists

This is a greedy approach because it:

• chooses one available path at a time

• sends maximum possible flow immediately

• never revises earlier decisions

---

✅ Algorithm (Clean Pseudocode Version)

Naive Greedy Max-Flow Algorithm

Initialize flow f(e) = 0 for every edge e in E

Repeat:
    Find an s–t path P such that for every edge e in P:
        f(e) < capacity(e)

    If no such path exists:
        STOP and return current flow

    Let Δ = minimum remaining capacity on path P
           = min over e in P of (capacity(e) − f(e))

    For each edge e in P:
        Increase f(e) by Δ

---

✅ Why This Algorithm is “Naive”

• It may terminate with non-maximum flow

• Because earlier choices might block better routes later

• It cannot undo previous flow decisions

This motivates:

👉 Residual graphs
👉 Ford–Fulkerson algorithm

---

✅ Example Showing Failure

If the algorithm first chooses a bad path:

s → v → w → t

it may saturate edges incorrectly and prevent a better total flow.

The algorithm terminates at this point with a  flow with value 3. We already know that the maximum 

flow value is 5, and we conclude that the naive greedy algorithm can terminate with a non-maximum 

flow. This leads to Residual Graph

✅ Residual Graph (Key Idea)

To improve a flow, we build a residual network:

• forward edge capacity = remaining space ${𝑢}_{𝑒}-{𝑓}_{𝑒}$

• backward edge capacity = current flow ${𝑓}_{𝑒}$

This allows:

• sending more flow

• undoing earlier decisions

This idea leads to the Ford–Fulkerson algorithm.

---

✅  Ford–Fulkerson Algorithm (Core Algorithm)

Steps:

1. Start with zero flow

2. Find path from $𝑠$ to $𝑡$ with available capacity

3. Push maximum possible flow along path

4. Update residual graph

5. Repeat until no path exists

When no path exists → flow is maximum.

Finding the Maximum Flow Path through the Graph

Instead of using a depth-first search, you can use a modification of Dijkstra's algorithm to find the path through the residual that has the maximum flow. When processing a node, Dijkstra's algorithm traverses the node's edges, and if shorter paths to any other nodes is discovered, the nodes are updated. At each step, the node with the shortest known path is processed next.

The modification works as follows. When processing a node, again the algorithm traverses the node's edges, and if paths with more flow to any other nodes are discovered, then the nodes are updated. At each step, the node with the maximum flow is processed next.

We'll work an example now: The source is A an the sink is G:

The first path we get is A->B->C->E->G with a flow of one. In the residual, the edges whose flow is reduced are colored red, and the reverse edges are colored green:

The next greedy path through the residual is A->B->C->D->F->G, with a flow of two:

The last path is A->D->F->G with a flow of three. Here are the final flow and residual graphs:

The Max Flow is - 1 + 2 + 3 = 6

---

✅  Important Theorem

🔹 Max-Flow Min-Cut Theorem

$$\text{Maximum flow}=\text{Minimum cut capacity}$$

Meaning:

The largest flow equals the smallest bottleneck separating $𝑠$ and $𝑡$.

This is one of the most important results in algorithms.

We can use the final residual graph to find the min cut.

First, you find all nodes reachable from the source in the residual graph. This is one set of nodes, which we color purple below:

Now, in the original graph, we divide our nodes into two sets: the set determined above, and all of the remaining nodes. They are drawn purple and yellow in the original graph below:

The minimum cut is composed of all the edges that go from the source set to the sink set. These are edges AD, CD and EG, which is drawn in red above. The sum of their capacities equals the maximum flow of six.

---

✅ Applications of Maximum Flow

🟦 Networks

• Internet packet routing

• Bandwidth allocation

🟦 Transportation

• Traffic flow optimization

• Railway scheduling

🟦 Supply Chain

• Goods distribution

• Logistics planning

🟦 Image Processing

• Image segmentation (cutting object from background)

🟦 Matching Problems

• Job assignment

• Student–course allocation

🟦 Machine Learning

• Graph cuts in computer vision

• Energy minimization problems

Summary

A flow graph or flow network is a directed graph where each edge has a capacity representing the maximum allowable flow. It includes a source node s and a sink node t. A feasible flow must satisfy capacity constraints and flow conservation at intermediate nodes.

The maximum flow problem asks for the greatest possible amount of flow that can be sent from the source to the sink. Algorithms such as Ford–Fulkerson repeatedly find augmenting paths in the residual graph and increase the flow until no more such paths exist. The Max-Flow Min-Cut theorem states that the maximum flow equals the minimum cut capacity.

Applications include traffic routing, communication networks, bipartite matching, logistics optimization, and image segmentation.