每个顶点具有哈密顿循环所需的最小顶点度数是多少?

What is the minimum degree of vertex required for each vertex to have a Hamiltonian cycle?

我用谷歌搜索发现:

If G = (V,E) has n ≥ 3 vertices and every vertex has degree ≥ n/2 then G has a Hamilton circuit.

但是我的问题是如果每个顶点的度数都是2或者更多,那么这个图也可以有哈密顿环

示例:-

          1---->2
          2---->3
          3---->4
          4---->5
          5---->6
          6---->7
          7---->8
          8---->1

假设该图是无向的...

在上面的例子中每个顶点的度数都是2,所以这个图会有一个哈密顿环。

那么,上面引用的文字有什么意义呢?

"上面例子中每个顶点的度数都是2,所以图会有一个哈密顿环。"

每个顶点的度数为 2 是确保图具有哈密顿循环的必要但不充分条件。因此,您提供的示例具有哈密顿循环,但并非所有具有二次顶点的图都必然具有哈密顿循环。

你引用的段落解释了保证哈密顿循环存在的条件。

[编辑 1] “你能给我一个每个顶点的度数为 2 但没有哈密顿循环的图的例子吗?”

答:画两个独立的三角形。每个顶点都是二阶的,但你显然不能有哈密顿循环。

但是,如果你有一个哈密顿循环,这意味着所有顶点的次数至少为 2。这意味着如果任何顶点的次数为 0 或 1,你就不可能有哈密顿循环.

从逻辑上讲,p => q不等同于q => p。我没有带伞走在雨中意味着我被淋湿了。我淋湿了不代表下雨了

图有哈密顿回路 => 每个顶点的度数至少为 2。

每个顶点的度数至少为 2 不 => 图有哈密顿回路。

但是:

“G = (V,E) 有 n ≥ 3 个顶点并且每个顶点的度数 ≥ n/2 => G 有一个汉密尔顿电路。”

注:=>implies

的符号

通过单个顶点附加 2 个三角形图:

*     *
|\   /|
| \ / |
|  *  |
| / \ |
|/   \|
*     *

两侧顶点的度数为2-2-2-2,中间的顶点度数为4。

  • 所以它满足了每个顶点的度数为2或更多的尝试要求,但它实际上并不包含哈密顿圆
  • 并且“巧合地”它不满足引用的要求。 n=5 在这种情况下,顶点需要度数 >=2.5(因此,实际上是 3)才能确定包含哈密顿圆。

肯定 是这里的重要部分:虽然您可能会发现不符合 >=n/2 的图表要求并且仍然包含哈密顿圆,你找不到满足要求但不包含哈密顿圆的图。