CS515 Homework 8

CS515, Fall 2020
Homework 8
Due: November 11, 2020
1. (16 pts.) Let e1 and e2 be two lowest-weight edges in a connected and weighted graph G. Show that
e1 and e2 belong to some MST in G.
2. (16 pts.) Consider this statement: If e1, e2 and e3 are three lowest-weighted edges in a connected
and weighted graph G, then e1, e2 and e3 belong to some MST in G. Is this statement true? Either
prove it or show a counterexample.
3. (16 pts.) Show that every MST in a connected, weighted graph G is returned by Kruskal’s algorithm
for some sorted order of the edges of G.
4. (16 pts.) Let G be a connected, weighted graph G and let e be an edge in G. Is it possible for e to
be a part of every MST in G? If so, describe a general condition that guarantees it.
5. (20 pts.) Let G be a connected, weighted graph G and let e be a highest-weight edge in G. Is it
possible for e to be a part of some MST in G? If you think the answer is no, explain why. If you
think the answer is yes, formulate a possibly general conditions under which e is included in some
MST.
6. (16 pts.) Suppose all edge weights in a graph are integers in the range 1 to V . How fast can you
make Kruskal’s algorithm run? Explain.
7. (Bonus: 30 pts.) A directed graph G = (V; E) is semi-connected if for all pairs of vertices u; v 2 V ,
u is reachable from v or v is reachable from u. Describe a O(jV j + jEj) algorithm to determine
whether or not G is semi-connected. A precise narrative is acceptable. Explain why your algorithm
is correct and justify the running time.