1

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

假设：存在一种确定图是否具有哈密顿循环的有效算法（返回 True\False）。让我们将此 alg' D称为确定。

  • 证明：存在一种返回哈密顿循环的有效算法。

我的回答尝试

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'

我的问题

正如你所看到的，我有一个算法的想法来证明一个算法的存在。我觉得这是正确的方向......但是我如何证明这个算法实际上返回了哈密顿循环？

4

2 回答 2

1

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

  • 你的 for 循环的一个不变量是 G' 总是包含一个哈密顿循环，所以必须证明 G' 不包含不属于循环的边

  • 有一个定理表明哈密顿循环的边数等于 V + 1。因此，如果您可以证明在循环结束时恰好有 V + 1 个边，您就完成了。（我认为您提供的算法并不容易，但也许可以进行一些小的修改）

  • 如果您可以正式证明当且仅当有必要存在哈密顿循环时您才能恢复边缘这一事实，那么在循环结束时不会立即出现不属于循环的边缘

于 2020-02-28T12:53:49.900 回答
1

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

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

If not D(G):
    Return No_Hamilton_Cycle!

其次，该算法返回一个汉密尔顿循环（不是）：在中可以有许多替代的汉密尔顿循环，但是您尝试删除边的顺序决定了您最终将获得哪些竞争的汉密尔顿循环。

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

当循环结束时，你知道：

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

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

于 2020-02-29T00:29:08.087 回答