MHB Calculate the diameter of a tree

[evinda]

Hey! (Smile)

$$T=(V,E) \text{ tree }$$
$$\text{diameter of a tree } = \max_{u,v \in V} \delta(u,v)$$

$$\delta(u,v)=\text{the length of the shortest path from the vertex u to the vertex v}$$

How can we calculate the diameter of a tree,when we are given the algorithm of the Breadth-first-search ? (Wait)

    Breadthfirstsearch(G,s)
    for each u ∈ V \ {s}
         color[u]<-white
         d[u]<-oo
         p[u]<-Ø
    color[s]<-gray
    d[s]<-0
    p[s]<-Ø
    Q<-Ø 
    Insert(Q,s)
    while Q ≠ Ø
           u<-Del(Q)
           for each v  ∈ Adj(u)
              if color[v]=white then
                 color[v]<-gray
                 d[v]=d[u]+1
                 p[v]<-u
                 Insert(Q,v)
    
           color[u]<-black

According to my notes,we could do the following:

1. We implement the Breadth-first search from a given initial node $s$.
   We calculate $d$ for all the vertices.
   Let $u$ the vertex,such that: $$\delta(s,u)=d=\max_{v \in V} d[v]$$
   
   [*] We implement the Breadth-first search with the vertex $u$,as the initial node.
   Let $w$ the vertex,such that:
   $$\delta(u,w)=d[w]=\max_{v \in V} d[v]$$
   

Then,the diameter of $T$ is equal to $\delta(u,w)$.

Could you explain me why we calculate the diameter in this way? (Thinking)

 

[I like Serena]

Hey! (Smile)

$$T=(V,E) \text{ tree }$$
$$\text{diameter of a tree } = \max_{u,v \in V} \delta(u,v)$$

$$\delta(u,v)=\text{the length of the shortest path from the vertex u to the vertex v}$$

How can we calculate the diameter of a tree,when we are given the algorithm of the Breadth-first-search ? (Wait)

    Breadthfirstsearch(G,s)
    for each u ∈ V \ {s}
         color[u]<-white
         d[u]<-oo
         p[u]<-Ø
    color[s]<-gray
    d[s]<-0
    p[s]<-Ø
    Q<-Ø 
    Insert(Q,s)
    while Q ≠ Ø
           u<-Del(Q)
           for each v  ∈ Adj(u)
              if color[v]=white then
                 color[v]<-gray
                 d[v]=d[u]+1
                 p[v]<-u
                 Insert(Q,v)
    
           color[u]<-black

According to my notes,we could do the following:

1. We implement the Breadth-first search from a given initial node $s$.
   We calculate $d$ for all the vertices.
   Let $u$ the vertex,such that: $$\delta(s,u)=d=\max_{v \in V} d[v]$$
   
   [*] We implement the Breadth-first search with the vertex $u$,as the initial node.
   Let $w$ the vertex,such that:
   $$\delta(u,w)=d[w]=\max_{v \in V} d[v]$$
   

Then,the diameter of $T$ is equal to $\delta(u,w)$.

Could you explain me why we calculate the diameter in this way? (Thinking)

Hi evinda! (Blush)

The diameter is the length of the longest path in the tree.
To find it, we need to find the ends of this longest path.

That is a 2-step process.
First we start at an arbitrary node ($s$) and find the furthest node from it ($u$).
This is one of those 2 ends of the longest path.
When we find the furthest node from $u$, we have found the longest path.
Its length is the diameter. (Mmm)

 

[evinda]

Hi evinda! (Blush)

The diameter is the length of the longest path in the tree.
To find it, we need to find the ends of this longest path.

That is a 2-step process.
First we start at an arbitrary node ($s$) and find the furthest node from it ($u$).
This is one of those 2 ends of the longest path.
When we find the furthest node from $u$, we have found the longest path.

Could you explain me further why we find the shortest distance from the node $s$ to the node $v$ and then the shortest distance from the node $v$ to the node $w$? (Thinking)

Its length is the diameter. (Mmm)

So,shouldn't the diameter be equal to $\delta(s,u)+ \delta(u,w)$ ?

 

[I like Serena]

Could you explain me further why we find the shortest distance from the node $s$ to the node $v$ and then the shortest distance from the node $v$ to the node $w$? (Thinking)

So,shouldn't the diameter be equal to $\delta(s,u)+ \delta(u,w)$ ?

Suppose we pick an example.

Say:

Suppose we pick (1) as node $s$.
What would $u$ and $w$ be? (Thinking)

 

[evinda]

Suppose we pick an example.

Say:Suppose we pick (1) as node $s$.
What would $u$ and $w$ be? (Thinking)

I wanted to implement now the Breadth-first search,with the node $(1)$ as node $(s)$.
At the beginning,we have:

View attachment 3082

and then:

View attachment 3083

But..then, does the queue remain empty,because of the fact that the node $1$ has no children or is it: $Adj(1)=\{ 3 \}$ ? (Thinking)

 

[I like Serena]

I wanted to implement now the Breadth-first search,with the node $(1)$ as node $(s)$.
At the beginning,we have:

