I'm studying random contraction algorithm and could not understand how it works.
In the course it says that a graph G=(V,E) with n vertices, m edges. a minumum cut(A,B), are there are many vertices either on A's or B's sides. k=number of edges crossing (A,B).(call these edges F)
then it make the conclusion that an edge of F is contracted at some point, algorithm will not output(A,B).
Why is this? suppos there is a vertice C in A's side and a vertice D in B's side, so the edge(C,D) would belong to F, but even if C and D are to contract, we still have A and B, the algorithm can still return (A,B) right?
If G is a graph and (A, B) is a cut in the graph, then A and B are sets of nodes, not individual nodes in G. That is, there is no node in G called A or B. Rather, the nodes in G can be split apart into two groups, one of which we’ll call A and one of which we’ll call B. As a result, you can’t have the situation you’ve described.
Here’s another way to think about this. Suppose (A, B) is a minimum cut. You can then imagine that every node in the graph is painted red if it’s in the A side and blue if it’s in the B side. The randomized contraction algorithm will then find the cut (A, B) assuming that no red node is merged with a blue node. If nodes of opposite colors are merged, then the resulting cut won’t consist of all the red nodes on one side and all the blue nodes on the other.