离散数学第二版答案（6-7章）

第七章 图论

6.1第164页

1.画出图G??V,E,??的图示，指出其中哪些图是简单图。 （1）

v2e3v1e4v3e5e6e1e2v4不是简单图。

（2）

v3e8e9e10e5e6e1e2v4e3v1不是简单图。

v5e7v2e4（3）

e1v1e2e5v3e7e8v5v4e6v7e10v8v2e9v6e11e3e4是简单图。

2.写出图7-8的抽象数学定义。 （1）解：G??V,E,??，其中

V?{1,2,3，,E?{a,b,c,d,e,f}，

??{?a,?2,4??,?b,?1,2??,?c,?1,1??,?d,?1,3??,?e,?3,2??,?f,?4,2??}（2）解：G??V,E,??，其中V?{1,2,3,4,5,6,7,8,9}，E?{a,b,c,d,e,f,g,h,i,

j,k,l}，

??{?a,{1,3}?,?b,{1,3}?,?c,{1,2}?,?d,{2,3}?,?e,{3,4}?,

?f,{2,4}?,?g,{2,5}?,?h,{6,7}?,?i,{7,9}?,?j,{7,8}?,

?k,{8,9}?,?l,{9,9}?}3.证明：在n阶简单有向图中，完全有向图的边数最多，其边数为n(n?1)。

证明：简单有向图是没有自环，没有平行边的有向图，只要两个不同的结点之间才能有边。完全有向图是每个结点的出度和入度都是n-1的简单有向图，也就是每个结点都有到其他所有结点的边，因此，完全有向图的边数最多。

在完全有向图中，所有结点的出度之和为n(n-1)，所有结点的入度之和为n(n-1)，设边的个数为m，由握手定理可知，2m= n(n-1)+ n(n-1)，即m= n(n-1)，得证。 4.证明：3度正则图必有偶数个结点。

证明：设三度正则图的结点个数为n，那么所有结点的度数之和为3n，由握手定理可知，边的个数为3n/2=1.5n，由于边的个数一定是整数，因此，n为偶数。得证。

5.在一次集会中，相互认识的人会彼此握手，试证明：与奇数个人握手的人数是偶数个。 证明：设集会上的人一共有m个，可分为两部分，一部分为与奇数个人握手的人，设为x个，另一部分为与偶数个人握手的人，为m-x个。

由于握手是相互的，即一次握手，两个人握手的次数都加1，一共加2，因此，集会上所有人的握手次数之和为偶数。

与偶数个人握手的人，这些人的握手次数之和为

a1?a2??am?x（其中，

a1,a2,,am?x都是偶数），为偶数。

?b2??bx（其中，b1,b2,,bx为

与奇数个人握手的人，这些人的握手次数之和为b1基数），由于所有人的握手次数之和偶数，因此b1?b2??bx也要为偶数，即

(b1?b2?又因为

?bx)mod2?0

(b1?b2??bx)mod2?bxmod2

?b1mod2?b2mod2??xmod2即xmod2?0，因此x为偶数，即与奇数个人握手的人是偶数个，得证。

6.证明：图7-7中的两个图同构。

证明：首先，给这两幅图标上对应的结点编号，如下

1231'2'3'4'4两

个

图

5的

结

6点

和

边

的

数

6'目

都

5'相

同

。假

设函数

??{?1,1'?,?5,2'?,?3,3'?,?4,4'?,?5,2'?,?6,6'?}，左图中相邻的结点是

1和4，1和5，1和6，2和4，2和5，2和6，3和4，3和5，3和6，对应的像点1’和4’，1’和2’，1’和6’，5’和4’，5’和2’，5’和6’，3’和5’，3’和2’，3’和6’在右图中也相邻，因此，两图同构。

7.证明：在任意六个人中，若没有三个人彼此认识，则必有三个人彼此都不认识。 证明：分三种情况：

（1）任何一个人最多认识另外一个人 将相互认识的两个人分成一组，则至少可以分3组，每组取一个人，则这三个必不认识。 （2）任何一个人最多认识另外两个人 最糟糕的情况是当每个人都认识另外两个人时，若认识的人之间画一条线可以构成一个六边形，取不相邻的三个点即是不认识的。 （3）任何一个人最多认识另外的三个人

AFBEC

不妨设点A与B,C,E认识（用实线连接）。因为B,C,E之间只有有两个人认识就不满足任何三个人都不认识的条件，比如B,C认识画一条实线，那么A,B,C就相互认识，与已知矛盾。所以B,C,E是所求的三个互补认识的人。 （4）任何一个人最多认识两外4或5个人 该情况与（3）类似，所求的人即与A认识的两外4或5个人中的三个人。 证毕。

8.证明：图7-9的两个图不同构。

证明：给这两幅图标上对应的结点编号，如下：

D1e121'?e12'e95e56e9?5'?e56'e4e103e87e6e7e3a)8e2?e4?e87'?e6?e7?e3b)8'?e2e10?43'4'

两个图的点数和边数相同。假设函数：

??{?1,1'?,?2,2'?,?3,3'?,?4,4'?,?5,5'?,?6,6'?,?7,7'?,?8,8'?}

易证：① a）中的子图G1??V1,E1,?1?，V1?{1,2,3,4}，E1?{e1,e2,e3,e4}，

?1?{?e1,{1,2}?,?e2,{2,3}?,?e3,{3,4}?,?e4,{1,4}?}与G1???V1?,E1?,?1??，

b）中的子图

，

??,3?,4?}V1??{1,2，

E1??{e1?,e2?,e3?,e4?}?1??{?e1?,{1,2}?,?e2?,{2,3}?,?e3?,{3,4}?,?e4?,{1,4}?}同构。

② a）中的子图G2??V2,E2,?2?，V2?{5,6,7,8}，E2?{e5,e6,e7,e8}，

?2?{?e5,{5,6}?,?e6,{6,7}?,?e7,{7,8}?,?e8,{8,9}?}与

b）中的子图

G2???V2?,E2?,?2??，G2???V2?,E2?,?2??，V2??{5?,6?,7?,8?}，E2??{e5?,e6?,e7?,e8?}，

?2??{?e5?,{5,6}?,?e6?,{6,7}?,?e7?,{7,8}?,?e8?,{8,9}?}同构。

??1,5,7,3}，除这两个子图以外，对应a）中的子图G3??V3,E,33，V2?{E2?{e4,e8,e9,e10}，?2?{?e9,{1,5}?,?e8,{5,7}?,?e10,{7,3}?,?e4,{3,1}?}在b）无

中对应的同构图。因此a）和b）两个图不同构。

9．图7-10的两个图是否同构？说明理由。

aa?dd?cbc?b?a)b)