Find Min Cut In Graph Online Calculator

Calculate Minimum Cut

Enter the graph details to find the min s-t cut using the max-flow min-cut theorem.

What is a Min Cut in a Graph?

A min cut in a graph, specifically an s-t cut, is a partition of the vertices of a flow network (a graph with capacities on its edges, a source ‘s’, and a sink ‘t’) into two disjoint sets, S and T, such that the source ‘s’ is in S and the sink ‘t’ is in T. The capacity of the s-t cut (S, T) is the sum of the capacities of all edges that have their start vertex in S and their end vertex in T.

The min cut in a graph is the s-t cut whose capacity is minimum among all possible s-t cuts. Finding the min cut in a graph is a fundamental problem in graph theory and network flow analysis, with applications in network reliability, image segmentation, and clustering.

The famous Max-Flow Min-Cut theorem states that the maximum flow that can be sent from the source ‘s’ to the sink ‘t’ in a network is exactly equal to the minimum capacity of an s-t cut. This theorem provides a powerful way to find the min cut in a graph by solving the max flow problem.

Who should use it?

Network engineers, computer scientists, operations researchers, and anyone dealing with network flow, connectivity, or partitioning problems can use a min cut in graph online calculator. It helps analyze network bottlenecks, identify critical connections, and understand the robustness of a network.

Common misconceptions

A common misconception is that the min cut always involves the edges with the smallest capacities. While edges with small capacities are often part of the min cut, it’s the sum of capacities of edges going from S to T that matters, and the partition (S, T) is determined by the max flow.

Min Cut in Graph Formula and Mathematical Explanation

The min cut in a graph is found using the Max-Flow Min-Cut Theorem. We first find the maximum flow from the source ‘s’ to the sink ‘t’ using an algorithm like Edmonds-Karp or Dinic’s.

The Edmonds-Karp algorithm works as follows:

1. Initialize flow to 0.
2. While there exists an augmenting path from ‘s’ to ‘t’ in the residual graph:
1. Find an augmenting path using Breadth-First Search (BFS) on the residual graph (edges with remaining capacity).
2. Determine the bottleneck capacity (minimum residual capacity) along this path.
3. Increase the flow along this path by the bottleneck capacity. Update the residual graph (decrease capacity on forward edges, increase on backward edges).
3. The max flow is the accumulated flow, and this value is equal to the capacity of the min cut in a graph.

After the max flow is found, the residual graph has no more augmenting paths from s to t. To find the min cut set (S, T):

• Find all vertices reachable from ‘s’ in the final residual graph using only edges with positive residual capacity. These form the set S.
• All other vertices form the set T (including ‘t’).
• The min cut in a graph consists of all original edges (u, v) such that u is in S and v is in T.

Variables Table

Variable	Meaning	Unit	Typical range
N	Number of vertices	–	2 to ~100 (for this calculator)
u, v	Vertices (nodes)	–	1 to N
c(u,v)	Capacity of edge (u,v)	Flow units	0 to large numbers
s	Source vertex	–	1 to N
t	Sink vertex	–	1 to N (t != s)
f(u,v)	Flow through edge (u,v)	Flow units	0 to c(u,v)
cf(u,v)	Residual capacity of (u,v)	Flow units	0 to c(u,v) + f(v,u)

Table of variables used in min cut and max flow calculations.

Practical Examples (Real-World Use Cases)

Example 1: Network Bottleneck

Consider a communication network represented as a graph, where vertices are routers/servers, and edge capacities are bandwidths. We want to find the bottleneck between a source server ‘s’ and a destination server ‘t’.

Vertices: 4, Edges: 1-2(20), 1-3(10), 2-3(5), 2-4(10), 3-4(20), Source=1, Sink=4.
Using the calculator with input:
N=4
Edges:
1,2,20
1,3,10
2,3,5
2,4,10
3,4,20
s=1, t=4

The calculator would find the max flow (and thus min cut) to be 25. The min cut edges might be (1,3) and (2,4) or another combination summing to 25, indicating the critical links limiting flow.

Example 2: Image Segmentation

In image segmentation, a graph can be constructed where pixels are nodes, and edges connect adjacent pixels with capacities based on similarity. A source ‘s’ is linked to foreground seed pixels, and a sink ‘t’ to background seeds. Finding the min cut in this graph separates the foreground from the background.

If we have a small 2×2 image forming vertices 1(top-left), 2(top-right), 3(bottom-left), 4(bottom-right), with s=1, t=4, and edge capacities representing dissimilarity, the min cut separates the most dissimilar regions connected to s and t.

How to Use This Min Cut in Graph Online Calculator

1. Enter Number of Vertices (N): Input the total count of vertices in your graph.
2. Enter Edges and Capacities: In the textarea, list each directed edge with its capacity, one per line, in the format `u,v,c` (from u to v with capacity c). For undirected edges, enter two directed edges: `u,v,c` and `v,u,c`.
3. Enter Source (s) and Sink (t): Specify the start and end vertices for the flow/cut analysis. Ensure s and t are between 1 and N and are different.
4. Calculate: Click “Calculate Min Cut”. The calculator will find the max flow and identify the min cut.
5. Read Results: The “Primary Result” shows the min cut value (equal to max flow). “Intermediate Results” show the max flow, the edges forming the min cut (from source-side to sink-side), vertices on the source side, and the number of augmentations.
6. Chart: The chart visualizes the flow added in each augmentation step of the Edmonds-Karp algorithm.

The min cut in graph online calculator helps identify the bottleneck capacity between the source and sink.

Key Factors That Affect Min Cut Results

• Edge Capacities: Higher capacities generally lead to a higher min cut value. Edges with low capacities are more likely to be part of the min cut.
• Graph Topology: The way vertices are connected significantly impacts the possible paths and cuts. Dense graphs might have larger min cuts than sparse ones with similar capacities.
• Choice of Source and Sink: The min cut in a graph is specific to the chosen ‘s’ and ‘t’. Different s-t pairs in the same graph can have different min cut values.
• Number of Edges: More edges can mean more paths and potentially a larger max flow/min cut, but it depends on their capacities and connections.
• Direction of Edges: For directed graphs, the direction matters. An edge u->v contributes to the cut (S,T) if u is in S and v is in T, but v->u does not.
• Presence of Bottlenecks: If the graph has clear “choke points” with low total capacity connecting two parts, these will likely define the min cut in the graph.

Frequently Asked Questions (FAQ)

What is the Max-Flow Min-Cut Theorem?

It states that in any flow network, the maximum flow from a source ‘s’ to a sink ‘t’ is equal to the minimum capacity of an s-t cut (the min cut in the graph).

How do I represent an undirected edge?

Represent an undirected edge between u and v with capacity c as two directed edges: u,v,c and v,u,c.

What if there is no path from s to t?

If there’s no path from s to t, the max flow and min cut value will be 0.

Can edge capacities be zero?

Yes, a capacity of zero means no flow can pass through that edge directly.

Is the min cut unique?

The value of the min cut in a graph is unique, but the set of edges forming the min cut may not be unique.

What algorithm does this calculator use?

This calculator uses the Edmonds-Karp algorithm, which finds augmenting paths using BFS in the residual graph to calculate max flow, and then identifies the min cut.

What are the limitations of this calculator?

It’s designed for relatively small graphs due to browser limitations. For very large graphs, more optimized algorithms and dedicated software are needed.

How do I find the vertices on each side of the cut?

The calculator lists the “Vertices on Source Side of Cut”. These are vertices reachable from ‘s’ in the final residual graph. The remaining vertices (including ‘t’) are on the other side.