离散数学及其应用--第2版第8章部分习题答案.docx

第8章习题解答

1.（1）有欧拉回路（2）（3）（6）没有欧拉回路，没有欧拉通路（4）（5）有欧拉通路

2.构造欧拉图使满足条件：(1)m和n奇偶性相同；(2)m和n奇偶性相反。

解：

3、n为何值时，无向完全图Kn是欧拉图？n为何值时，无向完全图Kn仅存在欧拉通路而不存在欧拉回路？

解：当n为大于2的奇数时，无向完全图Kn是欧拉图，因为每个节点的度数为偶数。当n为2时，K2，是唯一存在两个奇度点的完全图，因此此图只存在欧拉通路

4.（1）有欧拉回路（3）没有欧拉回路，没有欧拉通路（2）有欧拉通路

5.（1）（2）（4）（5）有哈密顿回路（3）没有哈密顿回路，没有哈密顿通路（6）有哈密顿通路

6.

(1)画一个有一条欧拉回路和一条汉密顿尔回路的图.

(2)画一个有一条欧拉回路但没有一条汉密顿尔回路的图.

(3)画一个没有一条欧拉回路,但有一条汉密顿尔回路的图.

7.能

8.是，不是

9.(1)是哈密尔顿图。一条哈密尔顿回路为：abcihgfeda。

(2)不是哈密尔顿图。

10.可能

11.是

12.设G为n(n=3)阶无向简单图,边数m=(1/2)(n-1)(n-2)+2，证明G是哈密尔顿图。

证明:

反证法：假设存在不相邻的结点vi，vj∈V，有dev(vi)+dev(vj)≤n-1。另V1={vi，vj}，G1=G-V1，则G1是（n-2）阶简单图，它的边数m1满足m1=(1/2)(n-1)(n-2)+2-(dev(vi)+dev(vj))≥(1/2)(n-1)(n-2)+2-(n-1)=(1/2)(n-2)(n-3)+1这与G1是(n-2)阶的简单图矛盾（注：(n-2)阶的简单图的最大边数为(1/2)(n-2)(n-3)）所以G中任何两个不相邻的结点度数之和均大于等于n。

再根据定理：设G=（V，E）是n阶（n≥3）无向简单图，若对于任意的不相邻的结点vi，vj∈V，有dev(vi)+dev(vj)≥n，则G是哈密尔顿图。

所以G是哈密尔顿图。

13.设G是无向连通图，证明，若G中有桥或割点，则G不是哈密顿图。

证明：反证法，假设存在有割点v的图是哈密顿图，那么此图存在哈密顿回路。在此回路中删除割点v，那么剩下的节点依然连通。这和割点的定义相矛盾，所以G中有割点，则G不是哈密顿图。另外，若G中有桥，桥的端点就是割点，所以题设命题成立。

14.假定在n个人的团体中,任何2人合起来认识其余的n-2个人。证明:

(1)这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人；

(2)当n≥4时,这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人

证明：（证：如果任意两个人加起来认识其余的ｎ－２个人，那么每个人至少认识n-2个人。）

将n个人看成图的结点，相互认识则在相关两个结点间有一条边，构成一个简单无向图G。设u和v是两个互相不认识的人，对除u和v外的任意一个人t，如果u和ｖ不认识t，则u和ｖ合起来认识n-3个人，和题意矛盾，因此ｕ和v都至少认识n-2个人。所以在此图中，不相邻的任意两个结点满足：d(u)+d(v)≥2(n-2)。

当ｎ≥3时，任何两个结点的点度之和d(u)+d(v)≥2(n-2)≥n-1,因此存在哈密顿道路，即这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人；

当n≥4,任何两个结点的点度之和d(u)+d(v)≥2(n-2)≥n,因此图中存在哈密顿回路，即这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人。

15.求图中结点a到其他所有结点的最短路径和距离

解:

由Dijkstra算法可得:

(1)初始P={a}

D(a)=0,D(b)=4,D(c)=3,D(d)=∞,D(e)=∞,D(f)=∞,D(g)=∞,D(z)=∞

(2)P={a,c}

D(b)=min{4,2+3}=4,D(d)=∞,D(e)=min{∞,3+8}=11,D(f)=∞,D(g)=∞

D(z)=∞

(3)P={a,b,c}

D(d)=min{∞,4+3}=7,D(e)=min{11,4+∞}=11,D(f)=∞,D(g)=∞,D(z)=∞

(4)P={a,b,c,d}

D(e)=min{11,7+1}=8,D(f)=min{∞,7+5}=12,D(g)=∞,D(z)=∞

(5)P={a,b,c,d,e}

D(f)=min{12,8+3}=11,D(g)=min{∞,8+5}=13,D(z)=∞

(6)P={a,b,c,d,e,f}

D(g)=min{13,