Trees path

Problème 1.

Let $\mathcal{G}=(\mathcal{N},\mathcal{E})$ be an undirected tree (graph $G$ is undirected, connected, and has $|\mathcal{N}|=|\mathcal{E}|+1$ if we count edges $(v,w)$ and $(w,v)$ as the same edge). Let $m,n\in \mathcal{N}$. We say that the distance between $m$ and $n$, denoted by dist(m,n), is the length of the shortest path between $m$ and $n$.

P1.1

Show that $\text{dist}(m,n)=\text{dist}(n,m)$

An undirected tree $\mathcal{G}$ has the following properties:

1. $\mathcal{G}$ is connected and acyclic
2. A tree with $n$ nodes has $n-1$ edges
3. In a tree, there is a unique path between any two vertices.

Let $m$ and $n$ be two arbitrary vertices in the $\mathcal{G}$. There exists a unique path $P$ from $m$ to $n$.

Let the vertices along the path $P$ be: $m,v_1,v_2,\dots ,v_k,n$. The length of path is $k+1$, which is the number of edges

Let the vertices along the path $P^{{}^{\prime }}$ be: $n,v_k,\dots ,v_2,v_1,m$. Since $\mathcal{G}$ is an undirected graph, each edge $(v_i,v_{i+1})$ in $P$ corresponds to the same edge $(v_{i+1},v_i)$ in $P^{{}^{\prime }}$. Therefore, length of path $P^{{}^{\prime }}$ is also $k+1$

dist(m, n) denotes the shortest path from m to n, and dist(n, m) denotes the shortest path from n to m. Since there is one unique path between m and n in the tree, both $P$ and $P^{{}^{\prime }}$ are shortest paths between m and n, with length $k+1$

Therefore $\text{dist}(m,n)=\text{dist}(n,m)$ $\square$

P1.2

Prove that there is a unique path without repeated nodes and edges from node $m$ to node $n$ with length dist(m,n)

Since $\mathcal{G}$ is an undirected tree, there is a unique path between any two vertices. Let $m$ and $n$ be two arbitrary vertices in the $\mathcal{G}$. There exists a simple path $P$ from $m$ to $n$.

Suppose there are two different simple paths connecting $m$ and $n$:

$$\begin{array}{rl}{P}_1& :m,u_1,u_2,\dots ,u_k,n\\ P_2& :m,v_1,v_2,\dots ,v_j,n\end{array}$$

where $j\ne k$. Since the paths are different and since $P_2$ is a simple path, $P_1$ must contain an edge that isn’t in $P_2$

Let $j\ge 1$ the first index for which the edge $\{u_{j-1},u_j\}$ of $P_1$ is not in $P_2$. Then $u_{j-1}=v_{j-1}$.

Let $u_k$ be the first vertex in path $P_1$ after $u_{j-1}$ (that is $k\ge j$) that is in the path $P_2$. Then $u_k=v_l$ for some $l\ge j$

We now have two simple path, $Q_1:u_{j-1},\dots ,u_k$ using edges from $P_1$ and $Q_2:v_{j-1},\dots ,v_l$ using edges from $P_2$, between $u_{j-1}=v_{j-1}$ and $u_k=v_l$.

The path $Q_1$ and $Q_2$ have no vertices, edges in common, thus the path from $u_{j-1}$ to $u_k$ along $Q_1$ followed by the path from $v_l$ to $v_{j-1}$ along the reverse of $Q_2$ is a cyclic in $T$, which contradicts the assumption that $T$ is a tree.

Thus, the path from $m$ to $n$ is unique simple path $\square$

P1.3

Prove the triangle inequality $\text{dist}(m,n)\le \text{dist}(m,x)+\text{dist}(x,n)$

Let $m,n,x$ be three arbitrary vertices in the undirected tree $\mathcal{G}$a

There exists a simple unique path $P_1$ from $m$ to $x$ (length is $\text{dist}(m,x)$), a simple unique path $P_2$ from $x$ to $n$ (length is ).

Consider $P$ formed by concatenating $P_1$ and $P_2$. This is a path from $m$ to $n$ that passes through $x$ (length is $\text{dist}(m,x)+\text{dist}(x,n)$)

since $P$ denotes path from $m$ to $n$, and $\text{dist}(m,n)$ denotes the shortest path between $m$ and $n$, we have

$$\text{dist}(m,n)\le \text{length}(P)=\text{dist}(m,x)+\text{dist}(x,n)$$

P1.4

Provide an algorithm that computes the distance $d={\text{max}}_{m,n\in N}\text{dist}(m,n)$ that is the maximum distance between any pair of nodes in $\mathcal{G}$ in $\mathcal{O}(|\mathcal{N}|+\mathcal{E})$

Algorithm 34 Maximum Distance in Tree

1:procedure MaxDistance($\mathcal{G}$)

2:$u \gets$ BFS($\mathcal{G}, v$)//$v$ is any arbitrary node in $\mathcal{N}$

3:$d \gets$ BFS($\mathcal{G}, u$)

4:

5:return $d$

6:end procedure

7:procedure BFS($\mathcal{G}, s$)

8:$Q \gets$ empty queue

9:$\text{dist}[v] \gets \infty$ for all $v \in \mathcal{N}$

10:$\text{dist}[s] \gets 0$

11:$Q.\text{Enqueue}(s)$

12:$f \gets s$

13:while $Q$ is not empty do

14:$u \gets Q.\text{Dequeue}()$

15:$f \gets u$

16:for all $v \in \mathcal{N}$ such that $(u, v) \in \mathcal{E}$ do

17:if $\text{dist}[v] = \infty$ then

18:$\text{dist}[v] \gets \text{dist}[u] + 1$

19:$Q.\text{Enqueue}(v)$

20:end if

21:end for

22:end while

23:

24:return $f$

25:end procedure