Graph travelling algorithm

Question

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

1 - 2 (1)

2 - 3 (1)

3 - 4 (2)

4 - 5 (1)

4 - 6 (1)

we need 8 steps to walk this tree. That are for example: 1->2->3->4->3->4->5->4->6

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?

Answer 1

Add extra edges to your graph corresponding to the weight of each edge. (i.e. if a->b has weight 3, then your graph should include 3 undirected edges connections between a and b).

Then what you are trying to find is called an Eulerian trail on this graph.

A Eulerian trail can be closed (if start==end) or open (if start!=end).

Closed trails exist if all nodes have even degree.

Open trails exist if all nodes except 2 have even degree.

Paths can be found using Fleury’s Algorithm (faster linear algorithms also exist if this is too slow).

If your graph does not satisfy the requirements for an Eulerian trail, then simply add the smallest number of extra edges until it does.

One way of doing this is to perform a depth first search over the tree and keep track of the minimum number of edges that you can add to each subtree in order that it has 0,1, or 2 vertices of odd degree. This should take time linear in the number of nodes in the tree.

EXAMPLE CODE

This Python code computes the shortest number of steps for a graph. (To construct the graph you should consider it as a rooted graph and add edges for each edge going away from the root)

from collections import defaultdict
D=defaultdict(list)
D[1].append((2,1))
D[2].append((3,1))
D[3].append((4,2))
D[4].append((5,1))
D[4].append((6,1))
BIGNUM=100000

class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if not self.memo.has_key(args):
            self.memo[args] = self.fn(*args)
        return self.memo[args]

@Memoize
def min_odd(node,num_odd,odd,k):
    """Return minimum cost for num_odd (<=2) odd vertices in subtree centred at node, and using only children >=k

    odd is 1 if we have an odd number of edges into this node from already considered edges."""
    edges=D[node]
    if k==len(edges):
        # No more children to consider, and no choices to make
        if odd:
            return 0 if num_odd==1 else BIGNUM
        return 0 if num_odd==0 else BIGNUM

    # We decide whether to add another edge, and how many of the odd vertices to have coming from the subtree
    dest,w0 = edges[k]
    best = BIGNUM
    for extra in [0,1]:
        w = w0+extra
        for sub_odd in range(num_odd+1):
            best = min(best, w + min_odd(dest,sub_odd,w&1,0) + min_odd(node,num_odd-sub_odd,(odd+w)&1,k+1) )

    return best

root = 1
print min( min_odd(root,2,0,0),min_odd(root,0,0,0) )