发布时间 : 星期四 文章离散数学习题集（十五套）更新完毕开始阅读
用 00000传送 5；00001传送 6；0001传送 7；100传送 3；101传送 4；001传送 2；11传送 1；01传送 0 （频率越高传送的前缀码越短）。
十九、
10%
证明：
（1） 乘：由运算表可知运算*是封闭的。
（2） 群：即要证明(x*y)*z?x*(y*z)，这里有43=64个等式需要验证
但：① e是幺元，含e的等式一定成立。
②ab=a*b=b*a，如果对含a，b的等式成立，则对含a、b、ab的等式也都成立。③剩下只需验证含a、b等式，共有23=8个等式。即：
(a*b)*a=ab*a=b=a*(b*a)=a*ab=b； (a*b)*b=ab*b=a=a*(b*b)=a*e=a； (a*a)*a=e*a=a=a*(a*a)=a*e=a ； (a*a)*b=e*b=b=a*(a*b)=a*ab=b； (b*b)*a=e*a=a=b*(b*a)=b*ab=a； (b*b)*b=e*b=b=b*(b*b)=b*e=b； (b*a)*a=ab*a=b=b*(a*a)=b*e=b ； (b*a)*b=ab*b=a=b*(a*b)=b*ab=a 。 （3） 幺： e为幺元
（4） 逆：e -1=e ；a -1=a ；b -1=b ； (ab) -1=ab 。 所以
一、 填空 15% （每小题 3分）
1、 n阶完全图Kn的边数为 。
2、 右图
的邻接矩A= 。
3、 图
的
对
偶
为 。
4、 完全二叉树中，叶数为nt，则边数m= 。
5、 设< {a,b,c}, * >为代数系统，* 运算如下： * a b c a a b c 阵
图
b c b c a c c c 则它的幺元为 ；零元为 ；
a、b、c的逆元分别为 。
二、 选择 15% （每小题 3分）
1、 图 相对于完全图的补图为（ ）。
2、 对图G 则
k(G),?(G),?(G)分别为（ ）。
A、2、2、2； B、1、1、2； C、2、1、2； D、1、2、2 。
3、 一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，
则T中有（ ）片树叶。
A、3； B、4； C、5； D、6
4、 设 +，·>是整环。 A、{x|x?2n,n?Z}； B、{x|x?2n?1,n?Z}； 4C、{x|x?0,且x?Z}； D、{x|x?a?b5,a,b?R}。 5、 设A={1，2，?，10 }，则下面定义的运算*关于A封闭的有（ ）。 A、 x*y=max(x ,y)； B、x*y=质数p的个数使得x?p?y； C、x*y=gcd(x , y)； (gcd (x ,y)表示x和y的最大公约数)； D、x*y=lcm(x ,y) （lcm(x ,y) 表示x和y的最小公倍数）。 三、 证明 45% n2m?4。1、设G是（n,m）简单二部图，则（8分） 2、设G为具有n个结点的简单图，且 m?1(n?1)(n?2)2则G是连通图。（8分） 3、设G是阶数不小于11的简单图，则G或G中至少有一个是非平图。（14分） 4、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下： + 0 1 证明它是一个环，并且是一个域。（15分） 0 0 1 1 1 0 · 0 0 1 0 0 1 0 1 四、 生成树及应用 10% 1、（10分）如下图所示的赋权图表示某七个城市 v1,v2,?,v7及预先测算出它们之间的一些直接通信线路 造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。 2、（10分）构造H、A、P、N、E、W、R、对应的前缀码， 并画出与该前缀码对应的二叉树，写出英文短语HAPPY NEW YEAR的编码信息。 五、 5% 对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。 Max Min + 可结合性 可交换性 存在幺元 存在零元 答案： 二十、 填空 15%（每小题3分） ?0??0?0 1?n(n?1)?1、2；2、?0 b、没有 二十一、 选择 15%（每小题 3分） 题目 答案 二十二、 证明 45% 1 A 2 A 3 C 1 0110101 1??1?0??0??；3、；4、2(nt?1)；5、a，c，a、 4 D 5 A，C 1、 （8分）：设G=（V，E），V?X?Y,X?n121,Y?n2,则n1?n2?n n2n2m?n1?n2?n1(n?n1)??n?n1n??(n1?)?24 对完全二部图有 n2nn1?2时，完全二部图(n,m)的边数m有最大值4。 当 n2m?(n,m)4。 故对任意简单二部图有 2、 （8分）反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设 G1和G2的顶点数分别为n1和n2，显然n1?n2?n。 ?n1?1n2?1?n1?n?1n2?n?1 ?m?n1(n1?1)n2(n2?1)(n?1)(n1?n2?2)(n?1)(n?2)???2222 11?10?552条，因而必有G与假设矛盾。所以G连通。 3、（14分）（1）当n=11时，G?G?K11K11边数 m'?或G的边数大于等于28，不妨设G的边数m?28，设G有k个连通分支，则G中必