# Graph theory algorithm

I've got an interesting graph-theory problem. I am given a tree $T$ with $n$ nodes and a set of edges. $T$ is, of course, undirected. Each edge has weight that indicates how many times (at least) it has to be visited. We are strolling from node to node using edges and the task is to find minimal number of needed steps to satisfy above conditions. I can start from any node.

For example, this tree (edge weight along edge): we need $8$ steps to walk this tree. That are for example: $4\to5\to6\to5\to3\to5\to3\to2\to1$

I don't know how to approach this algorithm. Is it possible to find this optimal tour or can we find this minimal number not directly?

• I planted the tree. Please make sure I didn't break your tree. – Frenzy Li Nov 25 '12 at 11:49
• @FrenzYDT., thank you! – ray Nov 25 '12 at 11:54
• Even if irrelevant, I'm curious how did you deduce that :) – ray Nov 25 '12 at 12:10
• @FrenzYDT. Actually, in any tree you can pick an optimal path in such a way that every edge $(a,b)$ is only visited in this fashion ($a \to b \to a \to \ldots$). But it doesn't guarantee that reducing the weight by 2 will reduce the resulting path by 2, because the optimal path can actually visit an edge many more times than is required by its weight. – Dan Shved Nov 25 '12 at 12:18
• @FrenzYDT. That tree looks oddly familiar. Is it generated by Mathematica? – Yong Hao Ng Nov 27 '12 at 14:37

First of all, here is how the first attempt at a recursive solution would normally go. For a rooted tree $T$ with root $r$, let's call $f(T)$ the minimal length of a path that starts at $r$ and visits every edge as many times as needed. Now, if we suppose that $f$ can be implemented as a recursive function, then there should be a way to somehow calculate $f(T)$ using values $f(T_1),\,f(T_2),\,\ldots,\,f(T_k)$ that were calculated recursively for the subtrees $T_i$ whose roots are children of $r$. But there's no obvious way to do this, and that's where one would usually give up the recursive approach.
But it can still be done if approached wisely, using this idea: instead of calculating only $f$ as a recursive function, calculate simultaneously $f$ and $g$, where $g(T)$ is the minimal length of a path that visits each edge of $T$ the required amount of times, starts at $r$ and also ends at $r$. I say that $g(T)$ can be calculated recursively from values $g(T_i)$, and $f(T)$ can also be calculated recursively from values $f(T_i)$ and $g(T_i)$.