12 24
1 1
2 2
3 3
4 4
6 6
4 8
12 12
12 24
X（2）?X,o?, 其中X?{1,2,3}。（假定XX为丛X到X的双射函数）
解：X到X有6个双射函数，分别用
p1,p2,L,p6表示，设
X:abc???p1:abc
p2:acbp3:bac
p4:bcap5:cabp6:cba构造运算表o如下：
o
p1 p2 p1 p1 p2 p2 p2 p1 p3 p3 p4 p4 p4 p3 p5 p5 p6 p6
p6
p5
第七章 图论
6.1第164页
p3 p4 p3 p4 p5 p6 p1
p2 p6
p5 p2 p1 p4
p3
p5 p6 p5 p6 p3 p4 p6 p5 p1 p2 p4 p3 p2
p1
1.画出图G??V,E,??的图示，指出其中哪些图是简单图。 （1）
v2e3v1e4v3e5e6e1e2v4不是简单图。
（2）
v3e8e9e10e5e6e1e2v4e3v1不是简单图。
v5e7v2e4（3）
e1v1e2e5v3e7e8v5v4e6v7e10v8v2e9v6e11e3e4是简单图。
2.写出图7-8的抽象数学定义。 （1）解：G??V,E,??，其中
V?{1,2,3,4}，
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?L?am?x（其中，
a1,a2,L,am?x都是偶数），为偶数。
与奇数个人握手的人，这些人的握手次数之和为b1?b2?L?bx（其中，b1,b2,L,bx为
?b2?L?bx也要为偶数，即
基数），由于所有人的握手次数之和偶数，因此b1(b1?b2?L?bx)mod2?0
又因为
(b1?b2?L?bx)mod2?b1mod2?b2mod2?L?bxmod2
?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的两个图不同构。
证明：给这两幅图标上对应的结点编号，如下：
1De121'?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}?}同构。
除这两个子图以外，对应a）中的子图G3??V3,E3,?3?，V2?{1,5,7,3}，
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)?
解：对于图b）中的点d?，其出度为：dG?(d?)?3，入度：dG?(d?)?0。而在a)图中不存在这样的结点。因此这两个图不同构。
10．证明：任何阶大于1的简单无向图必有两个结点的度数相等。
证明：考虑一个有n个结点的连通图（如果有一个孤立结点，去掉孤立结点考虑联通子图）。因为是无向连通图，每个结点的最大度数是n-1，最小度数是1。即对n个点赋值，共n-1种取值，由抽屉原理，必有两个结点的取值相同，即必有两个点的度数相同。
11．设n阶无向图G有m条边，其中nk个结点的度数为k，其余结点的度数为k+1，证明：
nk?(k?1)n?2m。
证明：由题意，结点数为n，由总边数建立关系：
m?
nk?k?(n?nk)(k?1)，由此可得：nk?(k?1)n?2m。
2
离散数学第二版(6-7章)
