如何检测给定图形是否包含包含其所有节点的循环？建议的算法是否有任何缺陷？

Question

我有一个连接的,非定向的图,有N个节点和2N-3边.您可以考虑将图形构建到现有的初始图形上,该图形具有3个节点和3个边缘.每个节点都添加到图表上,并与图中的现有节点有2个连接.当所有节点都添加到图形中时(总共添加N-3个节点),构建最终图形.

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

由于我没有被要求找到路径,我应该首先检查是否存在给定数量节点的哈密顿路径.我知道平面图和循环图 s(C _n)是哈密​​顿图(我也知道哈密​​顿图的Ore定理,但我将要研究的图不会是一个概率很大的密集图,因此使得Ore定理很漂亮在我的情况下没用.)因此,我需要找到一种算法来检查图是否是循环图,即是否存在包含给定图的所有节点的循环.

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

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

我几乎被困在这里.你能帮我想一下另一个算法来告诉我图是一个循环图吗？

编辑

我在评论的帮助下意识到了(感谢你nm):

循环图由单个循环组成,具有N个边和N个顶点.如果存在包含给定图的所有节点的循环,那就是哈密顿循环. - nm

我实际上正在寻找哈密尔顿路径,我不打算这样做:)在第二个想法,我认为在构建它时检查图的哈密尔顿性质将更有效,这也是我也在寻找:时间效率.

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

编辑#2

我再次意识到,按照我描述的方式构建图形可能会改变哈密顿特性.考虑如下输入:

1 3
2 3
1 5
1 3

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

第4和第7个节点连接到相同的节点,从而将可以访问的最大节点数减少一次,如果我检测到这些冲突(不包括输入,例如3 3,这是您建议的示例)因为问题表明新添加的边连接到其他2个节点)并且从N开始降低最大节点数,我相信我可以得到正确的结果.

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

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

Answer 1

对此线程添加一些说明：找到哈密顿循环是 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 的 HC，并为添加的第 2001 个顶点再次添加一个 HC。很可能您在 23 个顶点上拥有的 HC 不会对您有太大帮助。

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