《2022年离散数学试卷八试题与答案.docx》由会员分享，可在线阅读，更多相关《2022年离散数学试卷八试题与答案.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 试卷八试卷与答案一、填空 15% （每道题 3 分）1、 n 阶完全图 K n的边数为；3、 图的对偶2、 右图的邻接矩阵A= ；图为；4、 完全二叉树中,叶数为 nt,就边数 m= ；5、 设 为代数系统, * 运算如下：* a b c 就它的幺元为；零元为；a a b c a、b、c 的逆元分别为；b b a c 二、挑选 15% （每道题 3 分）c c c c 1、 图相对于完全图的补图为（）；2、 对图 G 就kG ,G,G分别为（）；A 、2、2、 2； B 、1、1、2； C、2、1、2； D、1、2、 2 ；3、 一棵无向树T
2、有 8 个顶点, 4 度、 3 度、 2 度的分枝点各1 个,其余顶点均为树叶,就 T 中有（）片树叶；A、3； B、4； C、5； D、6 1 / 6 名师归纳总结 - - - - - - -第 1 页,共 6 页精选学习资料 - - - - - - - - - 4、 设是代数系统,其中+, 为一般的加法和乘法,就A= （）时 是整环；Z； B、x|x2nb,1nZ；R ；A 、x|x2n,nZ； D、x|xa45,a ,bC、x|x0 ,且x5、 设 A=1 ,2, , 10 ,就下面定义的运算* 关于 A 封闭的有（）；A、x*y=maxx ,y ； B、x*y= 质数 p 的个数使得x
3、py；C、x*y=gcdx , y ； gcd x ,y 表示 x 和 y 的最大公约数 ；D、x*y=lcmx ,y （lcmx ,y 表示 x 和 y 的最小公倍数）；三、证明 45% 2nm1、设 G 是（ n,m）简洁二部图,就 4；（ 8 分）m 1 n 1 n 2 2、设 G 为具有 n 个结点的简洁图,且 2 就 G 是连通图；（ 8 分）3、设 G 是阶数不小于 11 的简洁图,就 G 或G 中至少有一个是非平图；（14 分）4、记“ 开” 为 1,“ 关” 为 0,反映电路规律的代数系统 0 ,1 ,+,的加法运算和乘法运算；如下：+ 0 1 15 分）0 1 0 0 0 0
4、 0 1 1 1 0 1 0 1 证明它是一个环,并且是一个域；（四、生成树及应用 10% 1、（ 10 分）如下图所示的赋权图表示某七个城市v 1,v 2,v 7及预先测算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间既能够通信而且总造价最小；2、（ 10 分）构造 H、A、P、N、E、W、R、对应的前缀码,并画出与该前缀码对应的二叉树,写出英文短语 HAPPY NEW YEAR 的编码信息；2 / 6 名师归纳总结 - - - - - - -第 2 页,共 6 页精选学习资料 - - - - - - - - - 五、5% 对于实数集合 R,在下表所列的二元远算是否具有
5、左边一列中的性质,请在相应位上填写“ Y ” 或“N” ；Max Min + 可结合性可交换性存在幺元存在零元答案：1、1n一、填空 15% （每道题3 分）2 tn1； 5、 a,n1 0101； 3、； 4、00110100；2、01102c,a、b、没有二、挑选 15% （每道题 3 分）n2E）,题目1 2 3 4 5 答案A A C D A,C 三、证明 45% 1、 （8分）：设G=（V,VXY,Xn 1,Yn2,就n 1n 2n对完全二部图有mn1n2n 1nn 12 n 1n 1nn 1n224G1、G2,假设当n 1n时,完全二部图n,m 的边数 m 有最大值n2；24故对任
6、意简洁二部图n,m 有mn2；42、 （8 分）反证法：如G 不连通,不妨设G 可分成两个连通分支G1和 G2的顶点数分别为n1和 n2,明显n 1n2n；n 11n 21n 1n1n 2n13 / 6 名师归纳总结 - - - - - - -第 3 页,共 6 页精选学习资料 - - - - - - - - - mn 1n 11 n 2 n21n1 n 1n22 n1 n2 2222与假设冲突；所以 G 连通； 11 103、（ 14 分）（ 1）当 n=11 时,G G K 11 K 11 边数 m2 55条,因而必有 G 或 G 的边数大于等于 28,不妨设 G 的边数 m 28,设 G
7、 有 k 个连通分支,就 G中必有回路；（否就 G 为 k 棵树构成的森林,每棵树的顶点数为 ni,边数 m i,就k km i n i ,1 i 1 k , i 1 n i n 11 ,i 1 m i mk k28 m m i n i 1 n k 11 ki 1 i 1 冲突）下面用反证法证明 G 为非平面图；假设 G 为平面图,由于 G 中有回路且 G 为简洁图,因而回路长大于等于 3 ；于是 Gm g n k 1 的每个面至少由 g g 3 条边围成,由点、边、面数的关系 g 2,得：28mgg2 11k1 33111k1 3 1111 3113227而2827冲突,所以G 为非平面图；
8、 G ,就 G 或 G 必为非平面图；（2）当 n11 时,考虑 G 的具有 11 个顶点的子图假如 G 为非平面图,就G 为非平面图；假如 G 为非平面图,就G 为非平面图；4、 （15 分）1）0 ,1 ,+,是环0 ,1 ,+是交换群乘：由“+” 运算表知其封闭性；由于运算表的对称性知：+运算可交换；群：（ 0+0）+0=0+（0+0）=0 ；（ 0+0）+1=0+（0+1）=1；（ 0+1） +0=0+（1+0）=1 ；（ 0+1）+1=0+（1+1）=0；（ 1+1） +1=1+（1+1）=0 结合律成立；幺：幺元为 0；逆： 0,1 逆元均为其本身；所以,是 Abel 群；4 /
9、6 名师归纳总结 - - - - - - -第 4 页,共 6 页精选学习资料 - - - - - - - - - 是半群乘：由“ ” 运算表知封闭群： 0 0 0=0 （ 00）=0 ；（ 00）1=0 （ 01）=1；（ 0 1）0=0 （ 1 0）=1 ；（ 01）1=0 （ 11） =0；（ 1 1）1=1 （ 1 1）=0 ； 对 +的安排律对x , y01,x+0 y 0 （ x+y ）=0=0+0=0 1 （ x+y ）当 x=y x+y=0 就1xy100001z 10 10 1x 1y11 11 11当xy（xy1）就0 1 10 1x 1y11111xy 01 10 11所
10、以x,y,z0 1,均有zxyxzy同理可证：xyzxz yz所以 对 + 是可安排的；由得, 是环；（2）是域由于 是有限环,故只需证明是整环即可；乘交环：由乘法运算表的对称性知,乘法可交换；含幺环：乘法的幺元是 1 无零因子： 11=1 0 因此 0 , 1 ,+,是整环,故它是域；四、 树的应用 20%1、（ 10 分）解：用库斯克（Kruskal ）算法求产生的最优树；算法略；结果如图：5 / 6 名师归纳总结 - - - - - - -第 5 页,共 6 页精选学习资料 - - - - - - - - - 树权 CT=23+1+4+9+3+17=57 即为总造价五、 （10 分）由二叉树知H、A 、P、Y 、N、E、W、 R 对应的编码分别为000、001、010、011、100、 101、 110、111；明显 000 ,001,010,011,100,101, 110,111 为前缀码；英文短语 HAPPY NEW YEAR 的编码信息为000 001 010 010 011 100 101 001 001 101 001 111 六、 5%可结合性Max Min + Y Y Y 可交换性Y Y Y 存在幺元N N Y 存在零元N N N 6 / 6 名师归纳总结 - - - - - - -第 6 页,共 6 页