Description
- Gru has decided to give you yet another task. He gives you a system of inequalities with variables x1,x2,…,xn, where each inequality is of the form xi1 < xi2 for i1,i2 ∈ {1,…,n}. He proceeds to give you an example of such a system of inequalities: n = 5 and x1 < x3, x1 < x4, x2 < x5, x5 < x4.
Your task, he explains, is to write down an algorithm (high level description is sufficient) which does two things: (1) it should check whether a solution to a given system of inequalities exists, and (2) if a solution exists, it should find the solution. (Gru’s hint: Convert the system of inequalities into a graph).
- Gru argues that he could simplify our algorithm for finding SCCs by using the original graph G (instead of GT) in the second call to DFS, and considering the vertices in increasing order of finish times. Will Gru’s idea produce the correct result? If yes, provide justification of why it works; if not, provide a counterexample.
- Gru gives you a graph G, a set of edge weights w, and an MST T of G. He would like to know if T is also an MST of G0, where G0 is formed by decreasing the weight of exactly one of the edges in T. In other words, denote the edge chosen to be (x,y) ∈ T, k be a positive number representing the decreased edge weight, and a weight function defined as
(
0Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â w(u,v)Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â if (u,v) 6= (x,y)
w (u,v) = w(x,y) − k if (u,v) = (x,y)
Prove that T is an MST for G0, whose edge weights are given by w0.
- Your final task this week (assigned, of course, by Gru himself) is to show that a graph G has a unique MST if, for every cut of G, there exists a unique light edge crossing the cut. In addition, Gru asks you to disprove the converse via a counterexample.
