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^{'}$ 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^{'}$. Therefore, length of path $P^{'}$ 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^{'}$ 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{align*} P_1 & : m, u_1, u_2, \dots, u_k, n \\ P_2 & : m, v_1, v_2, \dots, v_j, n \end{align*}$$

where $j \neq 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 \geq j$) that is in the path $P_2$. Then $u_k = v_l$ for some $l \geq 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) \leq \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) \leq \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})$

$"\\begin{algorithm}\n\\caption{Maximum Distance in Tree}\n\\begin{algorithmic}\n\\Procedure{MaxDistance}{$\\mathcal{G}$}\n\\State $u \\gets$ \\Call{BFS}{$\\mathcal{G}, v$} \\Comment{$v$ is any arbitrary node in $\\mathcal{N}$}\n\\State $d \\gets$ \\Call{BFS}{$\\mathcal{G}, u$}\n\\State \\Return $d$\n\\EndProcedure\\Procedure{BFS}{$\\mathcal{G}, s$}\n\\State $Q \\gets$ empty queue\n\\State $\\text{dist}[v] \\gets \\infty$ for all $v \\in \\mathcal{N}$\n\\State $\\text{dist}[s] \\gets 0$\n\\State $Q.\\text{Enqueue}(s)$\n\\State $f \\gets s$\n\\While{$Q$ is not empty}\n\\State $u \\gets Q.\\text{Dequeue}()$\n\\State $f \\gets u$\n\\ForAll{$v \\in \\mathcal{N}$ such that $(u, v) \\in \\mathcal{E}$}\n\\If{$\\text{dist}[v] = \\infty$}\n\\State $\\text{dist}[v] \\gets \\text{dist}[u] + 1$\n\\State $Q.\\text{Enqueue}(v)$\n\\EndIf\n\\EndFor\n\\EndWhile\n\\State \\Return $f$\n\\EndProcedure\n\\end{algorithmic}\n\\end{algorithm}"$

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