哈密顿循环；证明：如果有一个有效的算法来确定一个 HC 存在，那么就有一个有效的 FIND 算法

Question

设G(V,E)为无向图。哈密顿循环是访问G的每个顶点v恰好一次的循环（第一个顶点除外，它也是循环中的最后一个顶点).

假设：存在一种有效的算法来确定图是否具有哈密顿循环 (returns True\False)。我们称此算法为 D for Determine.

证明：存在一个returns哈密顿循环的有效算法。

我的回答尝试

Assume D(G) = true

Let G'=G (Define G' a copy of G).

For each edge e in E:

    G' = G' \ {e}           // Remove e from G.

    d_boolean = D(G')       // Run D alg' on the new Graph.

    if d_boolean = false
        then G' = G' U {e}  // restore e to graph (because e must be in the Hamiltonian Cycle)

    // else d_boolean=true we do nothing because e is not an edge on the Hamiltonian Cycle

Return G'

我的问题

如您所见，我想到了一种算法来证明它的存在。我觉得方向是对的... 但是我如何证明这个算法实际上 returns 哈密顿循环？

Answer 1

我不是形式证明方面的专家，所以我只会给出一些可能有用的观察结果。

for 循环的一个不变量是 G' 总是包含哈密顿循环，因此必须证明 G' 中不包含不属于循环的边
有一个定理表明哈密顿环的边数等于V + 1。所以如果你能证明在循环的最后恰好有V + 1条边你完成了。（我认为使用您提供的算法并不容易，但也许可以稍作修改）
如果你能正式证明你恢复边缘的事实当且仅当哈密顿循环的存在是必要的而不是直接的在循环结束时不会有边不属于循环

Answer 2

您的伪代码中只缺少一个元素：不能保证具有汉密尔顿循环。

因此，在执行任何其他操作之前，您需要先进行检查，以确保它确实具有汉密尔顿循环。

If not D(G):
    Return No_Hamilton_Cycle!

其次，算法returns a哈密顿循环（不是the ): 中可以有许多可供选择的汉密尔顿循环，但是您尝试删除边的顺序决定了您最终将获得那些竞争汉密尔顿循环中的哪一个。

通过上面的添加，您可以确定在每次迭代的开始和结束时，' 都有一个汉密尔顿循环：迭代将删除一条边并确认 ' 仍然有一个汉密尔顿循环，或者删除已撤消，因此 ' 的状态在迭代结束时与迭代开始时相同。

当循环结束时，您知道：

' 有一个汉密尔顿循环，因为在最后一次迭代结束时是这样
没有一条边可以从 ’ 中移除并且仍然有一个汉密尔顿循环，因为您尝试移除所有这些边但没有成功。诚然，有时 ' 在尝试的那个时刻仍然有其他边，但这并不重要：如果边对于在 a 中拥有汉密尔顿循环是必不可少的，那么在您删除其他一些非必要的边之后它仍然是必不可少的.
该算法没有添加或删除任何节点：' 具有与
该算法没有添加任何边：’的边集是（可能等于它）的边的子集。

从这些点我们可以得出结论，如果有一个汉密尔顿循环，那么'是一个汉密尔顿循环。

哈密顿循环；证明：如果有一个有效的算法来确定一个 HC 存在，那么就有一个有效的 FIND 算法

Hamiltonian Cycle; Prove: if there's an efficient algorithm to determine that an HC exists, then there's an efficient FIND algorithm

algorithm

graph-theory

hamiltonian-cycle

哈密​​顿循环；证明：如果有一个有效的算法来确定一个 HC 存在，那么就有一个有效的 FIND 算法

Hamiltonian Cycle; Prove: if there's an efficient algorithm to determine that an HC exists, then there's an efficient FIND algorithm

algorithm

graph-theory

hamiltonian-cycle

哈密顿循环；证明：如果有一个有效的算法来确定一个 HC 存在，那么就有一个有效的 FIND 算法