11

我有一个有趣的图论问题。我得到一棵树 T，它有 n 个节点和一组边。当然，T 是无向的。每条边都有权重，表示它必须被访问多少次（至少）。我们正在使用边从一个节点到另一个节点，任务是找到满足上述条件所需的最少步骤。我可以从任何节点开始。

例如，这棵树（括号中的边权重）：

1 - 2 (1)

2 - 3 (1)

3 - 4 (2)

4 - 5 (1)

4 - 6 (1)

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

我不知道如何处理这个算法。是否有可能找到这个最佳游览，或者我们不能直接找到这个最小数量？

4

1 回答 1

6

根据每条边的权重向图形添加额外的边。（即如果 a->b 的权重为 3，那么您的图形应该包括 a 和 b 之间的 3 个无向边连接）。

那么你试图找到的就是这张图上的欧拉轨迹。

欧拉轨迹可以是封闭的（如果 start==end）或开放的（如果 start!=end）。

如果所有节点的度数相等，则存在闭合路径。

如果除 2 之外的所有节点都具有偶数度，则存在开放路径。

可以使用 Fleury 算法找到路径（如果速度太慢，也存在更快的线性算法）。

如果您的图不满足欧拉轨迹的要求，则只需添加最少数量的额外边，直到满足。

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

示例代码

此 Python 代码计算图的最短步数。（要构建图，您应该将其视为有根图，并为远离根的每条边添加边）

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) )
于 2012-11-25T18:57:48.613 回答