Overview
A cut in a directed network divides its vertices into two disjoint sets, S and T, such that the source belongs to S and the sink belongs to T. The capacity of the cut is the sum of the capacities of all edges directed from S to T. A minimum cut is a cut with the smallest possible capacity among all source-to-sink cuts.
Key concepts
name: Cut; description: A partition of the network's vertices into a source side and a sink side.; name: Cut Capacity; description: The sum of capacities of edges crossing from the source side to the sink side.; name: Minimum Cut; description: A source-to-sink cut having the smallest possible capacity.; name: Cut Edges; description: Edges directed from the source side to the sink side that contribute to the cut capacity.
Mathematical model
objective: Minimize the sum of capacities of edges directed from the source side to the sink side.; constraint: The source must remain on one side and the sink on the other.; importantNote: For directed graphs, only edges directed from the source side to the sink side contribute to the cut capacity.
Complexity
usingEdmondsKarp: O(V × E²) for the maximum-flow computation, followed by O(V + E) for the residual reachability search.; additionalSpace: O(V + E) for graph and search structures.
Example
scenario: A communication network connects a server to a destination through several routers.; description: Each connection has a maximum capacity. A cut separates the server from the destination by dividing the routers into two groups.; interpretation: The capacity of the cut is the combined capacity of all connections crossing from the server's group to the destination's group.; goal: Find the cut with the smallest total capacity, which identifies a minimum-capacity separation of the network.
Applications
Identifying bottlenecks in transportation networks.; Measuring communication network vulnerability.; Image segmentation and computer vision.; Clustering and graph partitioning.; Supply chain analysis.; Reliability and infrastructure planning.
Limitations
A minimum cut identifies a low-capacity separation but does not automatically model every real-world failure scenario.; The result depends on the accuracy of the edge-capacity model.; Some applications require multiple-terminal cuts or other variants rather than a single source-to-sink cut.; A minimum cut based only on capacity may not capture cost, reliability, or fairness considerations.