Math 2602  B1, B2                                                                         Homework  #9
                                            Due Tuesday, March 15, 2005

     1.  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 edge.)

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

       a)  Find the path of shortest length from A to E in  G .



















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