0
$\begingroup$

I'm working on an exam question that asks me to run the Double-Tree Heuristic algorithm on the following graph:

enter image description here

This algorithm starts by finding a minimum cost spanning tree.

My solution:

Minimum spanning tree contains edges ec, cb, dc, da

Doubling these edges to find an Euler tour: a, d, c, b, c, e, c, d, a

Removing duplicate edges: a, d, c, b, e, a

Actual solution:

Minimum spanning tree contains edges ed, ec, cb, da

Doubling these edges to find the Euler tour: a d e c b c e d a

Removing duplicate edges: a d e c b a (cost: 51)

I want to know if I have used the algorithm correctly. Can there be more than 1 specific solution to this problem?

$\endgroup$
  • $\begingroup$ There can be more than one minimum spanning tree. $\endgroup$ – Louis May 12 '15 at 14:20
  • $\begingroup$ Just to clarify, there can be several solutions for this problem (including mine)? $\endgroup$ – eyes enberg May 12 '15 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.