Minimum Cut
You've mastered max flow. Now learn minimum cuts: the cheapest way to disconnect source from sink.
Lessons
1. Intro
(Splitting networks)
2. What is a Cut?
(Partitioning vertices)
3. Cut Capacity
(Sum of crossing edges)
4. s-t Cut
(Source and sink separation)
5. Minimum s-t Cut
(Cheapest way to disconnect)
6. Max-Flow Min-Cut Theorem
(Flow equals cut capacity)
7. Theorem Intuition
(Why flow equals cut)
8. Quiz: Max-Flow Min-Cut Relationship
Knowledge check
9. Finding the Min Cut
Using max flow residual graph
10. Algorithm - Find Min Cut
(Step by step)
11. Why Residual Graph Works
(No augmenting paths left)
12. Example - Finding Min Cut
(Small network)
13. Quiz: Finding Cut Edges
Knowledge check
14. Global Minimum Cut
(No source or sink)
15. Stoer-Wagner Algorithm
(Finding global min cut)
16. Edge Connectivity
(Minimum edges to disconnect)
17. Vertex Connectivity
Minimum vertices to disconnect
18. Application - Network Reliability
(Finding weak points)
19. Application - Image Segmentation
(Foreground and background)
20. Application - Clustering
(Splitting data into groups)
21. Quiz: Stoer-Wagner Algorithm
Knowledge check
22. Problem - Police Chase
(CSES 1695)
23. Problem - Police Chase - Read Statement
(CSES 1695)
24. Core Idea - Max Flow with Unit Capacities
(Flow equals number of roads)
25. Core Idea - Extracting the Cut Edges
(Which roads to block)
26. Handling Bidirectional Roads
(Each road becomes two edges)
27. Implementation - Police Chase
(Pseudocode)
28. Implementation - Police Chase - Implement Solution
(CSES 1695)
29. Lessons - Min Cut Applications
(Real-world uses)
30. Quiz: Vertex vs Edge Connectivity
Knowledge check
31. Problem - Distinct Routes
(CSES 1711)
32. Problem - Distinct Routes - Read Statement
(CSES 1711)
33. Core Idea - Max Flow Equals Path Count
(Edge-disjoint paths)
34. Core Idea - Flow Decomposition
(Extracting paths from flow)
35. Algorithm - Path Decomposition
(Trace and subtract)
36. Implementation - Distinct Routes
(Pseudocode)
37. Implementation - Distinct Routes - Implement Solution
(CSES 1711)
38. Lessons - Flow Decomposition
(Paths from flow)
39. Problem - Network Segmentation
(Custom problem)
40. Core Idea - Try All Pairs
(Brute force approach)
41. Core Idea - Stoer-Wagner Basics
(Contracting vertices)
42. Maximum Adjacency Ordering
(Picking vertices to cut)
43. Algorithm - Stoer-Wagner
(Step by step)
44. Quiz: Maximum Adjacency Ordering
Knowledge check
45. Implementation - Network Segmentation
(Pseudocode for Stoer-Wagner)
46. Lessons - Global vs Local Cuts
(Different problem types)
47. Section Recap
(What you learned)