The minimum cut problem is to determine the cut which has the least number of crossing edges. 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.
No comments:
Post a Comment