Math 2602 B1 , B2                                                                                       Homework  #8

                                              Due Thursday, October 23, 2003

Let  G  be the weighted undirected graph with vertices { A , B , C , . . . , H }and the edge weights ("lengths") given below.  (The remaining pairs are not adjacent.)

  AB - 3      AC - 4      AD - 3     AG - 8      AH - 8      BD - 4      BF - 4       BG - 1     BH - 3     CD - 4  
  CF - 5      CG - 4      DE - 11     DF - 8      DG - 9      DH - 5      EF - 2       FG - 4     GH - 2


  i)  Find the length of a shortest path from A to E in  G , and give such a path.


  ii) Find the total weight of a minimal spanning tree in  G , and draw such a tree.


  iii) Is  G planar?  Explain.


  iv) Does  G have a Hamiltonian cycle?  If so, give one.