离散数学08A解答

第1页共8页得分评阅人暨南大学考试试卷教师填写2008–2009学年度第1学期课程名称：代数结构与图论授课教师姓名：陈双平考试时间:_2009年1月_14日课程类别必修[√]选修[]考试方式开卷[]闭卷[√]试卷类别[A]共8页考生填写学院(校)专业班(级)姓名学号内招[]外招[]题号一二三四五六七八九十总分得分一、填空题（共8小题，每小题2分，共16分）1.设A={3，6，9}，A上的二元运算*定义为：a*b=min{a，b}，则在独异点A，*中，单位元是，零元是.2.设〈G，+〉是一个独异点，则若a有逆元，b，x∈G，x+a=b，则x=ba-13.n阶无向完全图Kn的边数是，每个结点的度数是4.一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，T的顶点数为5.在自然数集N上，下列哪种运算是可结合的？（）A．a*b=a-bB．a*b=max{a，b}C．a*b=a+2bD．a*b=|a-b|6.下列代数系统(G,)中，其中是加法运算。()不是群。(A)G为整数集合(B)G为偶数集合(C)G为有理数集合(D)G为自然数集合7.设a是12阶群的生成元，则a2是()阶元素，则a5是阶元素。第2页共8页暨南大学《代数结构与图论》试卷考生姓名、学号：得分评阅人得分评阅人8.以下各图，其中不存在哈密顿回路的图是（ABD）。ABCD二、判断题（共9小题，每小题1分，共9分）1.不连通平面图的对偶图是连通的。（）2.少于4个点的图一定是平面图。（）3.欧拉图一定满足欧拉公式。（）4.群不一定是半群。（）5.分配有补格就是布尔代数。（）6.完美匹配一定也是完备匹配（）7.点色数小于边色数。（）8.设N为自然数集合，I为整数集合，是算术乘法，则N,与I,同构。）9.设R,,为整环，|R|=n，则R,,是域。（）三、证明题（共3小题，每小题6~10分，共24分）1.（8分）在K6的边上涂上红色或蓝色，证明对于任意一种随意的涂法，总存在红色K3或蓝色K3。2.（10分）设(G,)为循环群，生成元为a，设(A,)和(B,)均为(G,)的子群，而ai和aj分别为(A,)和(B,)的生成元。①证明(A∩B,)是(G,)的子群。②请问：(A∩B)是否为循环群。如果是，请给出其生成元。第3页共8页暨南大学《代数结构与图论》试卷考生姓名、学号：得分评阅人4，3.（6分）n个顶点的连通图至少有n-1条边。四、求解题（5小题，每小题7分，共35分）1.设M={1,2,3,4}，M上的置换122344311234，试计算1,并将结果写成对换321和轮换的形式。1第4页共8页暨南大学《代数结构与图论》试卷考生姓名、学号：0111101002.已知有向图D（如右图）的邻接矩阵为A(D)0110101求从v2到v4长度为2的通路条数和从v3到v3长度为3的回路条数，并将它们具体写出。解：v2到v4长度为2的通路条数为2条（1.5分）分别是v2v3v4和v2v1v4（2分）v3到v3长度为3的回路条数为2条（1.5分）分别是v3v4v1v3和v3v2v1v3（2分）第5页共8页暨南大学《代数结构与图论》试卷考生姓名、学号：3.画出3阶2条边的所有非同构有向简单图。4.有向图G如图所示。（1）求a到d的最短路和距离；（2）求d到a的最短路和距离；（3）判断G是哪类连通图，是强连通的？是单向(侧)连通的？还是弱连通的？（4）求出全部不同构的初级回路第6页共8页暨南大学《代数结构与图论》试卷考生姓名、学号：得分评阅人5.对于如下带权图。利用克鲁斯克尔(kruskal)算法求一棵最小生成树。请给出具体步骤（或者在生成树上标出边添加的顺序）。五、计算题（共2小题，每小题6~10分，共16分）1.(6分)判断以下映射是否为同态映射，如果是，说明它是否为单同态和满同态。（1）G为群，:GG,(x)e,xG，其中e是G的幺元。（2）GZ,为整数加群，:GG,(n)2n,nZ。（3）G1R,,G2R,，其中R为实数集，R为正实数集，+和·分别为普通加法和乘法，:G1G,(x)ex,xR。第7页共8页暨南大学《代数结构与图论》试卷考生姓名、学号：2.（10分）对以下定义的集合和运算判别它们能否构成代数系统？如果能，请说明是构成哪一种代数系统，并简要说明理由。（1）S1{1,1/2,2,1/3,3}，*为普通乘法。（2）S20,1,为普通乘法。（3）S3{0,1,n1},n为任意给定的正整数且n2,*为模n乘法，为模n加法。（4）S4{0,1,2,3},为小于等于关系。（5）S5{1,2,3,6},﹡和+分别表示最小公倍数和最大公约数。