===========================================================================
CSC 373                     Homework Exercise 2                   Fall 2008
===========================================================================

Due: by 6pm on Tue 23 Sep
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure
that you use notation and terminology correctly, and that you explain and
justify what you are doing.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.


1.  Show that the reverse-delete algorithm presented in class is an
    implementation of the generic algorithm -- describe precisely how the
    choices made by the reverse-delete algorithm correspond to applications
    of the red rule or the blue rule.


2.  Suppose that G = (V,E) is an undirected, connected, weighted graph in
    which there is a unique edge e_1 with minimum cost (i.e., c(e_1) < c(e)
    for all edges e (- E-{e_1}).
    Prove that every MST of G contains e_1.


3.  Suppose that G = (V,E) is an undirected, connected, weighted graph in
    which there is a unique edge e_m with maximum cost (i.e., c(e_m) > c(e)
    for all edges e (- E-{e_m}).
    Prove or disprove: *no* MST of G contains e_m.