---

⭐ Maximum Flow — Detailed Explanation

Maximum Flow is a network optimization problem in graph theory.

Given:

• A directed graph ( G = (V, E) )
• A source vertex ( s )
• A sink vertex ( t )
• Each edge has a capacity (maximum allowed flow)

We want to find:

The maximum possible flow from source ( s ) to sink ( t ), without violating capacity or flow conservation.

---

⭐ Key Definitions

1. Capacity

Each edge ( (u, v) ) has capacity:
[
c(u, v) \quad (\text{max flow allowed from } u \to v)
]

---

2. Flow

Actual amount of flow sent on the edge:
[
f(u, v)
]

It must satisfy:
[
0 \le f(u, v) \le c(u, v)
]

---

3. Flow Conservation

For every vertex except source and sink:

[
\sum f(\text{incoming}) = \sum f(\text{outgoing})
]

(flow entering = flow leaving)

---

4. Residual Capacity

Residual capacity tells how much more flow can still be pushed.

[
c_f(u, v) = c(u, v) – f(u, v)
]

Residual graph also includes:

• Forward edges (remaining capacity)
• Reverse edges (to undo previous flow if needed)

---

5. Augmenting Path

A path from source ( s ) to sink ( t ) in the residual graph where all edges have positive residual capacity.

Flow can be increased using this path.

---

⭐ Maximum Flow Algorithms

There are four main algorithms:

1. Ford–Fulkerson Method
2. Edmonds–Karp Algorithm
3. Dinic’s Algorithm
4. Push–Relabel Algorithm

---

———————————————————

1. Ford–Fulkerson Method

———————————————————

A general method to compute max flow using augmenting paths.

Idea

Keep finding augmenting paths and push flow until no more exist.

Steps

1. Start with all flow = 0
2. While there exists an augmenting path:
   • Find bottleneck capacity (minimum capacity along path)
   • Add bottleneck flow to the path
   • Update residual capacities
3. When no augmenting path → flow is maximum

Complexity

Depends on how augmenting paths are chosen.
Worst case (irrational capacities) → no guaranteed termination

---

———————————————————

2. Edmonds–Karp Algorithm

———————————————————

A specific implementation of Ford–Fulkerson.

✔ Chooses shortest augmenting path using BFS

(Shortest in number of edges)

⭐ Guarantees termination.

Time Complexity

[
O(VE^2)
]

Common in textbooks and exams.

---

———————————————————

3. Dinic’s Algorithm (Advanced and Fast)

———————————————————

One of the fastest practical algorithms for max flow.

Idea

Use:

1. Level Graph (constructed using BFS)
2. Blocking Flow (using DFS)

Steps

1. BFS → build level graph (distance from source)
2. DFS → send blocking flow
3. Repeat until no augmenting paths

Complexity

[
O(V^2 E)
]
Much faster in practice than Edmonds–Karp.

---

———————————————————

4. Push–Relabel (Goldberg–Tarjan)

———————————————————

Uses preflows instead of flows.

Operations

• Push (send flow when possible)
• Relabel (increase height to send flow)

Complexity

[
O(V^3)
]

Very efficient for dense graphs.

---

⭐ Max-Flow Min-Cut Theorem (VERY IMPORTANT)**

The maximum flow from source to sink equals the minimum capacity of all s–t cuts in the graph.

This theorem proves the correctness of Ford–Fulkerson and its variants.

Cut:
Partition of vertices into S and T such that:

• ( s \in S )
• ( t \in T )

---

⭐ Example (Conceptual)

Graph:

• s → a (capacity 4)
• s → b (capacity 2)
• a → b (capacity 1)
• a → t (capacity 3)
• b → t (capacity 3)

Possible max flow = 5
(4 through a + 1 through b or other combination)

---

⭐ Applications of Maximum Flow

Maximum Flow is heavily used in:

1. Network Routing

Bandwidth allocation, data flow, routing.

2. Bipartite Matching

Job assignment, pairing problems.

3. Image Segmentation

Computer vision (min-cut).

4. Project Selection & Scheduling

Min-cut gives optimal project set.

5. Sports Tournament Eliminations

Detecting whether a team can still win.

6. Transportation Networks

Road networks, pipelines.

---

⭐ Summary Table

Algorithm	Best For	Complexity
Ford–Fulkerson	Simple, conceptual	Depends
Edmonds–Karp	Guaranteed solution	O(VE²)
Dinic’s Algorithm	Fastest in practice	O(V²E)
Push–Relabel	Dense graphs	O(V³)

---

⭐ Final Summary

Maximum flow determines the greatest flow from source → sink while respecting capacities and conservation.
It uses residual graphs, augmenting paths, and bottlenecks.
Algorithms include:

• Ford–Fulkerson (general idea)
• Edmonds–Karp (BFS, guaranteed termination)
• Dinic’s Algorithm (level graph)
• Push–Relabel (preflow method)

Applications span network routing, bipartite matching, image segmentation, and more.

---