1
$\begingroup$

Suppose i have a graph and i want to find minimum-spanning-tree. As in imperative languages we have to take specific steps from everynode(example ,we use kruskal's algorithm or prim's algorithm) to find the Minimum spanning tree

but

in declarative language(specially prolog, we can apply same algorithm but those are limited) , If i want to find a minimum spanning tree on the same graph, If i collect all possible hamiltonian paths using findall/3 predicate then chose the one with smallest accumulated cost, is it then also a minimum-spanning-tree?

More specifically , Can we transform the problem of finding minimum spanning tree to the hamiltonian path finding problem but not in other direction? Because normal algorithms return one specific minimum spanning tree of a graph but i am more interest in finding more than one minimum spanning trees.

$\endgroup$
2
$\begingroup$

No. Every path is a tree, but not every tree is a path. Therefore, the minimum spanning path might be more expensive than the minimum spanning tree.

If you work through some examples you should be able to find an explicit counterexample. I'll let you have the joy of finding it on your own.

$\endgroup$

Your Answer

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

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