--- date: '2024-03-22' description: assignment on tree distance proofs, path uniqueness in undirected trees, triangle inequality, and maximum distance algorithm using bfs. id: A8 modified: 2026-06-05 15:08:41 GMT-04:00 tags: - sfwr2c03 title: Trees path created: '2024-03-22' published: '2024-03-22' pageLayout: default slug: thoughts/university/twenty-three-twenty-four/sfwr-2c03/a8/A8 permalink: https://aarnphm.xyz/thoughts/university/twenty-three-twenty-four/sfwr-2c03/a8/A8.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- ## 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$. > \[!question\] 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$ > \[!question\] 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$ > \[!question\] 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) $$ > \[!question\] 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(G\mathcal{G})

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

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

4:

5:return dd

6:end procedure

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

8:Q←Q \gets empty queue

9:dist[v]←∞\text{dist}[v] \gets \infty for all v∈Nv \in \mathcal{N}

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

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

12:f←sf \gets s

13:while QQ is not empty do

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

15:f←uf \gets u

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

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

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

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

20:end if

21:end for

22:end while

23:

24:return ff

25:end procedure