8.7.1 Implementation of Some Graph Algorithms

This assignment involves five problems.

1.

Generate a connected graph with n vertices and a certain number of edges, decided by an average degree d of each vertex. The connected graph generated should have several spanning trees and several Hamiltonian paths. Also, generate random costs for all the edges.

2.

Find a minimum cost spanning tree (MST) for the above graph, using an efficient implementation of Prim's algorithm. Compute the execution time of this program.

3.

Find an MST using Kruskal's algorithm. In the implementation, use the heap data structure to organize the set of edges and the MFSET data structure to implement union's and find's. Compare the execution time with that of Prim's algorithm.

4.

Find a second best MST by extending the Kruskal's algorithm, using the following property: If T is an MST, then there exist an edge (u, v) $\in$ T and an edge (x, y) $\notin$T such that (T - {(u, v)})U{(x, y)} is a second best MST.

5.

Find a Hamiltonian path using a greedy strategy based on Kruskal's algorithm. You can compare the cost of this path to that of a minimal cost Hamiltonian path (found by exhaustive enumeration) for values of n up to 10. In fact, you can do a little better by using the branch and bound method to compute the minimal cost Hamiltonian path.

6.

Provide examples of connected graphs for situations specified below. If an example cannot exist for the situation, provide reasons.

(a)

A graph in which a maximum cost edge is a part of every MST in the graph

(b)

A graph in which a maximum cost edge is never a part of any MST

(c)

A graph in which a least cost edge is not a part of any MST

7.

Let T be a minimum spanning tree of a connected graph G. Prove that there exist edges (u, v) $\in$ T and (x, y) $\notin$Tsuch that T - {(u, v)} $\cup$ {(x, y)} is a second-best minimum spanning tree of G.