Tools

Spanning Trees in Graphs

  1. Take an example graph of about 10 vertices and 20 edges. Assign weights to edges and use the algorithm of Kruskal to find a minimum spanning tree.
  2. In a graph G, let the edge uv have the least weight. Is it true that uv is always part of any minimum spanning tree of G? Is it true that uv is always part of some minimum spanning tree of G? Justify your answers.
  3. Let G be a graph and T be a minimum spanning tree of G. Suppose that the weight of an edge e is decreased. How can you find the minimum spanning tree of the modified graph. What is the runtime of your solution?
  4. Let G be a graph and T be a minimum spanning tree of G. Suppose that the weight of an edge e that also belongs to T is increased. How can you find the minimum spanning tree of the modified graph. What is the runtime of your solution?
  5. Let G be a graph and T be a minimum spanning tree of G. If an edge e is added to G with weight w(e) to get the graph G', how can T be modified to T' so that T' is a minimum spanning tree of G'. What is the runtime of your solution?
  6. Let G be a graph and e be a maximum weight edge on some cycle in G. Let G' be the graph obtained by removing the edge e from G. show that G' has a minimum spanning tree T' that is also a minimum spanning tree of G.
  7. Suppose that the edge weights in a graph are all either 1 or 2. Can you modify Dijkstra's algorithm to run faster? If so, describe your approach and analyze the runtime of your approach.
  8. Generalize the above question where the edge weights are between 1 and W.