安徽大学2006—2007学年
A.4，20 ； B.4，22 ； C.5，22 ； D.5，24 。
图1-8
9．设G是具有w个连通分支的平面图，若G中有n个结点，m条边，k个面，则必有（ ） A.nmk2 ； B.nmkw ； C.nmkw1 ； D.nmkw1 。
10．设G=(V,E)为(n,m)连通图，则要确定G的一颗生成树必删去G中边数为（ ） A．n-m-1 ； B． n-m+1 ； C．m-n+1 ； D．m-n-1 。
二、填空题（每空2分，共22分）
1．设G={1,5,7,11}，为群，其中*为模12乘法，则5的阶（即周期）为__________，有__________个真子群。
2．令A={a,b,c}，是群，a是单位元，则b2=__________，c的阶（即周期）为__________。 3．设H{0,4,8}，H,12是群N12,12的子群，其中N12{0,1,2,...,11}，12是模12加法，则N12,12有__________个真子群，H的左培集3H__________，4H__________。 4．若连通平面图G有4个结点，3个面，则G有__________条边。
5．设T是无向树，它有40个1度点，20个2度点，31个3度点，且没有6度或6度以上的顶点。则T中有__________个4度点，有__________个5度点。
6．无向图G是有k（k2）棵树组成的森林，至少要添加_______条边才能使G成为一棵树。
三、综合题（每小题6分，共18分）
1．Q为有理数集，Q上定义运算*为：a*babab。（共6分）
（1） 求的幺元；（2分）
（2） 求中元素a的逆元（若存在逆元）；（2分）
（3） 求2*（-5）；7*12。（2分）
2．图3-2是格L所对应的哈斯图。（共6分）
《
离散数学
》试卷
（1） 若a,b,d,0的补元存在，写出它们的补元；（2分） （2） L是否是有补格？说明理由；（2分） （3） L是否是分配格？说明理由。（2分）
1 a d b e c 0 图3-2 3．画出所有具有6个顶点的无向树。（6分）
四、证明题（每小题8分，共40分）
1．设G,*是一个群，证明：对于G中任意的a,b,c,d,a1,b1,c1,d1，如果a*ca1*c1，a*da1*d1，b*cb1*c1。则有b*db1*d1。
2．设G是交换群，证明G中一切有限阶元素所成集合H是G的一个子群。
《
离散数学
》试卷
3．设L,为一个格，试证明：L,为分配格的充要条件是对于任意的a,b,cL，有(ab)*ca(b*c)。
4．证明在无向完全图Kn中（n3）任意删去n-3条边后，所得到的图是哈密尔顿图。
5．设简单平面图G中结点数n7，边数m15，证明：G是连通的。
《
离散数学
》试卷
安徽大学2006—2007学年
图3.3 （注，直接画出以上六个图形得6分，写出分析过程并正确可得3分。）
四、证明题（每小题8分，共40分）
1．证明：因为G,*是一个群，则x,yG，有(x*y)1y1*x1，x*x1e（1分）。所以，
（2分）
=(b*c)*(c1*a1)*(a*d) （3分） b*db*(c*c1)*(a1*a)*d =(b1*c1)*(a*c)1*(a1*d1) （4分） =(b1*c1)*(a1*c1)1*(a1*d1) （5分） =(b1*c1)*(c1*a1)*(a1*d1) （6分）
=b1*(c1*c1)*(a1*a1)*d1 （7分）
=b1*d1 （8分）
2．证明：
(1)eH，所以H；（2分）
(2)对任x,yH，存在m,nZ，使xme，yne，G是交换群，(x,y)mnxmnymne，即xy也是有限阶元素，所以xyH；（6分） (3)对任xH，存在mZ，使xme，所以(x1)m(xm)1e1e，所以x1H。（8分）
3．证明：
设L,是分配格。由a*ca，(b*c)(b*c)，可得
(a*c)(b*c)a(b*c)，而(ab)*c(a*c)(b*c) 所以(ab)*ca(b*c)。（2分）
反之，若对于任意的a,b,cL，有(ab)*ca(b*c)，则可得
(ab)*c((ba)*c)*c
《
离散数学
》试卷
1111(b(a*c))*c 由已知条件 ((a*c)b)*c
(a*c)(b*c) 由已知条件 （6
分）
又由a*c(ab)*c和b*c(ab)*c，可得
(a*c)(b*c)(ab)*c
于是有(ab)*c(a*c)(b*c) （8分）
4．证明：
我们已经知道，一个n阶无向简单图是哈密尔顿图的充分条件是：图中任意不同两点的度数之和大于等于n。（2分）
现证在无向完全图Kn中任意删去n-3条边后所得的图G，其不同两点的度数之和大于等于n。 用反证法。
设图G中存在两点vi和vj，其度数之和不大于等于n，即
deg(vi)+deg(vj)n-1 删去这两个点后，至多删去图G中的n-1条边，由题设条件可知，图G的边数
m(n1) n(n1)22
(n3)(n1)
1 （6(n2)(n3)分）
(n2)(n3)2(n2)(n3)21由此可知，在图G中删去点vi和vj后，余下的图为具有n-2个点，且至少有但这样的简单无向图是不存在的。因为具有n-2个点的简单无向图最多有
条边，
条边。所以图G中任意不同的两点的度数之和大于等于n，图G为哈密尔顿图。（8分）
5．证明：
设G为非连通的，具有2个连通分支G1,G2,...,G。设Gi的结点数为ni，边数为mi，i1,2,...,。
若存在nj1，则必为2，因为只有此时G为一个平凡图并上一个K6才能使其边数为15，可是K6不是平面图，这矛盾于G为平面图这个事实，所以不存在nj1。（2分）
若存在nj2，Gj中至多有一条边（简单图），另外5个结点构成K5时边数最多，但其值也仅为10条边，这与G有15条边矛盾。（4分）
综上所述，ni必大于等于3，i1,2,...,。由简单平面图可得：
mi3ni6，i1,2,...,
求和得：m3n6。（6分）将n7，m15代入得：152161。这与2矛盾。故G必为连通图。（8分）
《
离散数学
》试卷
