如何找到不使用“禁止”边缘的哈密顿循环数？(How do I find the number of Hamiltonian cycles that do not use “forbidden” edges?)

这个问题实际上改述了这个问题。 代码堵塞问题如下：

您将获得一个包含N个节点和K “禁止”边缘的完整无向图。 N <= 300， K <= 15.在图中找出不使用任​​何K “禁止”边的哈密顿循环数。

O(2^N*N^2)的直接DP方法对于这样的N不起作用。 看起来获胜的解决方案是O(2^K) 。 有人知道如何解决这个问题吗？

This question actually rephrases that one. The code jam problem is the following:

You are given a complete undirected graph with N nodes and K "forbidden" edges. N <= 300, K <= 15. Find the number of Hamiltonian cycles in the graph that do not use any of the K "forbidden" edges.

The straightforward DP approach of O(2^N*N^2) does not work for such N. It looks like that the winning solutions are O(2^K). Does anybody know how to solve this problem ?

最满意答案

让我们找出禁止边的每个子集S，存在多少哈密顿周期，使用S的所有边。如果我们解决这个子任务，那么我们将通过包含 - 排除公式来解决问题。

现在我们如何解决子任务？ 让我们绘制S的所有边。如果存在度数大于2的顶点，那么显然我们无法完成循环并且答案为0.否则图形被划分为连通分量。 每个组件都是唯一的顶点，循环或简单的路径。

如果存在循环，那么它必须通过所有顶点，否则我们将无法完成哈密顿循环。 如果是这种情况，答案是2.（循环可以在2个方向上移动。）否则答案为0。

剩下的情况是有c个路径和k个底点。 要完成哈密顿循环，我们必须选择每条路径的方向（ 2 ^ c方式），然后选择组件的顺序。 我们有c + k组件，因此可以重新排列（c + k）！ 方法。 但我们对周期感兴趣，所以我们不区分通过循环移位相互转换的顺序。 （所以（1,2,3），（2,3,1）和（3,1,2）是相同的。）这意味着我们必须将答案除以移位数c + k 。 所以答案（对于子任务）是2 ^ c（c + k-1）！ 。

这个想法是在bmerry的解决方案中实现的（非常干净的代码，顺便说一句）。

Let's find out for each subset S of forbidden edges, how many Hamiltonian cycles there exist, that use all edges of S. If we solve this subtask then we'll solve the problem by inclusion-exclusion formula.

Now how do we solve the subtask? Let's draw all edges of S. If there exist a vertex of degree more than 2, then obviously we cannot complete the cycle and the answer is 0. Otherwise the graph is divided into connected components. Each component is a sole vertex, a cycle or a simple path.

If there exists a cycle, then it must pass through all vertices, otherwise we won't be able to complete the Hamiltonian cycle. If this is the case, the answer is 2. (The cycle can be traversed in 2 directions.) Otherwise the answer is 0.

The remaining case is when there are c paths and k sole vertices. To complete the Hamiltonian cycle we must choose the direction of each path (2^c ways) and then choose the order of components. We've got c+k components, so they can be rearranged in (c+k)! ways. But we are interested in cycles, so we don't distinguish the orderings which turn into one another by cyclic shifts. (So (1,2,3), (2,3,1) and (3,1,2) are the same.) It means that we must divide the answer by the number of shifts, c+k. So the answer (to the subtask) is 2^c (c+k-1)!.

This idea is implemented in bmerry's solution (very clean code, btw).

更多推荐