Homework Exercise 2

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 e1 with minimum cost (i.e., c(e1) < c(e) for all edges e ∈ E-{e1}).
    Prove that every MST of G contains e1.

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