Problem 61

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Randomized MST example

Due: March 29
Points: 4

The following picture shows a graph with 8 nodes and 15 edges. Assume this is the \(G'\) that results after 3 Boruvka steps at the beginning of the randomized MST algorithm.

MST example graph

MST example graph

Some of the edges in \(G'\) as drawn above are in bold blue. Assume those are the edges chosen randomly to be in \(H\).

Show the steps of the randomized MST algorithm for this graph \(G'\). I want to see:

  • The subgraph \(H\) (by itself)
  • The resulting MST \(F\) of \(H\) from the first recursive call
  • Which edges in \(G'\) are \(F\)-light, and which are not.
  • The graph \(G''\) that will be sent to the second recursive call.
  • The result of the second recursive call, which will be the MST of \(G'\).

I know some of the labels in the graph above are hard to read. To help with that, keep in mind that all the labels are drawn in the middle of the edge length-wise, and off to one side. Here is a text listing of all the edges that should clarify any discrepancy:

  C -- E [label="1"];
  C -- D [label="2"];
  A -- B [color=blue,penwidth=2,label="3"];
  D -- E [color=blue,penwidth=2,label="4"];
  A -- F [label="5"];
  G -- H [color=blue,penwidth=2,label="6"];
  C -- G [color=blue,penwidth=2,label="7"];
  D -- H [color=blue,penwidth=2,label="8"];
  D -- G [label="9"];
  E -- H [color=blue,penwidth=2,label="10"];
  C -- H [color=blue,penwidth=2,label="11"];
  A -- D [color=blue,penwidth=2,label="12"];
  B -- H [color=blue,penwidth=2,label="13"];
  F -- G [color=blue,penwidth=2,label="14"];
  A -- H [label="15"];