离散数学期末复习试题及答案
( a, b,d,c ,a) or (a,c,d,b,a) long = 47
16．ｎ阶无向完全图 Kn，（ｎ＞1）是否存在欧拉道路和欧拉回路？ 充要条件是什么？
K2存在欧拉道路，Kn (n为奇数且 n>1) 存在欧拉回路。
17．如果ｎ（ｎ≥ 4）个顶点的线性图的每对顶点的次之和≥ｎ，则G 存在哈密顿回路。
每对顶点次之和≥n＞n-1 , 有充分性定理 , 必有 H 路, 不妨设此路 为( V1,V2,…,Vn)。若 V1与 Vn 相邻，则(V1,V2,…,Vn,V1)是 H 回路。否则,
V1与Vi1,Vi2,...,Vij相邻,则Vn必与Vi1 1,Vi2 1,...,Vij 1之一相邻。否
则, Vn 的次 ≤n-j-1, V1 的次加 Vn的次 ≤(n-j-1)+j = n-1，与每 对顶点次之和≥n矛盾。不妨Vn与Vit 1相邻，V1与Vit 相邻，可得
H 回路 (Vit 1
,Vit 2,...,V2,V1,Vit,Vit 1,...,Vn,Vit 1)
V1 V2 V3 Vi
t 1
it
Vn
…… ……