[Solved] CSCI 3104 Assignment # 6

1. Gru has decided to give you yet another task. He gives you a system of inequalities with variables x₁,x₂,,x_n, where each inequality is of the form x_i1 < x_i2 for i₁,i₂ {1,,n}. He proceeds to give you an example of such a system of inequalities: n = 5 and x₁ < x₃, x₁ < x₄, x₂ < x₅, x₅ < x₄.

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. (Grus hint: Convert the system of inequalities into a graph).

2. Gru argues that he could simplify our algorithm for finding SCCs by using the original graph G (instead of G^T) in the second call to DFS, and considering the vertices in increasing order of finish times. Will Grus idea produce the correct result? If yes, provide justification of why it works; if not, provide a counterexample.
3. 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 G⁰, where G⁰ 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

(

₀ 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 G⁰, whose edge weights are given by w⁰.

4. 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.