0

显然，如果该图甚至没有哈密顿路径，它就没有哈密顿循环，所以if (!g.hp()) return false;在那之后我有点迷茫。

课堂上给出的提示是添加一些顶点。我的想法是，如果图在添加顶点之前具有哈密顿路径，并且添加顶点意味着该图不再具有哈密顿路径，则原始图具有哈密顿循环。

当然，我不是在寻找伪代码或代码，我只是想被推向正确的方向。

编辑：维基百科页面提到，您可以使用哈密顿路径例程通过将附加顶点连接到上图中的每个顶点来查找它是否具有哈密顿循环。这是为什么？

4

1 回答 1

1

这样想 - 哈密顿循环只是在路径端点之间有边的哈密顿路径。同样，从哈密顿循环中删除任何一条边都会导致哈密顿路径。这意味着，如果您要通过一条边将一个顶点连接到一个现有顶点来向图中添加一个顶点，那么在新图中您仍然会有一条哈密顿路径。无论您在何处插入新顶点，这都是正确的。

这也意味着如果图中存在一个顶点，使得将其连接到具有单个边的单个新顶点会导致一个没有哈密顿路径的新图，那么该图没有哈密顿循环（我怀疑你的教授希望你通过矛盾来证明这一点，所以我将把它留给你）。您可以使用该事实来创建您的哈密顿循环算法。我知道你没有要求伪代码，但无论如何我会给你一些：

boolean hc(Graph g){
    if(!g.hp()) return false;

    Vertex test = new Vertex();

    for(Vertex v : g){
        g.connect(test,v); //adds single edge between test and v
        if(!g.hp()) return false;
        g.disconnect(test,v); //removes any edges between test and v
    }

    //every test yielded a new graph with a Hamiltonian Path, therefore
    //g must have a Hamiltonian Cycle:
    return true;
}
于 2013-09-17T21:57:49.040 回答