Equivalence classes, minimum spanning trees, and Kruskal's algorithm.
---------------------------------------------------------------------

Here are the set of 11 edges for an undirected, weighted graph G.
For your convenience, I have sorted the edges into ascending order using
     Microsoft Excel.    The set V  =  {a, b, c, d, e, f, g}

The set E is as follows: This is also the sorted list L for Kruskal's.
{c, f}  1
{a, e}  2         The edges are already in sorted order, ascending,
{d, e}  4             by weight, for list L and your convenience.
{a, d}  6
{f, g}  6
{c, g}  7         These 11 edges are the set E for graph G = (V, E),
{b, c}  8
{a, b}  10              with V = {a, b, c, d, e, f, g}
{a, c}  10
{d, g}  12        Make a minimum spanning tree and answer the homework
{d, f}  16              questions using this data to create tree T,
                        NOT the data on the original handout.  

1.  Using Kruskal's algorithm shown below (and on page 441 of Judith
    Gersting textbook), show the tree T as it would exist at the end of
    the Kruskal's algorithm shown here.

2.  Show the set of equivalence classes when there are three equivalence
    classes left.

3.  Show the set of equivalence classes when there are two equivalence
    classes left.

4.  State which edges, if any, do NOT satisfy the Kruskal algorithm
    condition
                [a] != [b]           !=  means  not equal  
                                                ---------    [a] != [b]

    which is part of the if statement on the 3rd line of the while: 

   1.  Sort edges of the graph by weight, and let L be the sorted list.
   2.  Let T be the minimum spanning tree and initialize T := {}. 
   3.  For each vertex v of the graph, create equivalence class [v] = {v}.
   4.  while there are 2 or more equivalence classes do
              Let {a, b} be the edge at the head of L;
              L := tail(L);
              if [a] != [b] then       // which edges DO NOT satisfy this?
                 T := T U {{a, b}};
                 Replace the equivalence classes [a] and [b] by [a] U [b]
              end-if
       end-while
-----------------------------------------------------------------------------
5.  Suppose that a given Graph is a connected, weighted graph similar to the 
    non-directed graph above.  The graph has n vertices, and exactly 2n edges.
    
    a.  Is is possible for list L to be <>, i.e. an empty list at the end
        of the execution of the above algorithm?  Describe why or why not
        with an example and/or explanation.

    b.  What is the largest value that length(L) could return if we added
        the statement 5. print length(L) as the last step of the algorithm?