Prim’s algorithm and Kruskal’s algorithm choose the lexicographically first edge

Question

Prim’s algorithm and Kruskal’s algorithm choose the lexicographically first edge first. That is, if a choice must be made between two distinct edges, e1 = (u1 , v1 ) and e2 = (u2 , v2 ) of the same cost, where u1 < v1 and u2 < v2 , then the following strategy is used. Suppose the vertices are numbered 1, 2, . . . , n. Choose e1 if u1 < u2 , or u1 = u2 and v1 < v2 . Other wise, choose e2 . Prove that under these conditions, both algorithms construct
the same min-cost spanning tree

Im a little confused on how to start this problem, any help would be appriciated :)

Explanation / Answer

I answered it in the math forum, why did you post twice? This proof is quite easy, try not to think of as a CS problem when you modified the cost function by using the lexicographic order you basically changed the cost function Lets see, name your vertices from 1 to n let edge cost f(u,v) = the defined edge cost(infinity if not present) Consider a new cost function for edges g(u,v) = f(u,v)*n^3 + un + v (I am assuming here that all edge costs are integers, which is reasonable, else we could clear out the denominator of the rational costs and we never really use irrational costs) This function considers the lexiographical order correctly, if f(u,v)>f(a,b) then g(u,v)>g(a,b) but if they are equal then g prefers those with smaller indices Now let prims and kruskals get the MST on the cost function g Its now obvious that the trees are same. Because the trees are same f would have generated the same trees with lex. order Hence proved

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.