离散数学期末试卷06-07(2).doc

安徽大学20062007学年第 二 学期 离散数学 考试试卷（B卷）一、选择题（每小题2分，共20分）1在自然数集合N上，下列运算中可结合的是（ ） A. ； B. ；C. ； D. 。2R为实数集，运算*定义为：，则代数系统是（ ） A. 半群； B. 独异点； C. 群； D. 阿贝尔群。3下列代数系统中，哪个是独异点（ ） A. ，其中； B. ，其中；C. ，其中max为求两数中较大数； D. ，其中GCD为最大公约数。（R：实数集，I：整数集，I+：正整数集）4下列集合对于指定运算，构成群的为（ ）A. 非负整数集关于数的加法运算； B. 整数集关于数的减法运算；C. 正实数关于数的除法运算； D. 一元实系数多项式集合关于多项式加法。5下面哪个集合关于指定运算构成整环（ ） A. ，关于数的加法和乘法； B. n阶实数矩阵，关于矩阵的加法和乘法； C. ，关于数的加法和乘法； D. ，关于矩阵的加法和乘法。6下面给出了一些偏序集的哈斯图，其中哪个不是格（ ） A.； B.； C.； D.。7. 下面哈斯图（图1-7）表示的格中哪个元素无补元（ ）？ A. a ； B. c ； C. e ； D. f 。图1-78给定平面图G如图1-8所示，则G中面的个数及面的总次数分别为（ ） A. 4，20 ； B. 4，22 ； C. 5，22 ； D. 5，24 。 图1-89设G是具有个连通分支的平面图，若G中有个结点，条边，个面，则必有（ ） A. ； B. ； C. ； D. 。10设G=(V,E)为(n,m)连通图，则要确定G的一颗生成树必删去G中边数为（ ）An-m-1 ； B n-m+1 ； Cm-n+1 ； Dm-n-1 。二、填空题（每空2分，共22分）1 设G=1,5,7,11，为群，其中*为模12乘法，则5的阶（即周期）为_，有_个真子群。2 令A=a,b,c，是群，a是单位元，则=_，c的阶（即周期）为_。3 设，是群的子群，其中，是模12加法，则有_个真子群，的左培集_，_。4 若连通平面图G有4个结点，3个面，则G有_条边。5 设T是无向树，它有40个1度点，20个2度点，31个3度点，且没有6度或6度以上的顶点。则T中有_个4度点，有_个5度点。6 无向图是有（）棵树组成的森林，至少要添加_条边才能使成为一棵树。三、综合题（每小题6分，共18分）1 Q为有理数集，Q上定义运算*为：。（共6分）（1） 求的幺元；（2分）（2） 求中元素a的逆元（若存在逆元）；（2分）（3） 求2*（-5）；7*。（2分）2 图3-2是格L所对应的哈斯图。（共6分）（1） 若a,b,d,0的补元存在，写出它们的补元；（2分）（2） L是否是有补格？说明理由；（2分）c1abde0（3） L是否是分配格？说明理由。（2分）图3-23 画出所有具有6个顶点的无向树。（6分）四、证明题（每小题8分，共40分）1 设是一个群，证明：对于中任意的,，如果，。则有。2 设G是交换群，证明G中一切有限阶元素所成集合H是G的一个子群。3 设为一个格，试证明：为分配格的充要条件是对于任意的，有。4 证明在无向完全图Kn中（）任意删去n-3条边后，所得到的图是哈密尔顿图。5 设简单平面图中结点数，边数，证明：是连通的。安徽大学20062007学年第 二 学期 离散数学 考试试题参考答案及评分标准一、选择题（每小题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，因为任, 0*a=a=a*0。（2分）（2）当时有逆元，使；（4分）（3）2*（-5）=2+（-5）+10=7；7*1/2=7+1/2-7/2=4。（6分）2.解：（1），；不存在。（2）L不是有补格，因为b无补元。（3）L不是分配格，因为而，两者不等。3.解：由无向树的性质可知，无向树中的顶点数n和边数m有 m=n一1 2m=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分）图3.3（注，直接画出以上六个图形得6分，写出分析过程并正确可得3分。）四、证明题（每小题8分，共40分）1 证明：因为是一个群，则，有，（1分）。所以， （2分） = （3分） = （4分） = （5分） = （6分） = （7分） = （8分）2 证明：(1)，所以；（2分）(2)对任，存在，使，G是交换群，即也是有限阶元素，所以；（6分）(3)对任，存在，使，所以，所以。（8分）3 证明：设是分配格。由，可得，而所以。（2分）反之，若对于任意的，有，则可得 由已知条件 由已知条件 （6分）又由和，可得于是有 （8分）4 证明：我们已经知道，一个n阶无向简单图是哈密尔顿图的充分条件是：图中任意不同两点的度数之和大于等于n。（2分）现证在无向完全图Kn中任意删去n-3条边后所得的图G，其不同两点的度数之和大于等于n。用反证法。设图G中存在两点vi和vj，其度数之和不大于等于n，即deg(vi)+deg(vj)n-1删去这两个点后，至多删去图G中的n-1条边，由题设条件可知，图G的边数 （6分）由此可知，在图G中删去点vi和vj后，余下的图为具有n-2个点，且至少有条边，但这样的简单无向图是不存在的。因为具有n-2个点的简单无向图最多有条边。所以图G中任意不同的两点的度数之和大于等于n，图G为哈密尔顿图。（8分）5 证明：设为非连通的，具有个连通分支。设的结点数为，边数为，。若存在，则必为2，因为只有此时为一个平凡图并上一个才能使其边数为15，可是不是平面图，这矛盾于为平面图这个事实，所以不存在