Math 2602  B1, B2                                                                                                Homework  #9
                                                 Due  Thursday, October 28, 2004


  Let  G  be the weighted, undirected graph with vertices { A , B , . . . , H } and the edge weights
  ("lengths") given in the table below.  ( The symbol  " * " means there is no such edge.)


                                        A      B      C      D      E      F      G      H
                                A     *       2       *       *       *      3       *       5
                                B     2       *       2       4       *      *       4       6
                                C     *       2       *       5       *      4       4       *
                                D     *       4       5       *       3      2       *       6
                                E     *       *        *       3      *      6       *        *
                                F      3      *        4       2       6     *        2       *
                                G     *      4        4       *       *      2       *       5
                                H     5      6        *       6       *      *       5       *

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

















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