X W NN 4. Recall: a cut of a graph is a partition of the node...

 

Transcribed Image Text:

X W NN 4. Recall: a cut of a graph is a partition of the node set into two non-empty subsets. E.g. on the small graph (above left), {{w,x}, {y,z}} is a cut with cross-edges {F,G,H,J}. RKMC is the randomized Kruskal min cut algorithm: unless otherwise stated, its input is a uniform- random permutation of the edges. a) For the big graph, give each min cut (partition and cross-edges) .. b)... and give the forest (draw on the nodes below) and cut (partition and cross-edges) found by RKMC when edges are input in order LUQRKNTVSJMP. b a d f h g X W NN 4. Recall: a cut of a graph is a partition of the node set into two non-empty subsets. E.g. on the small graph (above left), {{w,x}, {y,z}} is a cut with cross-edges {F,G,H,J}. RKMC is the randomized Kruskal min cut algorithm: unless otherwise stated, its input is a uniform- random permutation of the edges. a) For the big graph, give each min cut (partition and cross-edges) .. b)... and give the forest (draw on the nodes below) and cut (partition and cross-edges) found by RKMC when edges are input in order LUQRKNTVSJMP. b a d f h g