snorkel's blog

By snorkel, history, 3 years ago, In English

What is the proof of the fact that: if we want to traverse the tree with the minimal cost then we should traverse through the diameter, so visit diameter edges once and visit other edges twice.

This is kinda obvious, but I can't find the proof of it.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

It's obvious that when you traverse the tree, you start in some vertex $$$u$$$, visit all other vertexes and then finish in some other vertex $$$v$$$. You obviously have to traverse the edges which are not between $$$u$$$ and $$$v$$$ at least twice each, because otherwise you'd get stuck in a subtree. So you have to make at least $$$2(n-1) - \rho(u, v)$$$ moves ($$$\rho$$$ is the distance function), and obviously this bound is reachable with a simple DFS. So to minimize the moves number, you have to maximize $$$\rho(u, v)$$$, and this happens when you use the diameter.

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Don't know whether there's an easier proof, but I would prove it like that:

Consider a multigraph where each edge of the original tree occurs the same number of times as the number of times we go along this edge in our minimum cost path. Our path is an eulerian walk in this graph, so each vertex (except for two arbitrarily chosen vertices) should have an even degree.

It's quite obvious that some edges should have $$$1$$$ copy, other edges — $$$2$$$ copies (if the number of copies of some edge is greater than $$$2$$$, just reduce it by $$$2$$$, and the answer becomes better). How can we choose the edges with exactly one copy? There should be only two vertices adjacent to exactly one edge with one copy (otherwise, there won't be an eulerian walk). So, if we consider only edges with one copy, they should form a forest with exactly two leaves — and the only case when a forest has only two leaves is when all its edges form a single simple path. So, all edges with one copy form a path, and all other edges have two copies.

Let the endpoints of the path be vertices $$$x$$$ and $$$y$$$. If the edges along the path $$$x-y$$$ have only one copy, then the total weight of the graph (and the total length of the eulerian walk) is $$$2\sum w_i - distance(x, y)$$$, so, to minimize the total weight, we have to maximize the length of this path.