Network Flows: Max-Flow Min-Cut, Algorithms & Applications

Key Concepts & Definitions

1. Network Flow Basics

A network flow is a directed graph $G=(V,E)$ with:

• A source node $s$ (start point).
• A sink node $t$ (end point).
• Edges with capacities $c(u,v)$ (max flow allowed).
• A flow function $f(u,v)$ where $0\le f(u,v)\le c(u,v)$.

Flow Conservation Constraint: For any node $v\ne s,t$: $$\sum _{u}f(u,v)=\sum _{w}f(v,w)$$ (Flow in = Flow out)

2. Types of Edges

3. Max-Flow Min-Cut Theorem

• Max-Flow: The maximum possible flow from $s$ to $t$.
• Cut: Partition of nodes into $(S,T)$ where $s\in S$ and $t\in T$.
• Capacity of a Cut: $$c(S,T)=\sum _{u\in S,v\in T}c(u,v)$$
• Theorem: The max flow equals the min cut capacity.

Example: Consider a graph with:

• $s\to A$ (capacity 3)
• $s\to B$ (capacity 2)
• $A\to t$ (capacity 2)
• $B\to t$ (capacity 3)

Possible Cuts:

1. $S=\{s,A\},T=\{B,t\}$ $c(S,T)=c(A,t)+c(s,B)=2+2=4$
2. $S=\{s\},T=\{A,B,t\}$ $c(S,T)=c(s,A)+c(s,B)=3+2=5$

Min Cut: $(S,T)=(\{s,A\},\{B,t\})$ with capacity 4. Max Flow: Also 4 (verified via Ford-Fulkerson).

---

4. Ford-Fulkerson Algorithm

Steps:

1. Start with $f(u,v)=0$ for all edges.
2. Find an augmenting path $P$ from $s$ to $t$ in the residual graph $G_f$.
3. Bottleneck Capacity: $\min \{c(u,v)-f(u,v)\mid (u,v)\in P\}$.
4. Update Flow: Increase $f$ along $P$ by the bottleneck.
5. Repeat until no augmenting path exists.

Residual Graph $G_f$:

• Forward Edge: $(u,v)$ with residual capacity $c(u,v)-f(u,v)$.
• Backward Edge: $(v,u)$ with residual capacity $f(u,v)$.

Example: Given:

s --3--> A --2--> t
|       |
2       3
|       |
v       v
B --3--> t

Step 1: Augmenting path $s\to A\to t$, bottleneck = 2. Update:

• $f(s,A)=2$, $f(A,t)=2$. Step 2: Augmenting path $s\to B\to t$, bottleneck = 3. Update:
• $f(s,B)=3$, $f(B,t)=3$. Max Flow: $2+3=5$.

---

5. Applications of Network Flows

---

6. Solved Problems (Exam-Style)

Problem 1: Max Flow Calculation

Given:

s --4--> A --3--> t
|       |
2       1
|       |
v       v
B --2--> t

Solution:

1. Augment $s\to A\to t$: bottleneck = 3. Flow: $f(s,A)=3$, $f(A,t)=3$.
2. Augment $s\to B\to t$: bottleneck = 2. Flow: $f(s,B)=2$, $f(B,t)=2$.
3. Max Flow: $3+2=5$.

Problem 2: Min Cut Verification

For the above graph, find the min cut. Possible Cuts:

1. $S=\{s,A,B\},T=\{t\}$: $c(S,T)=3+2=5$.
2. $S=\{s,A\},T=\{B,t\}$: $c(S,T)=2+1=3$. Min Cut: $(\{s,A\},\{B,t\})$ with capacity 3 (but max flow was 5—error!). Correction: The correct min cut is $(\{s,A,B\},\{t\})$ with capacity 5, matching max flow.

---

7. Common Mistakes & Clarifications

• Residual Graph Misuse: Forgetting to include backward edges in $G_f$.
• Flow Conservation: Ignoring intermediate nodes (only $s$ and $t$ can have imbalance).
• Bottleneck Calculation: Must consider all edges in the augmenting path.
• Min Cut vs. Max Flow: Always verify that the min cut equals the computed max flow.

---

Exam Tip

1. Understand Definitions:

   • Memorize saturated edge, unsaturated edge, and slack.
   • Know max-flow min-cut theorem and its proof intuition.

2. Algorithm Steps:

   • For Ford-Fulkerson, trace augmenting paths carefully.
   • Draw the residual graph at each step.

3. Problem-Solving Strategy:

   • Start with simple augmenting paths (e.g., shortest path first).
   • For min cut, consider all possible partitions of $(S,T)$.

4. Applications:

   • Relate to real-world scenarios (e.g., "This is like optimizing traffic routes").
   • For matching problems, model as a flow network with capacity 1.

5. Diagrams:

   • Always draw the graph before solving.
   • Label flows and capacities clearly.

6. Common Exam Questions:

   • "Find the max flow" → Use Ford-Fulkerson.
   • "Prove max-flow = min-cut" → Use the theorem directly.
   • "Define saturated edge" → $f(u,v)=c(u,v)$.

---

Practice Questions:

1. Given a network, find the max flow and verify with min cut.
2. Explain how network flows solve the assignment problem.
3. What happens if an edge has zero capacity? How does it affect the flow?