每个顶点具有哈密顿循环所需的最小顶点度数是多少?
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
的图表要求并且仍然包含哈密顿圆,你找不到满足要求但不包含哈密顿圆的图。
我用谷歌搜索发现:
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
的图表要求并且仍然包含哈密顿圆,你找不到满足要求但不包含哈密顿圆的图。