4
$\begingroup$

Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have to return where I started.

As my specification is not really clear I made up an example: Consider the graph (which is a tree here - undirected weighted acyclic graph) to have nodes as cities and edges as roads between cities. I need to deliver something to every city (visit every node at least once). I can start from any city and end at any city that I choose to.

I read the following result. Find the two cities in the graph that are the farthest apart (call them $c1$ and $c2$). Start from one of them ($c1$ or $c2$), visit every other city along the way until I reach ($c2$ or $c1$). This minimises the total distance to travel.

How should I prove that this is the minimum distance ?

I attempted the following. I have the final route and I call edges, $m_1, m_2, ..., m_i$ and $e_1, e_2, ..., e_j$. Where $m_1, m_2, ..., m_i$ are the edges along the cities that are the farthest apart ($c1$ and $c2$) and $e_1, e_2, ..., e_j$ are everything else in the graph. As I start from $c1$, I travel along edges labelled m exactly once and everything else labelled e is a digression and go back and forth twice on those edges, before I reach $c2$.

We know that $m_1, m_2, ..., m_i$ and $e_1, e_2, ..., e_j$ taken together include all the edges on the graph (as it is a tree, there's only a unique path between every two nodes). So the distance I travel could be given as $2(e_1 + e_2 + .... + e_j) + (m_1 + m_2 + ... + m_i)$.

I need to prove that this sum is less than every other route that I can take to reach all the cities. My intuition says that this has to be the shortest route. I feel that have to use the fact that $(m_1 + m_2 + ... + m_i)$ is the maximum between any two nodes in the graph somehow (is that called the diameter ?), and arrive at a contradiction.

This is the kind of picture I have in my mind (red edges are in ($m_1, m_2, ..., m_i$) and the grey ones are everything else),

enter image description here

That graph is still a tree (please ignore the arrow head in the edges that show how I decide to travel). I don't to where to go from here. I would appreciate a proof that is simple to understand (This is not a homework or anything related to coursework.)

$\endgroup$
4
$\begingroup$

Let $x$ be a vertex of your tree and consider a shortest route that visits every vertex and returns to $x$. It's easy to see that, regardless of the choice of $x$, any minimal route walks along every edge exactly twice: it must use each edge at least twice, or it wouldn't be able to get back to $x$; if it uses an edge more than twice, you can rearrange to avoid the backtracking. Therefore, all such minimal routes have the same length, regardless of the choice of $x$. Call that length $L$ (which is $2(n-1)$ if the tree is unweighted and there are $n$ vertices, but this isn't important).

Now, given a minimal route from $x$, let $y$ be the last vertex to be visited for the first time (i.e., the vertex which, when you first visit it, you say "Aha, now I've been to every vertex!"). The minimal route visits every vertex on its way from $x$ to $y$, and then returns immediately to $x$ along the unique shortest path. Let $L_{xy}$ be the length of the walk taken from $x$ to $y$. We know that $L=L_{xy}+d(x,y)$, and $L$ and $d(x,y)$ don't depend on how we got to $y$, so $L_{x,y}$ also doesn't depend on the route and we can say that $L_{xy}$ is the length of any minimal walk from $x$ to $y$ that visits every vertex.

The vertex $y$ must be a leaf: if it wasn't, when you first visited $y$, you wouldn't have visited any of the vertices "beyond" it. Further, for any leaf $z$ of the tree, there are minimal routes from $x$ back to itself such that $z$ is the last vertex visited for the first time: let $v_1v_2\dots v_t$ be the path from $v_1=x$ to $z=v_t$ and don't go to $v_{i+1}$ until you've already visited every other descendant of $v_i$.

So, to get the longest walk from $x$ that visits every vertex, pick a route whose $y$ is the leaf at greatest distance from $x$. None of the above depends on which vertex was chosen as $x$, $L_{xy}=L-d(x,y)$ is minimized by choosing $x$ and $y$ to be the vertices at greatest possible distance in the tree, which are both leaves.

$\endgroup$
  • $\begingroup$ Thanks David. The $d(x,y)$ you use is the shortest path between $x$ and $y$ isn't it ?! Shortest because once I'm done, I want to retract in the shortest possible way. And, the shortest path between any two vertices that is the greatest should be the diameter. I want to find the largest shortest distance because I want to minimise $L$. $\endgroup$ – rranjik Mar 13 at 20:22
  • 1
    $\begingroup$ @rranjik Yes, $d(x,y)$ is distance. But you’re trying to minimise $L_{xy}$, so you need to maximise $d$. $\endgroup$ – David Richerby Mar 13 at 20:51
  • $\begingroup$ Oops! Minimise $L_{xy}$ not $L$. $L$ is just a constant for the given graph as you mentioned. Thanks for clarifying. $\endgroup$ – rranjik Mar 13 at 20:56
4
$\begingroup$

Here is a proof rigorous enough that should be easy enough to understand as well.

Let $T=(V,E)$. Let $j$ be a journey that passes every city, starting at city $s$ and finishing at city $f$. Let $t_e$ is the number of times $j$ goes through edge $e$. Let $P$ be the unique path from $s$ to $f$.

Claim 1: $t_e\ge 1$.
Proof: If we remove edge $e$ from $T$, $T$ is separated into two trees that are disconnected to each other. If $t_e\not\ge1$, i.e., $j$ does not include $e$, that means $j$ is disconnected, which is false.

Claim 2: $t_e\ge 2$ if $e\not\in P$.
Proof. Let $e\not\in P$. If we remove edge $e$ from $T$, $T$ is separated into two smaller trees that are disconnected to each other. Denote those two trees $T_1$ and $T_2$. Since $P$ is connected, $P$ is in $T_1$ entirely or $T_2$ entirely. That means both $s$ and $f$ are in $T_1$ or both are in $T_2$. Starting at $s$ in one of the smaller trees, $j$ must go to the other smaller tree through $e$ before returning to $f$ through $e$ again.

The total distance of $j$ is $$\begin{align}{\sum_{e\in E}t_ee}&=\sum_{e\in P}t_ee + \sum_{e\in E\text{ and }e\not\in P}t_ee\\ &=\sum_{e\in E}2e + \sum_{e\in P}(t_e-2)e + \sum_{e\in E\text{ and }e\not\in P}(t_e-2)e\\ &\ge\sum_{e\in E}2e + \sum_{e\in P}(t_e-2)e \\ &\ge\sum_{e\in E}2e - \sum_{e\in P}e \\ &\ge\sum_{e\in E}2e - \text{ diameter of } T \\ \end{align}$$

The other part of the proof is to show the journey can be as short as $\displaystyle{\sum_{e\in E}2e - \sum_{e\in P}e}$ for any path $P$, as indicated by the picture in the question. We can prove by induction on $n$, the number of nodes that is not on $P$. The base case when $n=0$ is clear. For the induction step, we can find a leaf that is not in $P$. (Pick any edge not in $P$, whose removal splits $T$ into two smaller trees. Pick any leaf in the smaller tree that does not contain $P$.) Then we can extend a journey that misses that leaf by inserting into that journey an excursion that goes to that leaf and then returns back.


Here is a related exercise.

Exercise. Prove the following algorithm finds a diameter of a given tree.

  1. Let $u$ be a node.
  2. Find $v$, one of the farthest nodes from $u$.
  3. Find $w$, one of the farthest nodes from $v$.
  4. return the path from $v$ to $w$.
$\endgroup$
  • $\begingroup$ @Apass.Jack Thanks for your time. I appreciate it. This is very rigorous as you mentioned. I was reading it all this time trying to understand. (I'm not really good at understanding a lot of math). Could you please explain the last line of the proof where we use $\sum_{e\in P}e \ge \text{ diameter of } T$ ? Isn't any path in the tree always lesser than or equal to the diameter. So the sum of the edges in $P$ should be at most the diameter right ? $\endgroup$ – rranjik Mar 13 at 20:54
  • $\begingroup$ @rranjik Exactly. $\endgroup$ – Apass.Jack Mar 13 at 21:30
  • $\begingroup$ @Apass.Jack I'm sorry. I still could not understand. I ask, isn't $\sum_{e\in P}e \le \text{ diameter of } T$ always ? Apparently, we are using it the other way around. Could you please explain a little more ? $\endgroup$ – rranjik Mar 13 at 21:35
  • $\begingroup$ @rranjik Did you notice there is negative sign? $-\sum_{e\in P}e \ge -\text{ diameter of } T$ $\endgroup$ – Apass.Jack Mar 13 at 21:37
  • $\begingroup$ Uh-oh sorry! Thank you so much. $\endgroup$ – rranjik Mar 13 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.