How can I give a set of transitions sufficient to transform any spanning tree into any another spanning tree in a finite number of steps via spanning trees? I was wondering if someone help me.Thanks.
1
-
1$\begingroup$ What do you mean by a transition? You could just consider the group of bijections on the set of spanning trees, but I imagine this isn't what you had in mind. $\endgroup$– Pat DevlinCommented Dec 10, 2016 at 20:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I assume that by a transition you mean adding one edge and removing another. Then it seems that a simple algorithm works: Add an edge from the new tree. This will create a cycle so just remove one edge from the cycle that is not in the new tree. Such an edge must exist, since there are no cycles in the new tree. The running time is just the number of edges in the new cycle that are not in the original one.
-
$\begingroup$ @user123 your question doesn't sound appropriate for this forum. But to answer your question, add an edge that you need and then just remove an edge from the formed cycle that you don't need. This will work in at most $n-1$ steps. $\endgroup$ Commented Dec 11, 2016 at 0:59