Math 2602 A1, A2, A3                                                                  Homework   #8

                                               Due  Tuesday,  March 18, 2003

       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 that there is no such edge.)


                                    A        B        C        D       E        F        G        H        I

                       A          *         4         2         6        *       10        6         5        7     
                       B          4          *        2         *        *         *         *        *        *
                       C          2         2         *         3        *         *         4        2        6
                       D          6         *         3         *        7         1         *        *        1
                       E           *         *         *         7        *         7         6       *        4
                       F          10        *         *         1        7         *         4        5        2
                       G          6         *         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 minimal spanning tree in G, and draw such a tree.












      iii)  Is G planar?  Explain.