[-] Question5
by sagydr - Saturday, 16 May 2009 10:32:24
I don't understand 2 things:
1. the removal of e' is done at the end of the process? once we already have the MST? or during the process of constructing the MST?

2. by removing the edge e' from the MST  T , and adding e, which was NOT in the MST, we get a new tree  T' but why would its weight be "at most" as the weight of T?
thread
Re: Question5
by algo092 - Sunday, 17 May 2009 12:21:36

1. During each iteration, an edge is being examined, as described in the algorithm and in the question. If the edge is closing a circle we ignore it. Otherwise, the algorithm adds it to the edges selected so far. If the edge we just added is in the spanning tree we have (existed from the Induction assumption) then we move one. Else - we replace it with e'. So, the removal of e' is done only in this case (In EACH iteration).

2. This section (seif b) is for you to figure out.

thread