A cut in a graph is a set C=(S,T) of nodes such that S and T are two disjoint subsets of all nodes of the graph. The size of the cut is the number of edges between two disjoint subsets. A cut is said to be minimum if the size of the cut is not larger than size of any other cut of the graph.
To find the minimum cut of a graph, we can use Karger algorithm as illustrated below :
Algorithm :
1)While there are more than two vertices repeat step 2 to 4.
2) Select a random edge of the graph.
3)Merge the two vertices of the edge.
4)Remove self loops.
5) Return the cut represented by two vertices.
Although this algorithm can not guarantee the success in a single run but multiple run of the algorithm can award you a minimum cut.
A newbie generally faces problem while attempting to merge the vertices. Here i give you the main part of my implementation in JAVA .
A graph with two cuts. The dotted line in red is a cut with three crossing edges. The dashed line in green is the min-cut of this graph, crossing only two edges.(src:wikipedia) |
To find the minimum cut of a graph, we can use Karger algorithm as illustrated below :
Algorithm :
1)While there are more than two vertices repeat step 2 to 4.
2) Select a random edge of the graph.
3)Merge the two vertices of the edge.
4)Remove self loops.
5) Return the cut represented by two vertices.
Although this algorithm can not guarantee the success in a single run but multiple run of the algorithm can award you a minimum cut.
A newbie generally faces problem while attempting to merge the vertices. Here i give you the main part of my implementation in JAVA .
void kargerCut(int v1, int v2) //v1 and v2 are random vertices passed to this method { //list contains list of the vertices ArrayList<Integer> first = list.get(v1);//list of vertices from v1th list ArrayList<Integer> second = list.get(v2);//list of vertices from v2th list int num1=first.get(0);//get first number from first list int num2=second.get(0);//get second number from second list first.addAll(second);//add all vertices of second list to first list list.set(v1, first);//update the list for (int i = 0; i < list.size(); i++) {//This loop replaces the num2 by num1 in the entire list ArrayList<Integer> temp = list.get(i); for (int j = 1; j < temp.size(); j++) { if ( temp.get(j) == num2 ) { temp.set(j, num1 ); } } } //remove self loops in the first list for (int i = 1; i < first.size(); i++) { if (first.get(i) == num1 ) { first.remove(i); i--; } } list.remove(v2);//removes v2th list }
No comments :
Post a Comment