离散数学试卷及答案(21)

离散数学试卷（二十一）137一、问答10%已知定义在集合},,,{dcba上的运算*如下表：试问：1）},,,,{dcba是代数系统否？（）2）},,,,{dcba是子群否？（）3）},,,,{dcba是群否？（）4）},,,,{dcba有单位元否？（）5）},,,,{dcba满足交换律否？（）二、填空10%下表中的运算均定义在实数集上，请在相应的空格中打“√”或填上具体实数（不满足或无该项者不填）+-×结合律交换律幺元（含左、右幺元）零元（含左、右零元）*abcdaabcdbbadcccdbaddcab离散数学试卷（二十一）138三、有向图的矩阵表示应用15%已知某有向图的邻接矩阵如下：00011011110001004321vvvvA试求：3v到1v的长度为4的有向路径的条数。四、图的同构15%下面两图是否同构，若是给出点集间的同构映射。五、树的性质15%已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）。六、最小生成树15%使用普里姆算法求下图的最小生成树七、自同构映射10%令},,,2{为普通加法QbabammR，定义映射g：RR为2)2(babag，试证：g是,R到,R的自同构映射。八、群与子群10%设,G是阶为6的群，证明它至多有一个阶为3的子群。v1v2v3v4离散数学试卷（二十一）139一、解：题号12345答案√√√√√二、解：+-×结合律√×√交换律√×√幺元（含左、右幺元）00（右幺元）1零元（含左、右零元）××0三、解：0001101111000100A，01001201101210112A，10112123130112013A，12013513313421234A，由3v到1v长度为4的有向路径的条数为3条。四、解：两有向图点集的同构映射为:f5514433221,,,,vvvvvvvvvv所以两有向图是同构的。五、解：设该树有t片树叶，总结点数为ttvd29443322)(总边数为ttve814321所以，29+t=2·(8+t)即t=13。该树有13片树叶。六、解：离散数学试卷（二十一）140七、解：①g是R，+上的同态映射)2(111bam，Rbam)2(222)()()2()2(2)()()2)()(()22()(21221121212121221121mgmgbababbaabbaagbabagmmg②g是R，+上的满射Rbam)2(，Rbam2使mbababagmg22)()2()(所以g是R，+上的满射。③g是R，+上的单射)2(111bam，Rbam)2(222，且21mm则2)(,2)(222111bamgbamg，如果)()(21mgmg则21212121,,02)()(bbaabbaa必有这与21mm矛盾。故)()(21mgmg。由①，②，③知g是从R，+到R，+的自同构映射。八、解：①G有一个3阶子群因为在G中除e外，G中元素的阶不可能都为2，否则G是交换群[事实上：ababbabaxxexGx11112)(,,,]，所以任取两个非幺元元素a,b，则{e,a,b,ab}是G的一个子群，其阶数为4，而4不能整除6，得出矛盾。于是，Gg，使eg且egg，从而g的周期为3或6。若g的周期为3，则（g）是3阶子群。若g的周期为6，则(g2)的阶数为3，即得证G有一个3阶子群。②G只有一个3阶子群若G有两个三阶子群H和H/，则HH是H和H/得子群，那么HH的阶只可能为1和3。（i）若HH的阶为3，则H=H/；（ii）若HH的阶为1，即HH={e}离散数学试卷（二十一）141GHHHHHHHH6933这里GHaHbHaabHHHa}{且得出矛盾。由①，②知命题成立。