View attachment 3082

and then:

View attachment 3083

But..then, does the queue remain empty,because of the fact that the node $1$ has no children or is it: $Adj(1)=\{ 3 \}$ ? (Thinking)

With the edges directed as they are, you are quite right.
Good! (Smile)

So, to make the example more interesting, let's pretend that all those directional edges are really bidirectional edges.
What would you get then? (Wondering)

 

[evinda]

So, to make the example more interesting, let's pretend that all those directional edges are really bidirectional edges.
What would you get then? (Wondering)

Picking $(1)$ as node $s$,I got the following:

View attachment 3084

So, $u=13$ and $\delta(s,u)=5$

Then,picking $(13)$ as node $s$,I got:

View attachment 3085

So,the diameter is equal to $6$,since this is the length of the longest path that exists at the tree,right? (Thinking)

 

[I like Serena]

Picking $(1)$ as node $s$,I got the following:

So, $u=13$ and $\delta(s,u)=5$

Then,picking $(13)$ as node $s$,I got:

So,the diameter is equal to $6$,since this is the length of the longest path that exists at the tree,right? (Thinking)

Right! (Smile)

Actually, in the 2nd step, you shouldn't have picked (13) as $s$.
It is still called $u$ and you're supposed to find $w$.

Could you explain me further why we find the shortest distance from the node $s$ to the node $v$ and then the shortest distance from the node $v$ to the node $w$? (Thinking)So,shouldn't the diameter be equal to $\delta(s,u)+ \delta(u,w)$ ?

Can you answer your own questions now? (Wondering)

 

[evinda]

Actually, in the 2nd step, you shouldn't have picked (13) as $s$.
It is still called $u$ and you're supposed to find $w$.

Oh yes,you are right! (Nod)

Can you answer your own questions now? (Wondering)

I will give it a try.. (Wasntme)

Could you explain me further why we find the shortest distance from the node s to the node v and then the shortest distance from the node v to the node w?

We choose an initial node $s$.
Then,we find the distance from $s$ to all the other nodes and call $u$,the node to which the distance from $s$ is the greatest.
Now,we start from $u$ and want to find a node,in order the length of the path to be the greatest possible.

So,the diameter of a tree is the height of the left subtree plus the height of the right subtree.
With $\delta(s,u)$ ,we find a node $u$, to which the distance from the root $s$ is the greatest .The node $u$ will be at the last level of one of the subtrees. Then,we are looking for a vertex $w$,that has the greatest distance from the vertex $v$,so it will be at the last level of the other subtree.

Now,we have found at least two nodes from the last level of both the left and right subtree and the length of the path from the node of the last level of the left subtree to the one of the right subtree will be the longest path,and also the diamater of the tree.

So,shouldn't the diameter be equal to δ(s,u)+δ(u,w) ?

No, adding $\delta(s,u)$ by $\delta(u,w)$ we add twice the length of the path from the vertex $s$ to the vertex $u$.Is my reasoning ok? (Blush)

 

[I like Serena]

I will give it a try.. (Wasntme)

We choose an initial node $s$.
Then,we find the distance from $s$ to all the other nodes and call $u$,the node to which the distance from $s$ is the greatest.
Now,we start from $u$ and want to find a node,in order the length of the path to be the greatest possible.

Good! :)

So,the diameter of a tree is the height of the left subtree plus the height of the right subtree.

That doesn't sound quite right. It's not true for our example.
It would only be true for a node that is already on the longest path.
And then there might still be more than 2 sub trees.

With $\delta(s,u)$ ,we find a node $u$, to which the distance from the root $s$ is the greatest .The node $u$ will be at the last level of one of the subtrees. Then,we are looking for a vertex $w$,that has the greatest distance from the vertex $v$

Yes! (Yes)

so it will be at the last level of the other subtree.
Now,we have found at least two nodes from the last level of both the left and right subtree

No.

and the length of the path from the node of the last level of the left subtree to the one of the right subtree will be the longest path,and also the diamater of the tree.

Yes.

No, adding $\delta(s,u)$ by $\delta(u,w)$ we add twice the length of the path from the vertex $s$ to the vertex $u$.

You do add twice a length, but it's the length from $s$ to the first common node in both paths. (Thinking)

 

[evinda]

That doesn't sound quite right. It's not true for our example.
It would only be true for a node that is already on the longest path.
And then there might still be more than 2 sub trees.

So,would it only be true for $s=(8)$ ? (Thinking)

No.

Why? (Thinking)

You do add twice a length, but it's the length from $s$ to the first common node in both paths. (Thinking)

A ok.. (Nod)

 

[I like Serena]

So,would it only be true for $s=(8)$ ? (Thinking)

Node (8) is the root, which happens to be part of the longest path.
But this is not necessarily the case.

However, you could treat any node that is on the longest path as the root of the tree.
In that case the diameter is the sum of the height of 2 sub trees of this node. (Nerd)

Why? (Thinking)

Because your statement about a left and right subtree is not correct.
That's why what you write here about the left and right subtree is also not correct. (Wasntme)