代数结构与图论暨南大学2012(A)答案

第1页共8页暨南大学考试试卷得分评阅人一、填空题（共7小题10空，每空2分，共20分）1.把置换表示成互不相交轮换的积是(1364)(25)；表示成对换的积是(13)(16)(14)(25)。2.设S是非空有限集，代数系统（P(S),∪,∩）中，P(S)对∪运算的么元是______________，P(S)对∩运算的么元是____S_______。3.无向图G中有6条边，3度与5度顶点各1个，其余的都是2度顶点，则图G中共有_____4____个顶点。4.无向图G如右图所示，则图G的割点为____d___________；割边为_____e5_________。5.设f为群(G,*)到群(H,o)的同构映射，e为(H,o)的幺元，则(G,*)的幺元为_____)(1ef__________。6.设某有限布尔格共有n个原子，则该有限布尔格的元素个数是__n2_______。7.图G的点连通度k、边连通度l和最小度d的大小关系是____dlk________。教师填写2012–2013学年度第___1______学期课程名称：_____代数结构与图论______________授课教师姓名：____陈双平_____________考试时间:___2013___年___1_____月_17___日课程类别必修[√]选修[]考试方式开卷[]闭卷[√]试卷类别答案[A]共8页考生填写学院(校)专业班(级)姓名学号内招[]外招[]题号一二三四五六七八九十总分得分123456356124adcbee2e1e3e4e5暨南大学《代数结构与图论》试卷A卷考生姓名、学号：第2页共8页得分评阅人二、选择题（共7小题，每小题2分，共14分）1.n阶k度正则图的边数应为（D）。A．n(n-1)/2B．nC．n(n+1)D．nk/22.设G是有n个顶点，m条边的无向简单图，并且m=n-1，则下列（B）是正确的。A．G一定是树B．G不一定是树C．G一定不是树D．以上说法都不对3.格不具有D（A）交换律(B)幂等律（C）吸收律（D）全上界4.拉格朗日定理不涉及的概念是D（A）陪集(B)有限群（C）子群（D）元素的阶5.关于图正确的是C（A）零图不是图(B)树不是二部图（C）竞赛图是有向图（D）欧拉图没有奇圈6.（多选）下列不是域的有ABC（A）布尔代数(B)整数（C）格（D）实系数多项式7.关于图正确的是C（A）欧拉图是平面图(B)平面图是连通的（C）货郎担问题有解说明有哈密顿回路（D）K5是平面图暨南大学《代数结构与图论》试卷A卷考生姓名、学号：第3页共8页得分评阅人三、证明题（共2小题，每小题8～10分，共18分）1.（8分）设G为群，a为G中的给定元素，a的正规化子N(a)表示G中与a可交换的元素构成的集合，即N(a)={x|x∈G∧xa=ax},证明N(a)为G的子群.证明：ea=ae故e∈N(a)，N(a)非空（2分）a-1a=aa-1故a-1∈N(a)设任意x,y∈N(a)则axy=xay=xya所以xy∈N(a)（2分）对于任意x∈N(a)，x的逆元x-1存在，下面证明x-1∈N(a)由ax=xa，左右同乘两个x-1，可知x-1axx-1=x-1xax-1即x-1a=ax-1根据定义x-1∈N(a)（3分）因此N(a)为a的子群（1分）如有其他答案能得到一些要点可以酌情给分。2.（10分）一棵树T有8片树叶，2个3度分支点，其余的分支点都是4度顶点，问T有多少个4度分支点？请画出4棵非同构的树.暨南大学《代数结构与图论》试卷A卷考生姓名、学号：第4页共8页解：设有x个4度分支点根据握手定理，以及树的边数m=节点数n-18+2×3+4×x=2（x+8+2-1）所以化简得14+4x=18X=2（2分）非同构的树有六种，任意4个即可，每个2分得分评阅人四、计算题（4小题，每小题6～10分，共32分）1.（10分）5阶轮图，求它的支配数γ0，点覆盖数α0，点独立数β0，匹配数β1，边覆盖数α1，最小度δ，最大度Δ，点色数χ，边色数χ’,面色数S。解：5阶轮图指的五个点的轮，故不难得出：（每个1分）γ0=1α0=3β0=2β1=2α1=3δ=3Δ=4χ=3χ’=4S=3暨南大学《代数结构与图论》试卷A卷考生姓名、学号：第5页共8页2.（6分）G=a是15阶循环群.(1)求出G的所有生成元.(2)求出G的所有子群解：（1）与15互质的是12478111314（2分）因此aa2a4a7a8a11a13a14（2分）（2）因为15的因子有1，3，5，15因此G的所有子群为（2分）aa3a5a153.（10分）有向图D如图所示:D中有几种非同构的圈？D中有几种非圈的非同构的简单回路？D是哪类连通图？D中长度等于3的通路共有多少条？其中有几条是回路？（需给出计算步骤）答：3种（1分），长度分别为1，2，3（1分）4种，长度分别为3456D是强连通，也是单向连通和弱连通（2分）它的邻接矩阵为0100100101010011A（2分）1001011110120112A20111111302231124A3（2分）因此共有24条通路7条回路（2分）暨南大学《代数结构与图论》试卷A卷考生姓名、学号：第6页共8页4.（6分）对以下定义的集合和运算判别它们能否构成代数系统？如果能，请说明是构成哪一种代数系统，并简要说明理由。（1）,1,02S为普通乘法。（2）nnS},1,1,0{3为任意给定的正整数且,*2n为模n乘法，为模n加法。（3）},6,3,2,1{5S﹡和+分别表示最小公倍数和最大公约数。解：（1）代数系统，封闭，具有单位元1，零元0，满足交换律，结合律，因此是含幺半群，也就是独异点，但0不可逆，不是群，（2分）（2）封闭，n为质数时为域，n不是质数时，它是交换环和含幺环，但不是无零因子环（2分）（3）是格也是布尔代数（2分）暨南大学《代数结构与图论》试卷A卷考生姓名、学号：第7页共8页得分评阅人五、简答题（共3小题，每小题4～8分，共16分）1.（4分）用文氏图画出充分条件、必要条件、充分必要条件之间的关系。答：一般来说，应该满足以下关系，如果图形对可得3分，其他酌情给分2.（8分）代数系统S,+,*什么时候是整环。答：S,+是交换群封闭性半群结合律独异点0可逆群交换群交换律(1分)S,*是半群封闭性半群结合律(1分)乘法关于加法的分配律(1分)以上说明它是环(1分)乘法交换律交换环(1分)乘法单位元1含幺环(1分)乘法无零因子无零因子环(1分)故是整环(1分)以上每个最好有详细说明暨南大学《代数结构与图论》试卷A卷考生姓名、学号：第8页共8页3.（4分）举出生活中碰到的4种可以抽象为图的例子.答：网络拓扑交通路线学生分组/选课社交圈相亲等合理的每个给1分