Answer Happy

Question 2. Consider the following scenario. ● G is a simple, weighted, undirected graph. • S is a shortest path tree of G starting at vertex s. ● T is a minimum spanning tree of G. G' is a graph that is basically a copy of G except that every edge weight has been increased by a constant c. (a) Disprove the following statement by drawing a counterexample. The vertices and edges making up S in G also make up a shortest path tree in G'. (Note: This is why it doesn't work to just add a constant to a graph with negative weights so that you can use Dijkstra's Algorithm on it.) (b) Prove that the following statement is true. The vertices and edges making up T in G also make up a minimum spanning tree in G'. (Hint: To prove this, you may want to use the fact that Kruskal's Algorithm will work correctly on all input graphs.)