9

我有一个具有 N 个节点和 2N-3 条边的连接的无向图。您可以将图视为构建在现有初始图的基础上，该图具有 3 个节点和 3 条边。添加到图中的每个节点都与图中的现有节点有 2 个连接。当所有节点都添加到图中（总共添加 N-3 个节点）时，构建最终图。

最初我被问到，这个图中可以访问一次的最大节点数是多少（初始节点除外），即给定图的最大哈密顿路径中包含的最大节点数是多少？（好吧，说最大哈密顿路径不是一个有效的短语，但考虑到问题的性质，我需要找到一次访问的最大节点数，并且行程在初始节点处结束。我认为它可以被视为子图是哈密顿量，由最大数量的节点组成，因此是最大可能的哈密顿路径）。

由于没有要求我找到路径，因此我应该首先检查给定数量的节点是否存在哈密顿路径。我知道平面图和循环图s (C n ) 是哈密顿图（我也知道哈密顿图的 Ore 定理，但我将要处理的图不会是一个很有可能的密集图，因此使 Ore 的定理很漂亮在我的情况下没用）。因此，我需要找到一种算法来检查该图是否为循环图，即是否存在一个包含给定图的所有节点的循环。

由于 DFS 用于检测周期，我认为对 DFS 进行一些小的操作可以帮助我检测我正在寻找的内容，例如跟踪探索的节点，最后检查最后访问的节点是否与初始节点有连接。不幸的是，我无法通过这种方法取得成功。

我尝试的另一种方法是排除一个节点，然后尝试从另一个相邻节点开始到达其相邻节点。根据所选的相邻节点，该算法可能无法给出正确的结果。

我几乎被困在这里。你能帮我想出另一种算法来告诉我该图是否是循环图吗？

编辑

我在评论的帮助下意识到（谢谢你）：

循环图由一个循环组成，有 N 个边和 N 个顶点。如果存在一个包含给定图的所有节点的循环，那就是哈密顿循环。-纳米

我实际上是在寻找一条哈密顿路径，我并不打算这样做:) 再想一想，我认为在构建图的同时检查图的哈密顿属性会更有效，这也是我正在寻找的: 时间效率。

经过一番思考，我认为无论节点数量是多少，由于节点添加标准，该图似乎是哈密顿量。问题是我无法确定，也无法证明。以这种方式添加节点，即添加具有 2 条边的新节点，将添加的节点连接到现有节点，是否会改变图的哈密顿属性？如果它不改变哈密顿性质，那又如何呢？如果它确实改变了，又是怎么回事？谢谢。

编辑#2

我再次意识到，按照我描述的方式构建图形可能会改变哈密顿量。考虑如下给出的输入：

1 3
2 3
1 5
1 3

这些输入表示第 4 个节点连接到节点 1 和节点 3，第 5 个节点连接到节点 2 和节点 3。. .

第 4 和第 7 个节点连接到相同的节点，从而将可以仅访问一次的最大节点数降低 1。如果我检测到这些冲突（不包括诸如 3 3 之类的输入，这是您建议的示例由于问题表明新添加的边连接到其他 2 个节点）并降低最大节点数，从 N 开始，我相信我可以得到正确的结果。

看，我不选择连接，它们是给我的，我必须找到最大值。节点数。

我认为在构建图形时计算相同的连接数并从 N 中减去相同的连接数会得到正确的结果吗？你能证实这一点还是这个算法有缺陷？

4

3 回答 3

1

我们在这个问题中得到的是一个connected, non-directed有N个节点和2N-3 条边的图。考虑下面给出的图表，

            A
           / \
          B _ C
         ( )  
          D

该图没有哈密顿循环。但是 Graph 的构造符合您添加节点的规则。因此，搜索哈密顿循环可能无法为您提供解决方案。更重要的是，即使有可能哈密顿循环检测是一个具有O(2 N )复杂性的NP 完全问题。所以这种方法可能并不理想。

我建议使用Floyd's Cycle Finding algorithm（也称为Tortoise and Hare算法）的修改版本。

修改后的算法是，

1. Initialize a List CYC_LIST to ∅.

2. Add the root node to the list CYC_LIST and set it as unvisited. 

3. Call the function Floyd() twice with the unvisited node in the list CYC_LIST for each of the two edges. Mark the node as visited.

