极稠密无向简单图中的哈密顿路径数

Number of Hamilton paths in an extremely dense undirected simple graph

在一个极其密集的无向简单图（大约 99.99% 的边是连通的）中计算汉密尔顿路径数的最快方法（算法）是什么？

我想到了以下方法:

首先计算完整图中的哈密顿路径数

一次删除一条边，但我无法计算出删除一条边会减少多少条路径。还有如何在去除边缘时防止重复计数？

我在 Math.SE 上遇到了类似的问题，但那是关于汉密尔顿循环而不是路径，我希望能显着改变问题。答案也不是很清楚，因此 post.

我不认为你可以计算出汉密尔顿路径的数量 实际生成路径或单独考虑每条路径 数的时候。对于特殊图——比如完整图——这个 当然可以，但一般情况下不会。

你可以生成完整图中的所有汉密尔顿路径并检查 对于每一个，如果它使用图形中的边的子集。当然 你可以通过修剪某些分支来加快速度 在完整图中生成汉密尔顿路径。

由于你的图很大，这种做法肯定不行 可行的。但是，您可以计算出所有路径的数量 包含缺失边之一的完整图，然后减去 这个数字。

我不认为这是微不足道的。关于它的一些想法：让我们考虑一下 最简单的情况，只缺少一条边。我们可以描述一条路径 具有一系列边或节点。假设你的图表有 n 节点。有 n-1 个缺失边的可能位置 通过完整图的汉密尔顿路径。边缘可以被遍历 可以遍历两个方向和不与边相邻的节点 在 (n-2)! 个不同的订单中。因此我们可以减去

2 * (n-1) * (n-2)! = 2 * (n-1)!

从通过完整图的汉密尔顿路径总数到 得到想要的结果。

如果正好缺少两条边，我们不能只减去两倍 number 因为我们对几条路径进行了两次计数，即路径 包含两条边。所以我们必须计算这个数字并添加它 再次。但现在它变得复杂了：重要的是边缘如何 有关系。如果它们是相邻的，则数字会比实际数字小 否则。所以一般来说你不能只计算 包含 k 条缺失边的汉密尔顿路径，但它是 重要的是您正在考虑哪些边缘以及它们是否 相邻与否。

但是假设你可以计算通过某个特定路径的路径数 边的选择（所有排列、遍历方向和 路径中的位置）。让我们进一步假设 k 边是 丢失的。您可以计算路径的数量，包括至少一个 像这样的边缘：

分别计算通过任何 k 条边的路径数 总结一下。

对于每对边，您计算了穿过这对边的路径 两次，所以再次减去这些路径（考虑每一对 个人）。

现在考虑包含三个边的路径。他们已经 数了 6 次并减去 3 次（3 个不同的对），所以 你必须减去它们两次。

包含4条边的路径要减去3次（因为 它们在包含 3 个边的路径中出现 4 次）。所以 上。

但是再说一次：你必须考虑边的每一种组合 个别地。甚至有可能某组边是 不兼容，因为某个节点出现了三次。还要考虑 考虑遍历边的方向。

所以没有简单的公式但是如果缺失边的数量是 真的很小，你可以数一下路径。