1. Give an example of a weighted graph for which the minimum spanning tree is unique. Indicate what the minimum spanning tree is for that graph. Give another example of a weighted graph that has more than one minimum spanning tree. Show two different minimum spanning trees for that graph. What determines whether a graph has a unique minimum spanning tree?

2. Execute Prim’s minimum spanning tree algorithm by hand on the graph below showing how the data structures evolve. Clearly indicate which edges become part of the minimum spanning tree and in which order. Start at vertex H.

3. Consider the weighted graph shown below:

Construct every depth-first search tree starting at vertex a and determine the weight of that tree. Construct the breadth-first search tree starting at vertex a. Determine its weight. Are any of those trees a minimum spanning tree?

4. Given the following adjacency lists (with edge weights in parentheses) for a digraph:

A: B(4.0), F(2.0)

B: A(1.0), C(3.0), D(4.0)

C: A(6.0), B(3.0), D(7.0)

D: A(6.0), E(2.0)

E: D(5.0)

F: D(2.0), E(3.0)

Execute Dijkstra’s shortest-path algorithm by hand on this graph, showing how the data structures evolve, with A as the starting vertex.. Clearly indicate which edges become part of the shortest path and in which order