Christopher Moore《计算的本质》中柯尼斯堡桥问题的路径数

Question

这应该是一个非常简单的问题。

在 Christopher Moore 的书《计算的本质》第 3 页的

Prologue

中，Konigsberg 问题的可能路径数计算为 $2^n$，其中 $n=7$。

引用：

为简单起见，假设每次我们到达岛屿或河岸时，都有两种不同的离开方式。那么，如果有 $n$ 座桥梁需要跨越，则粗略估计可能的步行次数将为 $2^n$。

我很难理解这个“粗略估计”。

其背后可能的心智模型是什么？

Answer 1

所以我写了一个Python代码来实际枚举人类可能尝试的所有可能不成功的“行走”（也许用铅笔在图表上画）：

def get_remaining_paths(v, edges):
    paths = []
    for i,e in enumerate(edges):
        if v in e:
            edges_next = edges[:]
            edges_next.pop(i)
            if e[0] == v:
                vnext = e[1]
            else:
                vnext = e[0]
            paths_next = get_remaining_paths(vnext, edges_next)
            if len(paths_next) == 0:
                paths.append([(v, vnext)])
            else:
                for p in paths_next:
                    paths.append([(v, vnext)] + p)
    return paths
    
vertices = ['A', 'B', 'C', 'D']
edges = [('A','B'), ('A','B'), ('A','C'), ('A','C'), ('A','D'), ('B','D'), ('C','D')]
all_paths = {v: get_remaining_paths(v, edges) for v in vertices}
all_paths_nums = {v: len(all_paths[v]) for v in vertices}
success = {v: any([len(p)==len(edges) for p in all_paths[v]]) for v in vertices}    
print(all_paths_nums)
print(success)

输出是

{'A': 108, 'B': 90, 'C': 90, 'D': 84}
{'A': False, 'B': False, 'C': False, 'D': False}

这意味着从“A”出发的可能不成功路线数量为 108 条，从“B”出发为 90 条，从“C”出发为 90 条，从“D”出发为 84 条。

所以试验总数为372。当然，都没有成功。

Answer 2

我认为这个估计有缺陷。

假设 G 是一个具有 n 个节点和 m 个桥的图（n 表示节点，m 表示边/桥，因为这是标准的）。

“为简单起见，假设每次我们到达岛屿或河岸时，都有两种不同的离开方式。”

• 那么起始节点有 2 个桥，其他每个节点有 3 个（我们到达的一个，以及引出的两个。
• 因此除了起始节点之外的每个节点的度都是3，并且起始节点的度为2。
• 但是G中没有欧拉行走。除了起始节点之外的每个节点都有3座桥，其中两座在我们第一次到达/离开时用完，第三座要么没有使用，要么让我们在岛上陷入困境。

现在让我们考虑一下确实具有欧拉游走的图。让我们举一个非常基本的例子：n 个顶点（为了方便起见，标记为 1, 2, ..., n），其中每个顶点都连接到顶点 +/- 1，没有环绕。

这里有n-1条边，所以m = n-1。那么估计有2^(n-1)条欧拉游走。实际上，有 2 种：从 1 开始的步行，以及从 n 开始的反向步行。

此外，对于任何图来说 2^m 都是一个奇怪且大的估计。也就是说，即使我们将估计应用于具有欧拉行走的图，这也是一个非常大的估计