MHB What is the Template Algorithm for Minimum Spanning Trees?

[evinda]

Hello! (Wave)

According to my notes:

Template algorithm
The algorithm keeps the invariant :
"before each iteration,the set $A$ of vertices is a subset of some minimum spanning trees" at each step,where $A$ is an initial set of vertices.

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

Definition:
The edge $(u,v)$ is called secure for the set $A$,if it can be added to it,without the violation of the invariant.Could you explain me the following sentence? (Thinking)

The algorithm keeps the invariant :
"before each iteration,the set A of vertices is a subset of some minimum spanning trees" at each step,where $A$ is an initial set of vertices.

 

[I like Serena]

Definition:
The edge $(u,v)$ is called secure for the set $A$,if it can be added to it,without the violation of the invariant.Could you explain me the following sentence? (Thinking)

The algorithm keeps the invariant :
"before each iteration,the set A of vertices is a subset of some minimum spanning trees" at each step,where $A$ is an initial set of vertices.

Hey evinda! (Wink)

An invariant is a statement (or property, or proposition) that holds true at each iteration of a loop.

In this case the statement is that A is a subset of a minimum spanning tree.
Initially A is an empty set, which satisfies the statement.
When we add an edge that belong to a minimum spanning tree, the statement will still be satisfied. So that edge was what they call secure.

 

[evinda]

Hey evinda! (Wink)

An invariant is a statement (or property, or proposition) that holds true at each iteration of a loop.

In this case the statement is that A is a subset of a minimum spanning tree.
Initially A is an empty set, which satisfies the statement.
When we add an edge that belong to a minimum spanning tree, the statement will still be satisfied. So that edge was what they call secure.

I understand...Thanks a lot! (Smile)
Could you also give me an example,at which I can apply the template algorithm? (Thinking)

 

[evinda]

The algorithm,that is in my notes,is the following:

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

I wrote component,instead of tree,in the first post.. (Blush) (Wasntme)

 

[I like Serena]

I understand...Thanks a lot! (Smile)
Could you also give me an example,at which I can apply the template algorithm? (Thinking)

Sure!

How about the following graph. (Blush)

View attachment 3113

I wrote component,instead of tree,in the first post.. (Blush) (Wasntme)

Ooooh! (Speechless)

 

[evinda]

Sure!

How about the following graph. (Blush)

View attachment 3113

Do we always choose the edge,with the minimum weight? (Thinking)

So..is this a minimum spanning tree? (Thinking)

View attachment 3115

 

[I like Serena]

Do we always choose the edge,with the minimum weight? (Thinking)

That is one of the ways to build a minimum spanning tree. (Happy)

So..is this a minimum spanning tree? (Thinking)

https://www.physicsforums.com/attachments/3115

Yep! (Nod)

Is it unique?
If not, how many alternatives are there? (Wondering)Anyway, how would you apply the Template algorithm? (Wondering)

 

[evinda]

That is one of the ways to build a minimum spanning tree. (Happy)

Nice! (Yes)

Is it unique?
If not, how many alternatives are there? (Wondering)

No,it isn't unique.. (Shake) There are two alternatives..The other one is this:

View attachment 3116

Or am I wrong? (Thinking)

Anyway, how would you apply the Template algorithm? (Wondering)

Α={}
A isn't a connected tree
Α={(Α,Β)}
A isn't a connected tree
Α={(Α,Β),(Β,Ε)}
A isn't a connected tree
Α={(Α,Β),(Β,Ε),(E,C)}
A isn't a connected tree
A={(Α,Β),(Β,Ε),(E,C),(C,F)}
A isn't a connected tree
A={(Α,Β),(Β,Ε),(E,C),(C,F),(A,D)}

So,a minimum spanning tree is the tree with the edges:
(Α,Β),(Β,Ε),(E,C),(C,F),(A,D)Am I right? (Thinking)

 

[I like Serena]

No,it isn't unique.. (Shake) There are two alternatives..The other one is this:

Or am I wrong? (Thinking)

Yes. That is also a minimum spanning tree!
... but I think there is also a third one. (Wondering)

Α={}
A isn't a connected tree
Α={(Α,Β)}
A isn't a connected tree
Α={(Α,Β),(Β,Ε)}
A isn't a connected tree
Α={(Α,Β),(Β,Ε),(E,C)}
A isn't a connected tree
A={(Α,Β),(Β,Ε),(E,C),(C,F)}
A isn't a connected tree
A={(Α,Β),(Β,Ε),(E,C),(C,F),(A,D)}

So,a minimum spanning tree is the tree with the edges:
(Α,Β),(Β,Ε),(E,C),(C,F),(A,D)Am I right? (Thinking)

Yup!
That is one way to execute the Template algorithm.

Could you also do it in another way? (Thinking)
(Other than making a different choice for the 4-edge.)

 

[evinda]

Yes. That is also a minimum spanning tree!
... but I think there is also a third one. (Wondering)
Could you also do it in another way? (Thinking)
(Other than making a different choice for the 4-edge.)

I didn't find an other spanning tree with weight $16$.. (Sweating)

For which edge could I make a different choice? (Thinking)

 

[I like Serena]

I didn't find an other spanning tree with weight $16$.. (Sweating)

Well... node (d) has 3 edge that each have weight 4.
I think you can pick either one (but only one) of them...

For which edge could I make a different choice? (Thinking)

All of them.

For executing the Template algorithm, you can pick any order you like.
Just as long as you only add edges that actually belong to specific minimum spanning tree. Those are secure.

However, to find secure edge without knowing the tree already, you need a more specific algorithm.
Like Prim's algorithm, or Kruskal's algorithm. (Thinking)

 

[evinda]

Well... node (d) has 3 edge that each have weight 4.
I think you can pick either one (but only one) of them...

A ok.. (Nod) So,this is an other spanning tree,right?

View attachment 3120

In this case, we execute the Template algorithm,like that:

A={}
A isn't a connected tree
A={(A,B)}
A isn't a connected tree
A={(A,B),(B,D)}
A isn't a connected tree
A={(A,B),(B,D),(B,E)}
A isn't a connected tree
A={(A,B),(B,D),(B,E),(E,C)}
A isn't a connected tree
A={(A,B),(B,D),(B,E),(E,C),(C,F)}

Right? (Thinking)

All of them.

For executing the Template algorithm, you can pick any order you like.
Just as long as you only add edges that actually belong to specific minimum spanning tree. Those are secure.

However, to find secure edge without knowing the tree already, you need a more specific algorithm.
Like Prim's algorithm, or Kruskal's algorithm. (Thinking)

I understand! (Sun)

 

[I like Serena]

A ok.. (Nod) So,this is an other spanning tree,right?

Right? (Thinking)

I understand! (Sun)

Yep, yep, and good! (Mmm)

 

[evinda]

Yep, yep, and good! (Mmm)

Great! Thanks a lot! (Cool)