问题是使用哈密顿循环 Hcycle(V,E) 函数来测试图 G 是否包含哈密顿路径，该函数在 G 是否包含哈密顿循环时给出输出真或假。
我必须编写一个具有多项式时间复杂度的程序，它必须使用一个必须为这个问题提供输出的哈密顿循环函数来确定无向图 G 是否包含至少一个哈密顿路径。
我还需要编写一个具有相反问题的程序。（使用 Hpath 函数判断图形是否包含 Hemiltonian 循环）。
我找不到这个问题的解决方案。我只能同时使用 Hcycle 和 Hpath 一次。
我们假设函数 Hcycle 和 Hpath 以线性时间复杂度运行。
每个汉密尔顿循环都是汉密尔顿路径，只需在某个地方打破循环即可。
反过来就不太容易了。蛮力解决方案是：对于所有的哈密顿路径p，检查p的起点和终点之间是否有边，如果有，做一个循环。但是，如果HPath只返回一些路径，则无法从中创建循环（我猜）。
检查维基百科
Path by Hcycle(V,E)：在通过添加一个连接到所有其他顶点的顶点创建的图上调用 Hcycle()。如果新图有一个循环而不是从该循环中删除新节点，我们会得到原始图上的路径。
按 Hpath(V,E) 循环：在通过添加一个顶点并将其连接到与一个现有顶点相同的邻居创建的图上调用 Hpath()。这意味着这两个顶点将具有相同的邻居。如果新图有一条路径，则至少一个路径末端位于这两个顶点上。如果其他顶点没有结束，则它位于路径第三位置，通过重新排序路径，我们可以将两个顶点都设置为路径端点。合并这两个顶点（因为它们具有相同的邻居），我们在原始图中得到一个循环。
Hcycle(V,E) 的路径：如果图有循环，则它也有路径。如果图没有循环，则对于每个未连接的顶点对 ( v1, v2) 在它们之间添加边并检查是否存在带有 的循环Hcycle(V,E+(v1,v2))。如果有一个循环，那么原始图中v1和之间就有一条路径。v2Hcycle 称为最大|V|^2次数。
按 Hpath(V,E) 循环：想法是强制路径具有我们知道的结束顶点。这可以通过构建两个顶点的度数为一的图来完成。成为N(v)的邻居v。对于一条边(v1,v2)和n1fromN(v1)-v2和n2from ，通过从except to中删除所有边，并从except to 中删除N(v2)-v1所有边来构造一个图。如果该图有一条路径，那么它的端点在和上，并且我们的原始图有一个圆圈。Hpath 称为最大次数。v1n1v2n2v1v2|E|*|V|^2