algorithm - 当必须始终包含一条或多条边时，完整无向图中的哈密顿回路总数是多少？

Question

对于一个完整的无向图 G，其中顶点由 索引[n] = {1,2,3,...,n} where n >= 4。我知道 G 中哈密顿回路的总数是(n-1)! / 2

1. 如果我们必须穿过边缘{1,2}，有多少个哈密顿回路？
2. 如果多个连续的边，例如{1,2} {2,3}必须被遍历呢？
3. 如果多个非连续边，例如{1,2} {3,4}必须被遍历怎么办？

直观地说，对于第 1 部分，答案似乎是，(n-2)! /2但我并不完全确定。对于其他部分，我完全被难住了。

任何帮助深表感谢！

Answer 1

1) 子箱 2

2）考虑G' = G - {v1, v2, v3...vk}（您需要使用的连续边E中出现顺序的顶点）。对于 G' 中的每个哈密顿回路 C，您可以将边序列添加到 C 的任何部分，从而得到C[0..i] + {C[i], v1} + E + {vk, C[i]} + C[i..n].

对于图 G'，there are (n - 1 - k)! / 2哈密顿电路。对于这些电路中的每一个，您都可以在任何 2 对连续边之间扩展它，就像我们上面讨论的那样。这是，|C| 这样做的方法。所以答案是(n - 1 - k)! / 2 * |C| = (n - 1 - k)! / 2 * (n - k)。

您仍然需要证明我们以这种方式计算所有这些，并且我们没有计算重复项。

3) 2 的推广。您计算 E 中没有提到任何顶点的哈密顿回路，然后开始将必须遍历的边 1 1 相加。