CSDS 455: Applied Graph Theory

Homework 6

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