Suppose Vojtech Jarnk had an evil twin, named Stanislaw, who designed a divideand-conquer algorithm for finding minimum

Question:

Suppose Vojtech Jarnìk had an evil twin, named Stanislaw, who designed a divideand-conquer algorithm for finding minimum spanning trees. Suppose G is an undirected, connected, weighted graph, and, for the sake of simplicity, let us further suppose that the weights of the edges in G are distinct. Stanislaw’s algorithm, MinTree(G), is as follows: If G is a single vertex, then it just returns, outputting nothing. Otherwise, it divides the set of vertices of G into two sets, V1 and V2, of equal size (plus or minus one vertex). Let e be the minimum-weight edge in G that connects V1 and V2. Output e as belonging to the minimum spanning tree. Let G1 be the subgraph of G induced by V1 (that is, G1 consists of the vertices in V1 plus all the edges of G that connect pairs of vertices in V1). Similarly, let G2 be the subgraph of G induced by V2. The algorithm then recursively calls MinTree(G1) and MinTree(G2). Stanislaw claims that the edges output by his algorithm are exactly the edges of the minimum spanning tree of G. Prove or disprove Stanislaw’s claim.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Algorithm Design And Applications

ISBN: 9781118335918

1st Edition

Authors: Michael T. Goodrich, Roberto Tamassia

Question Posted: