CSCI 2300 — Introduction to Algorithms
Lab 4 (document version 1.0) — DUE July 15, 2020
Minimum Spanning Trees and Perfect Matchings
• This lab is to be completed individually. Do not share your work or code with anyone else.
• For all labs, please avoid using Google to find suggestions or solutions. The goal is to use
your own brain to work these problems out, which will help you develop the skills to do well
on the exams and, more importantly, become a substantially better computer scientist.
In this lab, we focus on minimum spanning trees and the new concept of perfect matchings.
1. Show that Prim’s Algorithm works for graphs that contain negative edge weights.
Hint: Start by working out a few examples, then prove the claim by showing that each step
of Prim’s Algorithm works for an edge of negative edge weight.
2. Prove by contradiction that if graph G = (V, E) has a cycle that includes unique heaviest
(highest-weighted) edge e, then e cannot be part of any minimum spanning tree of G.
3. Given undirected tree T = (V, E), write a linear-time algorithm that determines whether T
contains a perfect matching. Here, we define a perfect matching as subset Em of edge set E
that contains edges incident with each vertex exactly once. As an example, in the graph
shown below (not a tree!), we have two perfect matchings, i.e., Em = {{A, B}, {C, D}}
and Em = {{A, C}, {B, D}}.
Be sure to describe the runtime of your algorithm using Big-O() notation.
Hint: Start by looking for specific properties that must be true to have a perfect matching
in a tree (e.g., how many vertices must you have to actually have a perfect matching, how
many perfect matchings can a tree have, etc.?), then generalize into a linear-time algorithm.
What to submit
Please submit a single PDF file called upload.pdf that neatly contains your answers to the above
questions. Be sure to proofread your work and make sure it is clear, concise, and correct.