Math 2602                                                                                        Homework #9
                                  Due Thursday, November 3, 2005


    Let G be the weighted, undirected graph with vertices  { A , B , C , . . . , I } 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        I

                       A      *         4         3         6        *        10        7        5        7
                       B      4         *         2         *        *         *          *        *        *
                       C      3         2         *         4        *         *         4        2         6
                       D      6         *         4         *        7         1         *        *         1
                       E      *         *          *        7        *         7         6        *         4
                       F     10        *          *        1        7         *         4        5         2
                       G     7         *          4        *        6          4         *       1         3
                       H     5         *           2       *        *          5         1       *         3
                       I       7         *          6        1        4          2         3       3         *

     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 minimim spanning tree in  G , and draw such a tree.