无向图的顶点编号为 1,2,...4286。如果 |i-j| 则边 (i,j) 存在<= 3，其中 i!=j。哪些说法是正确的？
The vertices of an undirected graph are numbered 1,2,...4286. The edge (i,j) exists if |i-j| <= 3, where i!=j. Which statements are true?
无向图的顶点编号为1,2,...4286。如果 |i-j| 则边 (i,j) 存在<= 3，其中 i!=j。哪些说法是正确的？
- 图形包含一个欧拉圆
- 该图包含完美匹配图
- 该图是哈密顿量
我在想最后两个是真的，而第一个是假的。
这是正确的吗？
该图不是 Eulerian cycle，因为这样的循环要求每个节点的度数都是偶数，但在此图中，节点 1 的度数是奇数 -- 它的邻居是 2、3 和 4。
该图包含一个 perfect matching：一个可能的匹配项是连接到 +1 的边集合，对于每个奇数：
1─2, 3─4, 5─6, ... , 4285─4286
该图是 Hamiltonian graph，因为它包含以下哈密顿循环：
1─2 ─ 4─5 ─ 7─8 ─ 10─11 ─ 13─14 ─ ... ─ 4282─4283 ── 4285─4286
\ /
─ 3 ─── 6 ─── 9 ──── 12 ──── ... ─── 4281 ─────── 4284 ─────
所以在底部我们有所有 3 的倍数，在顶部有所有其他值。
无向图的顶点编号为1,2,...4286。如果 |i-j| 则边 (i,j) 存在<= 3，其中 i!=j。哪些说法是正确的？
- 图形包含一个欧拉圆
- 该图包含完美匹配图
- 该图是哈密顿量
我在想最后两个是真的，而第一个是假的。 这是正确的吗？
该图不是 Eulerian cycle，因为这样的循环要求每个节点的度数都是偶数，但在此图中，节点 1 的度数是奇数 -- 它的邻居是 2、3 和 4。
该图包含一个 perfect matching：一个可能的匹配项是连接到 +1 的边集合，对于每个奇数：
1─2, 3─4, 5─6, ... , 4285─4286
该图是 Hamiltonian graph，因为它包含以下哈密顿循环：
1─2 ─ 4─5 ─ 7─8 ─ 10─11 ─ 13─14 ─ ... ─ 4282─4283 ── 4285─4286
\ /
─ 3 ─── 6 ─── 9 ──── 12 ──── ... ─── 4281 ─────── 4284 ─────
所以在底部我们有所有 3 的倍数，在顶部有所有其他值。