[Solved] CSDS455 Homework6

Next week we will be looking at distances in a graph. For this homework, you will need to look up distance parameters for graphs, and to read about Kruskals and Prims algorithms for minimum weight spanning trees and Dijkstras algorithm for finding a single source shortest paths tree.

Problem 1: Prove that rad(G) diam(G) 2 rad(G) for every graph G where rad(G) is the radius of graph G and diam(G) is the diameter of G.

Problem 2: Let G be a graph in which each edge e has a weight w(e) where w : E(G) Z. Let T be a minimum weight spanning tree of G. Let P be the spanning tree produced by running Prims Algorithm on G. Prove that we can convert the optimal tree T into tree P by a sequence of edge replacements such that after each replacement, the graph resulting from the edge replacement is a tree with total weight no larger than Ts weight.

Problem 3: Let G be a directed graph in which each edge e has a weight w(e) as above. Prove that if some edge has a negative weight then Dijkstras Algorithm may fail to produce a single source shortest spanning tree.

Problem 4: Let G be a graph (directed or undirected) in which each edge e has a weight w(e) as above and let s be a vertex of G. Prove that there exists a spanning tree of T such that for each vertex v of G, d_T(s,v) = d_G(s,v). That is, the distance from s to v in T is equal to the shortest distance from s to v in G. Prove that this holds even if some edge weights are negative (but there is no negative weight cycle and no undirected edge with negative weight).