图行算法 [英] Graph travelling algorithm

问题描述

我有一个有趣的图 - 理论问题。我给出一个树T有n个节点和一组边。 T是，当然，无向。每个边缘具有重量，表示多少（至少）倍它必须被访问。我们从节点漫步使用边缘节点，任务是找到所需的步骤最少数量，以满足上述条件。我可以从任何节点开始。

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）

1 - 2 (1)

2 - 3（1）

2 - 3 (1)

3 - 4（2）

3 - 4 (2)

4 - 5（1）

4 - 5 (1)

4 - 6（1）

4 - 6 (1)

我们需要8个步骤走这棵树。这是例如：1-> 2-> 3-> 4-> 3-> 4-> 5-> 4-> 6

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?

推荐答案

添加额外的边缘对应于每个边的权重的图。 （也就是说，如果A-> B的权重为3，那么你的图应该包括A和B之间3无向边连接）。

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.

一个欧拉踪迹可以被关闭（如果start ==完）或打开（如果开始！=结束）。

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

关闭道存在，如果所有节点都均匀度。

Closed trails exist if all nodes have even degree.

开放式创新存在，如果除2所有节点都均匀度。

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.

这样做的一种方法是执行在树的深度优先搜索，并跟踪边缘可以添加到每个子树的最小数目，以便它具有0,1，或2个顶点的奇数度。这应该采取时间线性在树中节点的数目。

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.

这Python的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) )

这篇关于图行算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！