1

$$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 ?

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:

  • 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[u]=\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?

evinda
  • 7,823
  • 2
    The reason one can calculate the diameter in this way is that for all trees $T$, the following holds: For any vertex $v$ in $T$, and any vertex $u$ furthest from $v$, and any vertex $w$ furthest from $u$, the diameter of $T$ is $\delta(u,w)$. I don't recall if this result is "named" or not. – D Poole Aug 29 '14 at 18:47
  • @DPoole But..why does it hold? Could you explain it to me? – evinda Aug 30 '14 at 21:58

1 Answers1

1

I tried to find this result online to no avail. If someone knows where this is originally proved, please let me know and I'll edit this post.

Let $s$ be some generic vertex of the tree $T$. Let $u$ be a vertex so that $$ \delta(s,u)=\max_v \delta(s,v) $$ and $w$ be a vertex so that $$ \delta(u,w)=\max_v \delta(u,v). $$ So we want to show that $\delta(u,w)$ is the diameter of $T$. One important fact that we'll be using is that between any two vertices in a tree, there is a $unique$ path between them.

Suppose that $P:(u=v_0, v_1, \ldots, v_{\ell}=w)$ are the vertices, in order, of the path from $u$ to $w$. We partition the vertices based on which $v_i$ they are closest to. In particular, $V_i:=\{v \in V: \delta(v,v_i) = \min_j\delta(u,v_j)\}$. Note that these $V_i$ are disjoint (or else there would be cycles). I claim that for each $0\leq i \leq \ell$, $$d_i:=\max_{v \in V_i} \delta(v_i, v) \leq \min\{i, \ell-i\}.$$

First, let $k$ be so that $s \in V_k$. Note that $k \geq \ell/2$ or else $w$ would be further than $s$ than $u$. So for $k$, we only need to show that $d_k \leq \ell-k$.

For $i \neq k$, if $d_i >i$, then there exists a vertex $v \in V_i$, so that the path from $s$ to $v$, which goes from $s$ to $v_k$ to $v_i$ to $v$ is longer than the path from $s$ to $u$, which is a contradiction.

Now if there is a $d_i$ so that $d_i > \ell-i$, then there would be a path from $u$ to $v_i$ to this vertex which has length longer than the path from $u$ to $w$, which also is a contradiction.

To finish this proof off, we need to show why this condition on $d_i$ forces the diameter to be $\ell$. Suppose that $v\in V_i$ and $t \in V_j$ for some $0\leq i \leq j \leq \ell$. Then there is a path from $v$ to $v_i$ of length at most $i$, a path from $v_i$ to $v_j$ of length $j-i$, and a path from $v_j$ to $t$ of length at most $\ell-j$. Adding these paths together, gives us a walk of length at most $\ell$.

D Poole
  • 2,762