algorithm - 如何在图中查找哈密顿路径数？

Question

我正在尝试这个 Google Codejam 问题，它说如果我们从完整图中删除 k 条边，则找出哈密尔顿路径的数量

链接到问题

https://code.google.com/codejam/contest/32004/dashboard#s=p2

我发现我们可以使用包含排除原则来找出数字

但我的问题是当我们考虑从完整图中删除了一些'x'条边时如何确定路径数(删除的边已给出)

Answer 1

这个想法是计算排列而不是计算路径。这样，每条路径都会被考虑 2*n 次。

如果排列是 n!，则总数。

让我们使用包含排除原则来计算不良循环。如果一条边被禁止，则有 2*n * (n-2) 条!包含这条边的路径(我们将两个相邻的顶点放在一起，其余的放在任何地方)。

如果有几条禁止边，则所有的顶点被分成几个独立的组(它们形成由这些边连接的链)。有两种放置每个组的方法(因为它可以颠倒)。所有组都可以任意排列。其余元素可以放置在任何地方(它将作为二项式系数乘以某个阶乘)。还有一个警告:链条可以缠绕。但是最多只能有一个这样的链。因此，我们可以迭代环绕的链，并使用上述算法计算放置其余部分的方法数。