1. Let graph G have the six vertices a,b,c,d,e, and f, and the nine edges
    ac with weight 15
    ad with weight 10
    ae with weight 1
    bc with weight 3
    bd with weight 20
    be with weight 5
    fc with weight 12
    fd with weight 7
    fe with weight 9

(a) What is the minimum spanning tree of this graph?

(b) In what order would the Prim-Dijkstra-Jarnik algorithm, starting
from vertex a, add edges to form the MST?

(c) In what order would Boruvka's algorithm add edges to form the MST?

(d) In what order would Kruskal's algorithm add edges to form the MST?


2. What is the running time for each of the three algorithms,
Prim-Dijkstra-Jarnik, Boruvka, and Kruskal, when used to build a maze
from a k-by-k grid of squares? For Prim-Dijkstra-Jarnik, use the
analysis for the variant of the algorithm that uses binary heaps, and
for Kruskal's algorithm, assume that the sorting stage of the algorithm
is done using a comparison sorting algorithm.  Express your answers in
O-notation, as a function of k.


3. Does graph G have an Euler tour? Why or why not?


4. There are six different Hamiltonian cycles in G.

(a) List them all. (Hint: you may assume that a, b, and f are in
positions 1, 3, and 5 of the cycle.)

(b) Which one is the traveling salesman tour? What is its length?