CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    Join Date
    Mar 2009
    Posts
    3

    Question simple MST problem

    can someone plz give me the solution to this problem--


    Show that if an edge(u,v)is contained in some MST, then it is a light edge crossing some cut of the graph.

    i have very little idea graphs...therfore a detailed soln will be welcome...

    plz help as soon as possible.

  2. #2
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: simple MST problem

    There are two algorithms which is Kruskal and Prim's algorithm.
    Thanks for your help.

  3. #3
    Join Date
    Mar 2009
    Posts
    3

    Re: simple MST problem

    can u plz explain ur answer??

  4. #4
    Join Date
    Oct 2006
    Posts
    616

    Re: simple MST problem

    Hi,

    If this is a homework assignment (and it sounds like one), please take a look at this.
    Now, after you show some genuine effort, it would help writing your question in a little more detail, especially if you use some special definitions,
    e.g. "light edge" (?)

    P.S: I believe the solution requires some sort of formal proof, therefore Peter's answer probably doesn't mean anything - Kruskal's and Prim's are just 2 algorithms for finding a MST in a graph.

    Regards,
    Zachm
    Last edited by Zachm; March 28th, 2009 at 03:36 PM.

  5. #5
    Join Date
    Mar 2009
    Posts
    3

    Re: simple MST problem

    A cut (S, V − S) of an undirected graph G = (V,E) is a partition of V .

    An edge (u, v) crosses the cut iff one of ts endpoints is in S and the other is in V −S.

    An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.

    P.S.-it is a homework assignment...
    but the thing is that we hvnt been taught graphs as of yet in our Data Structure class. nonetheless, we are expected to submit it by the 4th of april. i tried studying it by myself, but couldnt understand most of the things. however, i managed to understand the above defintions.

    i understand your policies regarding hw assignments, but i need your expert help urgently.

Tags for this Thread

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