代数结构与图论暨南大学2009年考试题答案

第1页共8页暨南大学考试试卷得分评阅人一、填空题（共10空，每空2分，共20分）1.设A={2，4，6，8}，A上的二元运算*定义为：a*b=max{a，b}，则在独异点A，*中，单位元是2，零元是8。2.n个结点的无向完全图nK的边数为n(n-1)/2，其点色数是n，如n为奇数，其边色数是n。3.用于判断非平面图的一个特殊的完全二部图是K3,3，它是否存在完美匹配？是。4.设G是n(n≧3)阶m条边的简单平面图，这m和n之间满足什么关系？m=3n-6。5.什么是消去律？任意x,y,z,x不等于零元，则xy=xz=y=z,且yz=zx=y=z6.什么是幂等律？任意x,n为正整数xn=x教师填写2009–2010学年度第___1______学期课程名称：_____代数结构与图论______________授课教师姓名：____陈双平_____________考试时间:____2010_____年__1______月_21___日课程类别必修[√]选修[]考试方式开卷[]闭卷[√]试卷类别[B]共8页考生填写学院(校)专业班(级)姓名学号内招[]外招[]题号一二三四五六七八九十总分得分暨南大学《代数结构与图论》试卷考生姓名、学号：第2页共8页得分评阅人二、选择题（共7小题，每小题2分，共14分）1.给定下列序列，（D）可以构成无向简单图的结点次数序列。A、（0，1，3，3，3）；B、（1，3，4，4，5）；C、（1，1，2，2，3）；D、（1，1，2，2，2）。2.以下各图，其中存在哈密顿回路的图是（C）。abcd3.下列代数系统（S，*）中，(B)是群。(A)S是整数集合，*是普通乘法(B)S={1,3,5},*是模6的乘法(C)S是有理数集合，*运算是普通乘法(D)S={0,1,3,5},*是模7的乘法4.设G是简单有向图，关联矩阵P(G)刻画下列（A）关系。A、点与边；B、边与点；C、点与点；D、边与边。5.一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（D）。A、7；B、8；C、5；D、9。6.集合对（C）运算封闭。A、减法；B、乘法；C、加法；D、。7.设是偏序格，其中N是自然数集合，“≧”是普通的数间“大于等暨南大学《代数结构与图论》试卷考生姓名、学号：第3页共8页于”关系，则有（D）。A、a；B、b；C、max(a，b)；D、min(a，b)。得分评阅人三、证明题（共3小题，每小题8分，共24分）1.设（G，*）是群，（A，*）和（B，*)是它的两个子群，C={a*b|a∈A,b∈B}.证明：若*满足交换律，则（C，*）也是(G，*）的子群。证明：显然C非空（2分）设a,c属于A,b,d属于B，由a*b属于C,c*d属于C,（1分）由*满足结合律（2分）a*b*(c*d)-1=a*b*d-1*c-1由*满足交换律（2分）a*b*(c*d)-1=a*c-1*b*d-1=（a*c-1）*（b*d-1）因此，由子群判定定理知它也是子群（1分）2.设（G，*）是n元有限群，e为单位元，a1,a2,…,an是G的任意n个元素，不一定两两不同。试证：存在正整数p和q，1≦p≦q≦n,使得ap*ap+1*…*aq=e.证明：（2分）设Mi=a1*a2*…ai则有n个值，如果存在某个p使得Mp=e则结论成立。（2分）如果不存在这样的p，那么由于n元群中只有n-1中取值可能利用鸽巢定理必存在ij,使得Mi=Mj（2分）即a1*a2*…ai=a1*a2*…aj利用群的性质（2分）消去a1*a2*…ai暨南大学《代数结构与图论》试卷考生姓名、学号：第4页共8页a1+i*a2+i*…aj=e.故知结论成立3.设G为n阶有向简单图，每个点的出度大于等于3，证明G中存在长度大于等于4的圈。证明：任取点v1由v1的出度大于等于3（1分），又G是简单图（1分），那么存在v2使得v1v2为一条边（1分）同样，由v2的出度大于等于3，又G是简单图，则必存在不同于v1的点v3使得v2v3为一条边（2分）。同样对于v3而言其出度大于等于3，则其存在不同于v1和v2的点v4使得v3v4为一条边（1分）。而对于v4，要么v4v1为边，此时就是长度为4的圈。要么这个过程可以继续下去，类推可知最后必形成一个长度至少为4的圈（2分）。暨南大学《代数结构与图论》试卷考生姓名、学号：第5页共8页得分评阅人四、计算题（共3小题，每小题8~10分，共26分）1.（8分）设M={1,2,3,4}，M上的置换13424321，12344321，试计算1,并将结果写成对换和轮换的形式。解：分）分））（）（（分）（分）2)(13)(12(241232414332212(234314211243342112.（8分）画出3阶有向完全图有3条或4条边的所有非同构的生成子图。解：都是有个3个点每个图1分暨南大学《代数结构与图论》试卷考生姓名、学号：第6页共8页3.（10分）有向图G如图所示。（1）求a到d的最短路和距离；（2）求d到a的最短路和距离；（3）判断G是哪类连通图，是强连通的？是单向(侧)连通的？还是弱连通的？（4）求出全部的初级回路和全部的简单回路。（5）求出长度为3的初级通路数解：（1）aed，距离2.（1分）（2）deba,距离无穷.（1分）（3）单向连通（1分）弱连通（1分）（4）初级回路：长度为2的和长度为3的（1分）长度为2的ede(1分),长度为3的bdeb(1分)的简单回路：edebaeb(1分),（5）10种(2分)暨南大学《代数结构与图论》试卷考生姓名、学号：第7页共8页得分评阅人五、简答题（共2小题，每小题6~10分，共16分）1.（10分）对以下定义的集合和运算判别它们能否构成代数系统？如果能，请说明是构成哪一种代数系统，并说明理由。（1）},,2,1,0{1nS，为普通加法。（2）,1,0,12S为普通乘法。（3）nnS},1,1,0{3为任意给定的正整数且,*2n为模n乘法，为模n加法。（4）},3,2,1,0{4S为大于等于关系。（5）},6,3,2,1{5S﹡和+分别表示最小公倍数和最大公约数。解：(1)不是代数系统(1分)，不封闭,nn不在集合中(1分)(2)是独异点（1分），封闭，可结合，有单位元1，但是0的逆元不存在（0.5分）(3)n为素数时，S3是整环和域(1分)，n不是素数时，S3是交换环、含幺环但不是无零因子环,如n=62*3=0(1分).(4)分配格（1分），但不是有补格（1分）。(5)布尔代数（2分）暨南大学《代数结构与图论》试卷考生姓名、学号：第8页共8页2.(6分)什么是环？什么是整环？什么是域？什么是格？什么是布尔代数？答：环就是加法构成交换群，乘法构成半群，乘法对加法适合分配率的代数系统。（2分）整环既是交换环、含幺环、也是无零因子环。（1分）域就是除零意外的所有元素都有逆的整环。（1分）格是任意两个元素都有最小上界和最大上界的偏序集。（1分）布尔代数就是有补分配格。（1分）