Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a connected, directed and weighted graph, Prim's algorithm may not necessarily generate the minimal spanning tree. Suppose we have such a graph $G$ with the special condition that for every pair of vertices $x, y \in G$ there exists a directed edge from $y \to x$ and a directed edge from $x \to y$ of equal weight. I was wondering if Prim's algorithm necessarily generates a minimal spanning tree if applied to $G$?

Further, suppose that we require a hamiltonian path of minimal weight between two vertices $x, y \in G$. Would the spanning tree generated by Prim's algorithm necessarily be less than or equal to the weight of this hamiltonian path?

share|improve this question
1  
Why do you use the Prim's algorithm for a directed graph? It doesn't generate even a spanning tree in this case. –  Harold Jun 5 '13 at 15:00
add comment

1 Answer

up vote 1 down vote accepted

So, in your directed graph, there is an edge from 'x' to 'y' of weight 'a' iff there is an edge from 'y' to 'x' of weight 'a'. Call this graph 'G1'.

Convert 'G1' into an undirected graph 'G2' so that there is an edge from 'x' to 'y' of weight 'a' in G2 iff there is an edge from 'x' to 'y' of weight 'a' in G1.

The cost of a minimum spanning tree (MST) in G1 is necessarily equal to the cost of an MST in G2.

So, take G1 as input, convert it into G2 and feed it into Prim's algorithm. IT generates a MST on G1.

As for the second part of your Q, yes-- Prim's algorithm necessarily be less than or equal to the weight of that Hamiltonian path. If it weren't, i.e. if the Hamiltonian path is of less cost than the tree, the Hamiltonian path would be the MST itself since a simple path is also a tree. A contradiction.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.