CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    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:
    Name:  4.jpg
Views: 1070
Size:  52.4 KB

  2. #2
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: Graphs and spanning trees

    Quote Originally Posted by lennard3 View Post
    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

  3. #3
    Join Date
    Jul 2013
    Posts
    576

    Re: Graphs and spanning trees

    Quote Originally Posted by lennard3 View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured