___________ is a partition of the vertices of a graph in two disjoint subsets that are joined by atleast one edge.

In graph theory, a minimum cut (or min-cut) is a partition of a graph's vertices into two disjoint subsets. A minimum cut is minimal in some metric. For example, in a flow network, the minimum cut separates the source and sink vertices. The weight of this cut equals the maximum amount of flow that can be sent from the source to the sink. Variations of the minimum cut problem include: Weighted graphs, Directed graphs, Terminals, and Partitioning the vertices into more than two sets. Here are some applications of minimum cut: Network analysis: To find the minimum number of links that need to... Show more

In graph theory, a minimum cut (or min-cut) is a partition of a graph's vertices into two disjoint subsets. A minimum cut is minimal in some metric. For example, in a flow network, the minimum cut separates the source and sink vertices. The weight of this cut equals the maximum amount of flow that can be sent from the source to the sink.

Variations of the minimum cut problem include: Weighted graphs, Directed graphs, Terminals, and Partitioning the vertices into more than two sets.

Here are some applications of minimum cut:
Network analysis: To find the minimum number of links that need to be removed to disconnect a network.
Image segmentation: To partition an image into two regions, such as foreground and background.
VLSI design: To partition a circuit into two parts, such as a chip and a board.
There are several algorithms for finding the minimum cut of a graph. 

The most common algorithms are:
The Ford-Fulkerson algorithm, The Stoer-Wagner algorithm, and The Karger-Stein algorithm.
The Ford-Fulkerson algorithm is a relatively simple algorithm that works by repeatedly finding augmenting paths in the graph. An augmenting path is a path from the source to the sink that can be used to increase the flow through the network. The algorithm terminates when there are no more augmenting paths.
The Stoer-Wagner algorithm is a more sophisticated algorithm that works by repeatedly contracting edges in the graph. An edge contraction is an operation that merges two vertices into a single vertex. The algorithm terminates when the graph is reduced to a single vertex.
The Karger-Stein algorithm is a randomized algorithm that works by repeatedly contracting edges in the graph. The algorithm terminates when the graph is reduced to two vertices. The algorithm then returns the cut that separates the two vertices.

Show less