1 Attachment(s)

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:

Attachment 31903

Re: Graphs and spanning trees

Quote:

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.

Re: Graphs and spanning trees

Quote:

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.