Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 7 / d

Table of contents
- Solution d

Solution

Processing by increasing weight, Kruskal's algorithm accepts

df

of weight one and

c f

of weight two, then rejects

c d

of weight three because its endpoints are already connected. It accepts

a c

,

e h

,

f h

, skips

d e

, accepts

b e

, skips

b c

, and accepts

e g

. Seven accepted edges now connect all eight vertices.

The resulting minimum spanning tree is

{df, c f, a c, e h, f h, b e, e g}, w (T) = 1 + 2 + 4 + 5 + 6 + 8 + 10 = 36.

The remaining heavier edges are unnecessary once the tree is complete. Distinct edge weights also imply that this minimum spanning tree is unique.

Figure 1.
Minimum spanning tree of weight 36 and its component-merging construction
. The solution highlights the seven selected edges. The second panel distinguishes the six distinct first-round choices from the joining edge fh selected in the second round. Details.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version