Description
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 Kruskal’s and Prim’s algorithms for minimum weight spanning trees and Dijkstra’s 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 Prim’s 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 T’s 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 Dijkstra’s 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, dT(s,v) = dG(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).
