patternMinor
Prove that the total distance is minimised (when travelling across the longest path)
Viewed 0 times
totalacrosspaththedistancetravellingprovethatwhenlongest
Problem
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
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
Solution
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.
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.
Context
StackExchange Computer Science Q#105534, answer score: 4
Revisions (0)
No revisions yet.