6
$\begingroup$

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):

Mathematica graphics

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?

  • 3
    I planted the tree. Please make sure I didn't break your tree.2012-11-25
  • 0
    @FrenzYDT., thank you!2012-11-25
  • 0
    Even if irrelevant, I'm curious how did you deduce that :)2012-11-25
  • 0
    @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.2012-11-25
  • 0
    @DanShved You are correct.2012-11-25
  • 0
    @FrenzYDT. I don't really understand your question: are you talking about rooted trees or usual trees? What are the $\ldots$ between 4 and 4? Please clarify your question.2012-11-25
  • 0
    Discussion result with @Dan: he provided with a counter-example to "optimal path always shortens when one weight is reduced by 2".2012-11-25
  • 1
    @FrenzYDT. That tree looks oddly familiar. Is it generated by Mathematica?2012-11-27

1 Answers 1