![[-]](/~ygleyzer/course.wiki/images/button-minus.gif)
q5, is there any constrain on the e' edge?
by eial - Thursday, 14 May 2009 17:30:45
e.g. can it be any edge from the tested cut?
Re: q5, is there any constrain on the e' edge?
by algo092 - Thursday, 14 May 2009 18:03:12
As mentioned in the question:
1. e' is an edge in F (F=The edges of T).
2. e'=(u,v) such that u is in S and v is in V\S.
1. e' is an edge in F (F=The edges of T).
2. e'=(u,v) such that u is in S and v is in V\S.
Re: q5, is there any constrain on the e' edge?
by eial - Thursday, 14 May 2009 18:17:01
so I understand that the answer is no, e.g. e' can be any edge in the cut.
thanks.
thanks.
Re: q5, is there any constrain on the e' edge?
by eial - Friday, 15 May 2009 19:04:36
there is something I don't quite understand, does e' is in F in the start or e?
if e' is in F, we selected it randomly? are we switching the wrong edge (e') with the right edge (e) or e is selected randomly too?
if e' is in F, we selected it randomly? are we switching the wrong edge (e') with the right edge (e) or e is selected randomly too?
Re: q5, is there any constrain on the e' edge?
by algo092 - Sunday, 17 May 2009 13:03:54
e' is an edge in F. We select it following these conditions:
1. e' is an edge in F (F=The edges of T).
2. e'=(u,v) such that u is in S and v is in V\S.
e is not selected randomly, but according to the algorithm rule of choosing the next edge.
The rest is for you to figure out.
1. e' is an edge in F (F=The edges of T).
2. e'=(u,v) such that u is in S and v is in V\S.
e is not selected randomly, but according to the algorithm rule of choosing the next edge.
The rest is for you to figure out.
Re: q5, is there any constrain on the e' edge?
by eial - Monday, 18 May 2009 12:39:30
ok, I think I understand it abit more, now F is the edges set of the final tree or the tree in each iteration? and e' is any edge from F and e is any edge from the cut that is defined by e'.
also T is mst but T' isn't an mst, right?
just to understand the question better in order to tackle it with more ease.
edit: after looking at the question again, I've deduce that the change in after T was completed (thus removal of e' creates 2 sub trees) but, if e'!=e, e'=(u,v) so u in S and v in V\S and e=(x,y) so x in S and y in V\S, then e' must be e or else there is a vertex l in V which isn't in S so T isn't a mst but T is, so in light of this, I must deduce that the change is created in a single iteration, but removal of e' doesn't necessarily creates two sub trees.
can you clarify when does the change occurs? and what exactly are the conditions?
thanks.
also T is mst but T' isn't an mst, right?
just to understand the question better in order to tackle it with more ease.
edit: after looking at the question again, I've deduce that the change in after T was completed (thus removal of e' creates 2 sub trees) but, if e'!=e, e'=(u,v) so u in S and v in V\S and e=(x,y) so x in S and y in V\S, then e' must be e or else there is a vertex l in V which isn't in S so T isn't a mst but T is, so in light of this, I must deduce that the change is created in a single iteration, but removal of e' doesn't necessarily creates two sub trees.
can you clarify when does the change occurs? and what exactly are the conditions?
thanks.