4. Add all the previously unvisited vertices traversed by the Tortoise pointer to the list CYC_LIST.

5. Repeat steps 3 and 4 until no more unvisited nodes remains in the list.

6. If the list CYC_LIST contains N nodes, then the Graph contains a Cycle involving all the nodes.

该算法最多调用 Floyd 的循环查找算法 2N 次。Floyd 的循环查找算法需要线性时间 ( O(N) )。因此修改后的算法的复杂度为O(N 2 )，比基于哈密顿循环的方法所花费的指数时间要好得多。

closed paths这种方法的一个可能问题是，除非实施更严格的检查标准，否则它将与循环一起检测。

回复编辑#2

考虑下面给出的图表，

            A------------\
           / \            \
          B _ C            \
          |\ /|             \
          | D |             F
          \   /            /
           \ /            / 
            E------------/

根据您的算法，该图没有包含所有节点的循环。但是这个图中有一个包含所有节点的循环。

A-B-D-C-E-F-A

所以我认为你的方法有一些缺陷。但是假设如果你的算法是正确的，它比我的方法要好得多。因为我的需要O(n 2 )时间，而你只需要O(n)。

于 2013-04-07T03:55:37.893 回答
0

为这个线程添加一些澄清：找到一个哈密顿循环是 NP 完全的，这意味着找到一个最长的循环也是 NP 完全的，因为如果我们可以在任何图中找到最长的循环，我们就可以找到子图的哈密顿循环由位于该循环上的顶点诱导。（参见关于最长周期问题的例如这篇论文）

我们不能在这里使用狄拉克的标准：狄拉克只告诉我们minimum degree >= n/2 -> Hamiltonian Cycle，这是我们需要的相反方向的暗示。反过来肯定是错误的：对n顶点进行循环，无论圆的大小如何，其中的每个顶点的度数都为 2，但它有（是）一个 HC。你可以从狄拉克那里看出no Hamiltonian Cycle -> minimum degree < n/2，这在这里没有用，因为我们不知道我们的图是否有 HC ，所以我们不能使用暗示（尽管我们根据 OP 描述的内容构建的每个图都会有一个度数的顶点2，即添加到图中的最后一个顶点，所以对于任意的n，我们有最小度数2）。

问题是您可以构建具有 HC 的任意大小的图和没有 HC 的任意大小的图。对于第一部分：如果原始三角形是A，B，C并且添加的顶点编号为1到k，则将第一个添加的顶点连接到A和C，将第k+1个顶点连接到A和第k个所有 k >= 1 的顶点。循环为A,B,C,1,2,...,k,A。对于第二部分，将顶点 1 和 2 都连接到 A 和 B；该图没有HC。

还需要注意的是，具有 HC 的属性可以在构造过程中从一个顶点更改为另一个顶点。您可以在添加顶点时创建和销毁 HC 属性，因此每次添加顶点时都必须检查它。一个简单的例子：在添加第一个顶点之后获取图形，并将第二个顶点与边一起添加到与第一个顶点相连的三角形的相同两个顶点。这从一个有 HC 的图构造了一个没有 HC 的图。反过来：现在添加第三个顶点并将其连接到 1 和 2；这是从没有 HC 的图和有 HC 的图构建的。
在构建过程中存储最后一个已知的 HC 并不能真正帮助您，因为它可能会完全改变。在添加第 20 个顶点之后，您可以有一个 HC，然后在 [21,2000] 中没有一个用于 k 的，然后再为添加的第 2001 个顶点添加一个。您在 23 个顶点上的 HC 很可能对您没有太大帮助。

如果您想弄清楚如何有效地解决这个问题，您必须找到适用于所有可以有效检查的图表的标准。否则，在我看来，您的问题并不比一般情况下的哈密顿循环问题更简单，因此您可以将用于该问题的算法之一调整为您的变体。

于 2013-04-06T20:30:36.183 回答
0

下面我在原始图中添加了三个额外的节点（3,4,5），看起来我可以无限期地添加新节点，同时保持哈密顿循环的属性。对于下图，循环将是0-1-3-5-4-2-0

  1---3---5
 / \ / \ /
0---2---4

由于对于如何添加具有两条边的新节点没有额外的限制，我认为通过构造，您可以拥有一个具有哈密顿循环属性的图。

于 2013-04-07T06:09:23.843 回答