PDF《离散数学图论作业 5 - 哈密顿图》

离散数学图论作业

5 - 哈密顿图 Problem

1 下方所示各图是否拥有哈密顿通路?若有哈密顿通路,则求出这样一条通路.

若没有哈密顿通路,则论证为什 么这样的通路不存在. (1) (2) (3) Problem

2 对哪些 m 和n值来说,完全二部图 Km,n 具有哈密顿回路? Problem

3 证明:每当 n 是正整数时,就存在 n 阶格雷码,或者等价地证明:n >

1 的n维立方体 (n-cube)Q,总是具有哈 密顿回路.[提示:用数学归纳法,证明如何从 n ?

1 阶格雷码产生 n 阶格雷码.]

1 Problem

4 证明:下图所示的彼得森图没有哈密顿回路,但删除任意顶点 v 和所有与 v 关联的边,所获得的子图都有哈密 顿回路. Problem

5 若简单图 G 满足 V(G) ≥

3 且δ(G) ≥ V(G)?1

2 ,证明或反驳: a) G 一定存在哈密顿回路. b) G 一定存在哈密顿通路. Problem

6 底图是完全图的有向图称为竞赛图,试证明: a) 竞赛图一定含有哈密顿通路. b) 竞赛图含有哈密顿回路的充分必要条件是强连通. Problem

7 考虑在

15 天安排

15 门课程的考试(每天考

1 门课) ,使得同一位老师所任的任意两门课程考试不排在接连的两 天中,试证明如果没有老师担任多于

8 门课程,则符合上述要求的考试安排总是可能的.

2 Problem

8 考虑 M * N 的网格,以其中的方格作为点集,任意两个点之间有边当且仅当对应的两个方格相邻,构成图 G. a) 当N是偶数且 M >

1 时,给出一种哈密顿回路的构造方法. b) 当N和M都是大于

1 的奇数时,证明此时 G 没有哈密顿回路. 3