Minimum Cut Problem

Input - An undirected graph G = (V,E) (note that parallel edges are allowed)

Goal - Tom compute a cut with fewest number of crossing edges (a min cut) 

The minimum cut problem or min-cut problem is to determine the cut which has the least number of crossing edges.

Please note that to understand mincut, you have to first read what is cut, if you don't alreadyy know that. 

So, consider the following graph -

What is the mincut for this graph? Answer is 2 :

Here the graph was symmetric, but generally it may not be so.

Applications of Min-cut

• This is used when you want to break a graph down into two or more pieces. For example, in networks, the minimum cut can help determine where hot spots and weaknesses are.
• Another example is image segmentation. An image can be thought of as a graph of pixels. Each pixel has an edge connecting to adjacent pixels, each with an edge weight which is how much you "expect" the two to be of the same object. Thus, by computing a minimum cut, we can essentially take out that object from the image.
  
• Community detection in social networks

Algorithms to find min-cut

• Random Contraction Algorithm