CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Hybrid View

1. Junior Member
Join Date
Oct 2013
Posts
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:

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.

3. Member +
Join Date
Jul 2013
Posts
576

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 04: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
•