Given a graph G(V,E) with nonnegative weights, a spanning k-forest is a cycle-free collection of edges...

 

Transcribed Image Text:

Given a graph G(V,E) with nonnegative weights, a spanning k-forest is a cycle-free collection of edges FCE such that the graph with the same vertices as G but only the edges in F has at most k connected components. The weight of a k-forest F is the total weight of all edges in F. The minimum spanning k-forest is defined as the spanning k-forest of minimum weight. 1 Note that when k = 1, this is equivalent to the minimum spanning tree. For simplicity, in this problem you may assume that all edges in G have distinct weights. (a) Define a j-partition of a graph G to be a list of j sets of vertices II = {S1, S2...S;} such that every vertex in G appears in exactly one of these sets. Define an edge (u, v) to be crossing a j-partition II = {S1, S2...S;} if the set in II containing u and the set in II containing v are different sets. For example, one 3-partition of the graph with vertices {A, B, C, D, E} is II = {{A, B}, {C}, {D, E}}, and an edge from A to C would cross this partition. Show that for any k'-partition II of a graph G, if k'>k then the lightest edge crossing II must be in the minimum spanning k-forest of G. (b) Give an efficient algorithm for finding the minimum spanning k-forest. Your solution should include the algorithm description, proof of correctness, and runtime analysis. Given a graph G(V,E) with nonnegative weights, a spanning k-forest is a cycle-free collection of edges FCE such that the graph with the same vertices as G but only the edges in F has at most k connected components. The weight of a k-forest F is the total weight of all edges in F. The minimum spanning k-forest is defined as the spanning k-forest of minimum weight. 1 Note that when k = 1, this is equivalent to the minimum spanning tree. For simplicity, in this problem you may assume that all edges in G have distinct weights. (a) Define a j-partition of a graph G to be a list of j sets of vertices II = {S1, S2...S;} such that every vertex in G appears in exactly one of these sets. Define an edge (u, v) to be crossing a j-partition II = {S1, S2...S;} if the set in II containing u and the set in II containing v are different sets. For example, one 3-partition of the graph with vertices {A, B, C, D, E} is II = {{A, B}, {C}, {D, E}}, and an edge from A to C would cross this partition. Show that for any k'-partition II of a graph G, if k'>k then the lightest edge crossing II must be in the minimum spanning k-forest of G. (b) Give an efficient algorithm for finding the minimum spanning k-forest. Your solution should include the algorithm description, proof of correctness, and runtime analysis.