离散数学期末复习试题及答案(五)(7)

离散数学期末复习试题及答案

( 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

…… ……

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库离散数学期末复习试题及答案(五)(7)在线全文阅读。