
October 10th, 2013, 10:23 PM
#1
Graphs and spanning trees
I found an article with algorithms as problems and this one particular problem seemed to intrigue me but I'm not sure how I would solve it. My first initial thought was to use Dijkstra's algorithm to solve it but I don't even know where to begin even with using that. Can anyone guide me through the problem so I can see how these types of problems are solved?
Thank you very much.
Here's the problem:

October 11th, 2013, 02:40 AM
#2
Re: Graphs and spanning trees
Originally Posted by lennard3
Can anyone guide me through the problem so I can see how these types of problems are solved?
These types of exercises are not solved in a particular way. You just need to wrestle with them until you see the solution. Try different approaches, draw things on paper, look for related proofs you know of.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it.  P. D. Ouspensky

October 11th, 2013, 05:50 PM
#3
Re: Graphs and spanning trees
Originally Posted by lennard3
Can anyone guide me through the problem so I can see how these types of problems are solved?
Well, in (a) it seems you've discussed different spanning tree algorithms in class? It's also suggested the edge change operation is used in those algorithms.
Now if in class an algorithm was presented that generates all spanning trees using edge changing that's what you're looking for. That algorithm generates a sequence of all spanning trees so there must be an edge changing path from any T1 to any T2 (because T1 and T2 are in the sequence of all T's with one edge change between neighbours).
As for (b), if the algorithm in (a) that generates all spanning trees works in polynominal time it's just to run it looking for a spanning tree with cost k.
Last edited by razzle; October 11th, 2013 at 05:57 PM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
