离散数学期末试卷06-07

《离散数学》试卷第1页共7页安徽大学2006—2007学年第二学期《离散数学》考试试卷（B卷）一、选择题（每小题2分，共20分）1．在自然数集合N上，下列运算中可结合的是（）A.baba*；B.),max(*baba；C.baba2*；D.baba*。2．R为实数集，运算*定义为：Rba,，||*baba，则代数系统R,*是（）A.半群；B.独异点；C.群；D.阿贝尔群。3．下列代数系统中，哪个是独异点（）A.R,，其中22baba；B.R,，其中333baba；C.I,max，其中max为求两数中较大数；D.I+,GCD，其中GCD为最大公约数。（R：实数集，I：整数集，I+：正整数集）4．下列集合对于指定运算，构成群的为（）A.非负整数集关于数的加法运算；B.整数集关于数的减法运算；C.正实数关于数的除法运算；D.一元实系数多项式集合关于多项式加法。5．下面哪个集合关于指定运算构成整环（）A.},|2{3Zbaba，关于数的加法和乘法；B.{n阶实数矩阵}，关于矩阵的加法和乘法；C.},|2{Zbaba，关于数的加法和乘法；D.},|{Zbaabba，关于矩阵的加法和乘法。6．下面给出了一些偏序集的哈斯图，其中哪个不是格（）A.；B.；C.；D.。7.下面哈斯图（图1-7）表示的格中哪个元素无补元（）？A.a；B.c；C.e；D.f。图1-78．给定平面图G如图1-8所示，则G中面的个数及面的总次数分别为（）《离散数学》试卷第2页共7页A.4，20；B.4，22；C.5，22；D.5，24。图1-89．设G是具有w个连通分支的平面图，若G中有n个结点，m条边，k个面，则必有（）A.2kmn；B.wkmn；C.1wkmn；D.1wkmn。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}，G,*为群，其中*为模12乘法，则5的阶（即周期）为__________，G,*有__________个真子群。2．令A={a,b,c}，A,*是群，a是单位元，则2b=__________，c的阶（即周期）为__________。3．设}8,4,0{H，12,H是群1212,N的子群，其中}11,...,2,1,0{12N，12是模12加法，则1212,N有__________个真子群，H的左培集H3__________，H4__________。4．若连通平面图G有4个结点，3个面，则G有__________条边。5．设T是无向树，它有40个1度点，20个2度点，31个3度点，且没有6度或6度以上的顶点。则T中有__________个4度点，有__________个5度点。6．无向图G是有k（2k）棵树组成的森林，至少要添加_______条边才能使G成为一棵树。三、综合题（每小题6分，共18分）1．Q为有理数集，Q上定义运算*为：abbaba*。（共6分）（1）求Q,*的幺元；（2分）（2）求Q,*中元素a的逆元（若存在逆元）；（2分）（3）求2*（-5）；7*21。（2分）2．图3-2是格L所对应的哈斯图。（共6分）《离散数学》试卷第3页共7页（1）若a,b,d,0的补元存在，写出它们的补元；（2分）（2）L是否是有补格？说明理由；（2分）（3）L是否是分配格？说明理由。（2分）图3-23．画出所有具有6个顶点的无向树。（6分）四、证明题（每小题8分，共40分）1．设,*G是一个群，证明：对于G中任意的dcba,,,,1111,,,dcba，如果11**caca，11**dada，11**cbcb。则有11**dbdb。2．设G是交换群，证明G中一切有限阶元素所成集合H是G的一个子群。c1abde0《离散数学》试卷第4页共7页3．设,L为一个格，试证明：,L为分配格的充要条件是对于任意的Lcba,,，有)*(*)(cbacba。4．证明在无向完全图Kn中（3n）任意删去n-3条边后，所得到的图是哈密尔顿图。5．设简单平面图G中结点数7n，边数15m，证明：G是连通的。《离散数学》试卷第5页共7页安徽大学2006—2007学年第二学期《离散数学》考试试题参考答案及评分标准一、选择题（每小题2分，共20分）1．B；2.A；3.B；4.D；5.C；6.C；7.B；8.C；9.D；10.C。二、填空题（每空2分，共22分）1.2，3；2.c,3；3.3,{3,7,11}，{4,8,0}；4.5；5.2，1；6.k-1。三、综合题（每小题6分，共18分）1.解：（1）幺元e=0，因为任Qa,0*a=a=a*0。（2分）（2）当1a时有逆元1aa，使aaaaaaaaaaa*10111*2；（4分）（3）2*（-5）=2+（-5）+10=7；7*1/2=7+1/2-7/2=4。（6分）2.解：（1）ca，ea；cd；10；b不存在。（2）L不是有补格，因为b无补元。（3）L不是分配格，因为cccea*1*)(而eececa0)*()*(，两者不等。3.解：由无向树的性质可知，无向树中的顶点数n和边数m有m=n一12m=2n一2由此可见，6个顶点的无向树中，6个顶点度数之和为10。（1分）因此，6个顶点的无向树中，6个顶点的度数分别为：1,1,2,2,2,2（见图3.3-a）；1,1,1,2,2,3(见图3.3-b,3.3-c)；1,1,1,l,3,3(见图3.3-d)；1,1,1,1,2,4（见图3.3-e）；l,1,1,1,1,5(见图3.3-f)。（3分）因此，具有6个顶点的无向树共有6种。（6分）《离散数学》试卷第6页共7页图3.3（注，直接画出以上六个图形得6分，写出分析过程并正确可得3分。）四、证明题（每小题8分，共40分）1．证明：因为,*G是一个群，则Gyx,，有111*)*(xyyx，exx1*（1分）。所以，daaccbdb*)*(*)*(**11（2分）=)*(*)*(*)*(11daaccb（3分）=)*(*)*(*)*(11111dacacb（4分）=)*(*)*(*)*(1111111dacacb（5分）=)*(*)*(*)*(11111111daaccb（6分）=11111111*)*(*)*(*daaccb（7分）=11*db（8分）2．证明：(1)He，所以H；（2分）(2)对任Hyx,，存在Znm,，使exm，eyn，G是交换群，eyxyxnmnmmn),(，即xy也是有限阶元素，所以Hxy；（6分）(3)对任Hx，存在Zm，使exm，所以eexxmm111)()(，所以Hx1。（8分）3．证明：设,L是分配格。由aca*，)*()*(cbcb，可得)*()*()*(cbacbca，而)*()*(*)(cbcacba所以)*(*)(cbacba。（2分）反之，若对于任意的Lcba,,，有)*(*)(cbacba，则可得ccabcba*)*)((*)(《离散数学》试卷第7页共7页ccab*))*((由已知条件cbca*))*(()*()*(cbca由已知条件（6分）又由cbaca*)(*和cbacb*)(*，可得cbacbca*)()*()*(于是有)*()*(*)(cbcacba（8分）4．证明：我们已经知道，一个n阶无向简单图是哈密尔顿图的充分条件是：图中任意不同两点的度数之和大于等于n。（2分）现证在无向完全图Kn中任意删去n-3条边后所得的图G，其不同两点的度数之和大于等于n。用反证法。设图G中存在两点vi和vj，其度数之和不大于等于n，即deg(vi)+deg(vj)n-1删去这两个点后，至多删去图G中的n-1条边，由题设条件可知，图G的边数)1()3(2)1()1(nnnnnm12)3)(2(nn（6分）由此可知，在图G中删去点vi和vj后，余下的图为具有n-2个点，且至少有12)3)(2(nn条边，但这样的简单无向图是不存在的。因为具有n-2个点的简单无向图最多有2)3)(2(nn条边。所以图G中任意不同的两点的度数之和大于等于n，图G为哈密尔顿图。（8分）5．证明：设G为非连通的，具有2个连通分支GGG,...,,21。设iG的结点数为in，边数为im，,...,2,1i。若存在1jn，则必为2，因为只有此时G为一个平凡图并上一个6K才能使其边数为15，可是6K不是平面图，这矛盾于G为平面图这个事实，所以不存在1jn。（2分）若存在2jn，jG中至多有一条边（简单图），另外5个结点构成5K时边数最多，但其值也仅为10条边，这与G有15条边矛盾。（4分）综上所述，in必大于等于3，,...,2,1i。由简单平面图可得：63iinm，,...,2,1i求和得：63nm。（6分）将7n，15m代入得：162115。这与2矛盾。故G必为连通图。（8分）