Network Flow
A whole class you haven't touched: flow networks. Learn Ford-Fulkerson and maximum flow.
Lessons
1. Intro
(Why flow matters)
2. Flow Networks
Directed graph with capacities
3. Flow Assignment
(How much flow on each edge)
4. Example Flow
(Simple network walkthrough)
5. The Max Flow Problem
(Find maximum throughput)
6. Residual Graph
(Captures remaining capacity)
7. Augmenting Path
(Path that increases flow)
8. Quiz: Residual Graph
Knowledge check
9. Ford-Fulkerson Method
Iterative augmentation fram...
10. Why It Works
(Correctness argument)
11. Edmonds-Karp Algorithm
BFS for shortest augmenting...
12. Pseudocode - Edmonds-Karp
(BFS-based max flow)
13. Residual Capacity Update
(Forward and backward edges)
14. Implementation Details
Adjacency list with capacities
15. Time Complexity
(Edmonds-Karp analysis)
16. Quiz: Edmonds-Karp Complexity
Knowledge check
17. Problem - Download Speed
(CSES 1694)
18. Download Speed - Modeling
(Direct translation to flow)
19. Download Speed - Implementation
(Edmonds-Karp code)
20. Download Speed - Walkthrough
(Example with 4 nodes)
21. Download Speed - Edge Cases
(No path, single edge)
22. Cuts and Capacity
(Partitioning the graph)
23. Min-Cut
(Cut with minimum capacity)
24. Max-Flow Min-Cut Theorem
(Duality result)
25. Finding the Min-Cut
Run BFS on final residual g...
26. Quiz: Max-Flow Min-Cut Theorem
Knowledge check
27. Problem - Police Chase
(CSES 1695)
28. Police Chase - Core Idea
Unit capacities mean edge-d...
29. Police Chase - Extracting the Cut
(BFS on residual graph)
30. Police Chase - Implementation
Edmonds-Karp + cut extraction
31. Police Chase - Walkthrough
(Example with 4 cities)
32. Bipartite Matching
(Classic flow application)
33. Problem - School Dance
(CSES 1696)
34. School Dance - Graph Construction
(Source and sink setup)
35. School Dance - Extracting Pairs
(Check flow on middle edges)
36. School Dance - Implementation
(Bipartite matching via flow)
37. School Dance - Walkthrough
(Example with 3 boys, 2 girls)
38. School Dance - Edge Cases
(Unbalanced sides, no edges)
39. Quiz: Bipartite Matching via Flow
Knowledge check
40. Multiple Sources and Sinks
Reduction to single source/...
41. Vertex Capacities
(Split nodes into in/out)
42. Flow with Lower Bounds
Forcing minimum flow on edges
43. Integer Flow Theorem
Integral capacities yield i...
44. Disjoint Paths
(Counting independent routes)
45. When to Use Flow
(Recognizing flow problems)
46. Common Mistakes
(What to avoid)
47. Quiz: Node Capacity Modeling
Knowledge check
48. Faster Algorithms
(Beyond Edmonds-Karp)
49. Flow in Practice
(Real-world applications)
50. Vocabulary - Augmenting Path
(Path that increases flow)
51. Vocabulary - Residual Graph
Remaining capacities after ...
52. Vocabulary - Cut
Partition separating source...
53. Practice Tips
(How to get good at flow)
54. Section Recap
(What you learned)