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

1. Junior Member
Join Date
Mar 2009
Posts
3

## 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. Senior Member
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.

3. Junior Member
Join Date
Mar 2009
Posts
3

## Re: simple MST problem

can u plz explain ur answer??

4. ## 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. Junior Member
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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•