Cheap and Secure Web Hosting Provider : See Now

Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?

, , No Comments
Problem Detail: 

I am studying the algorithm of Sollin and we recently studied a lemma:

Let be G a graph which values are diffferent on the edges.

  • We sort the edges $e_1,e_2,...e_m$ such as $v(e_i)<v(e_j)$
  • Every tree of minimal value has at least $e_1$ et $e_2$

Proof

let be A a spanning tree which doesn't have $e_1$

$A\bigcup\{e_1\}$ has a unique cycle

let be $e_i \in$ cycle, $e_i\ne e_1$ then $A\bigcup\{e_1\}-\{e_i\}$ is a tree which value is < $v(A)$ because $v(e_i)>v(e_1)$

I don't understand why would $A\bigcup\{e_1\}$ would have a unique cycle? Do you have a justification? A graphical example?

Asked By : Marine1
Answered By : Konstantin Yovkov

The proof outcomes from the definition of a tree - they are non-oriented, connected graphs with no cycles.

Lets assume that there's no cycle after adding $e1$. Let $e1$ = $(v1, v2)$. This means that before adding $e1$ there wasn't any path that connects $v1$ and $v2$, which contradicts to the connectivity of the spanning tree. On the other hand, if there was a path the connects $e1$ and $e2$ (which didn't include $(e1, e2)$) then adding this very edge will result into a cycle, which again contradicts to the definition of a tree.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50038

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback