MHB Sentences about the Template algorithm

[evinda]

Hello! (Wave)

Could you explain me some sentences,that are related to the following algorithm?

Template algorithm(G)
   A<-∅
   while A isn't a connected tree
           we define an edge (u,v),that is secure for A
           A<-A U {(u,v)} 
   return A

• Let $G=(V,E)$ be an undirected connected graph with weight function $w:E \to \mathbb{R}$.Let $A \subseteq E$,that is contained in a minimum spanning tree for the graph $G$ and let $(S, V \setminus S)$ any intersection of $G$,that respects $A$.Let,also, $(u,v)$ a light edge,crossing the intersection $(S, V \setminus S)$.Then,the edge $(u,v)$ is secure for $A$.
  $$$$
• A minimum spanning tree isn't unique.
  $$$$
• The Template Algorithm is implemented at most $|V|-1$ times.
  $$$$
  Does this sentence maybe stand,because of the fact that $G$ is connected,so $|E|=|V|-1$,and if during the implementation,cycles aren't created,the "while" loop is implemented so many times as the number of edges,so $|V|-1$ times? (Thinking)
  $$$$
• Let $G_A=(V,A)$.Then, $G_A$ is a forest and each of its connected components , is a tree.
  
  Why is $G_A$ a forest and not a connected tree,although the condition of the algorithm is:
  
  

  while A isn't a connected tree

  
  ? (Thinking)
  $$$$
• Any secure edge $(u,v)$ for $A$ connects different components of $A$.

 

[I like Serena]

Heya! (Blush)

• Let $G=(V,E)$ be an undirected connected graph with weight function $w:E \to \mathbb{R}$.Let $A \subseteq E$,that is contained in a minimum spanning tree for the graph $G$ and let $(S, V \setminus S)$ any intersection of $G$,that respects $A$.Let,also, $(u,v)$ a light edge,crossing the intersection $(S, V \setminus S)$.Then,the edge $(u,v)$ is secure for $A$.

What is that: $(S, V \setminus S)$ any intersection of $G$,that respects $A$?

• A minimum spanning tree isn't unique.

If you have edges with equal weight, you may be able to choose which one to include in the mimimum spanning tree.

• The Template Algorithm is implemented at most $|V|-1$ times.
  $$$$
  Does this sentence maybe stand,because of the fact that $G$ is connected,so $|E|=|V|-1$,and if during the implementation,cycles aren't created,the "while" loop is implemented so many times as the number of edges,so $|V|-1$ times? (Thinking)
  $$$$

Not quite. $G$ can have more edges than that.

How many edges can any tree have at most? (Wondering)
That identifies how many times you can add a secure edge.

• Let $G_A=(V,A)$.Then, $G_A$ is a forest and each of its connected components , is a tree.
  
  Why is $G_A$ a forest and not a connected tree,although the condition of the algorithm is:
  
  

  while A isn't a connected tree

  
  ? (Thinking)
  $$$$

Let's take a look at the following algorithm:

At which stages is it a forest of trees? (Wondering)

• Any secure edge $(u,v)$ for $A$ connects different components of $A$.

At any time $A$ represents a minimum spanning forest of trees.
If you remove any edge from $A$, it will split one of its trees into 2 sub trees. (Mmm)

 

[evinda]

What is that: $(S, V \setminus S)$ any intersection of $G$,that respects $A$?

The edge $(u,v) \in E$ crosses the intersection $(S, V \setminus S)$, if one of its vertices is in $S$ and the other one in $V \setminus S$.

View attachment 3169

An intersection $(S, V \setminus S)$ respects a set of edges, if no edge of the set crosses the intersection.

If you have edges with equal weight, you may be able to choose which one to include in the mimimum spanning tree.

I understand.. (Yes)

Not quite. $G$ can have more edges than that.

How many edges can any tree have at most? (Wondering)
That identifies how many times you can add a secure edge.

$|V|-1$, in order that we don't have cycles.. Or am I wrong? (Thinking)

Let's take a look at the following algorithm:At which stages is it a forest of trees? (Wondering)

Nice algorithm! (Mmm) Isn't it a forest of trees at each stage? (Thinking)

At any time $A$ represents a minimum spanning forest of trees.
If you remove any edge from $A$, it will split one of its trees into 2 sub trees. (Mmm)

I understand! (Nod)

 

[I like Serena]

$|V|-1$, in order that we don't have cycles.. Or am I wrong? (Thinking)

Nice algorithm! (Mmm) Isn't it a forest of trees at each stage? (Thinking)

I understand! (Nod)

Yep, yep, and good! (Happy)