algorithm - 使用哈密尔顿循环函数和相反任务的哈密顿寻路

Question

问题是测试图 G 是否包含哈密顿路径，其中一次使用哈密尔顿循环 Hcycle(V,E) 函数，该函数给出 true 或 false 是否 G 包含哈密顿循环。

我必须编写一个具有多项式时间复杂度的程序，它必须使用一个哈密顿循环函数来确定无向图 G 是否至少包含一条哈密顿路径，该函数必须给出该问题的输出。

我还需要编写一个具有相反问题的程序。 (利用Hpath函数判断图中是否包含海密尔顿圈)。

我找不到解决这个问题的办法。我只能同时使用 Hcycle 和 Hpath 一次。

我们假设函数 Hcycle 和 Hpath 以线性时间复杂度运行。

Answer 1

Path by Hcycle(V,E):在通过添加一个连接到所有其他顶点的顶点创建的图上调用 Hcycle()。如果新图有一个循环而不是从该循环中删除新节点，我们将获得原始图上的路径。

Cycle by Hpath(V,E):在通过添加一个顶点并将其连接到与一个现有顶点相同的邻居而创建的图形上调用 Hpath()。这意味着这 2 个顶点将具有相同的邻居。如果新图有一条路径，那么至少有一条路径的终点在这两个顶点上。如果其他顶点不是终点，那么它在路径第三个位置上，通过重新排序路径，我们可以将两个顶点设置为路径终点。合并这两个顶点(因为它们有相同的邻居)我们在原始图中得到一个循环。

Path by Hcycle(V,E):如果图有循环，那么它也有路径。如果图没有循环而不是每个未连接的顶点对 ( v1, v2) 在它们之间添加边并检查是否有循环 Hcycle(V ,E+(v1,v2))。如果存在循环，则原始图中 v1 和 v2 之间存在路径。 Hcycle 最多调用 |V|^2 次。

Cycle by Hpath(V,E):想法是强制一条路径有我们知道的结束顶点。这可以通过构建两个顶点的度数为 1 的图来完成。设 N(v) 是 v 的邻居。对于来自 N(v1)-v2 的边 (v1,v2) 和 n1 以及来自 的 n2 >N(v2)-v1 通过从 v1 中移除除 n1 之外的所有边并从 v2 中移除所有边来构建图> 除了 n2。如果该图有一条路径，那么它的末端位于 v1 和 v2 上，并且我们的原始图有一个圆圈。 Hpath 被调用最多 |E|*|V|^2 次。