有回路。（否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则
mi?ni?1,i?1?k ,
kk ?ni?n?11,?mi?mi?1i?1kk
?28?m??mi??(ni?1)?n?k?11?ki?1i?1 矛盾）
下面用反证法证明G为非平面图。
假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3 。于是G
的每个面至少由g (g?3)条边围成，由点、边、面数的关系
m?g(n?k?1)g?2，得：
28?m?g3(11?k?1)?(11?(k?1))?3(11?(1?1))?3?11?3?2?27g?23?1
而 28?27矛盾，所以G为非平面图。
''（2）当n>11时，考虑G的具有11个顶点的子图G，则G或G必为非平面图。
'如果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逆元均为其本身。所以，<{0，1}，+>是Abel群。 ②<{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 ；? ③·对+的分配律 对?x,y?{0,1}
Ⅰ 0·（x+y）=0=0+0=(0·x)+(0·y) Ⅱ 1·（x+y）
''当x=y (x+y)=0 则
?0?0??(1?0)?(1?0)?1?(x?y)?1?0?0???????(1?x)?(1?y)?1?1??(1?1)?(1?1)?
当x?y（x?y?1）则
?1?0??(1?1)?(1?0)?1?(x?y)?1?1?1???????(1?x)?(1?y)0?1(1?0)?(1?1)????
所以?x,y,z?{0,1}均有z?(x?y)?(z?x)?(z?y) 同理可证：(x?y)?z?(x?z)?(y?z) 所以·对+ 是可分配的。
由①②③得，<{0，1}，+，·>是环。 （2）<{0，1}，+，·>是域
因为<{0，1}，+，·>是有限环，故只需证明是整环即可。 ①乘交环： 由乘法运算表的对称性知，乘法可交换。 ②含幺环：乘法的幺元是1 ③无零因子：1·1=1≠0
因此[{0，1}，+，·]是整环，故它是域。
二十三、
树的应用 20%
1、（10分）解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：
树权C(T)=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 Y Y N N Min Y Y N N + Y Y Y N 一、 填空 30% （每空 3分）
1、 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）
的点集”则A= 。 2、 集合A={?,{?}}的幂集P(A) = 。 3、 设A={1，2，3，4}，A上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R
的关系图
。 4、 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},
则A?B= 。
A?B= 。
5、 设|A|=3，则A上有 个二元关系。
6、 A={1，2，3}上关系R= 时，R既是对称的又是反对称的。
7、 偏序集?A,R??的哈斯图为
则
，
R?= 。
8、 设|X|=n，|Y|=m则（1）从X到Y有 个不同的函数。
（2）当n , m满足 时，存在双射有 个不同的双射。 9、 2是有理数的真值为 。 10、
自
Q：我将去上海，R：我有时间，公式(Q?R)?(R?Q)的
然
语
言
为 。 11、
公式(Q?P)?(?P?Q)的 主
合
取
范
式
是 。 12、 则
若S?{S1 ,S2 ,?, Sm}是集合A的一个分划，
它
应
满
足 。
二、 选择 20% （每小题 2分）
1、 设全集为I，下列相等的集合是（ ）。
}； B、B?{x|? y(y?I?x?2y)}； A、A?{x|x是偶数或奇数C、C?{x|? y(y?I?x?2y?1)}； D、D?{x|0,1,?1,2,?2,3,?3,4,?4,?}。 2、 设S={N，Q，R}，下列命题正确的是（ ）。 A、2?N,N?S 则2?S； B、N?Q,Q?S 则N?S； C、N?Q,Q?R 则N?R； D、??N,??S 则??N?S。
S与?S?3、 设C={{a},{b},{a,b}}，则分别为（ ）。
S?CS?CA、C和{a,b}；B、{a,b}与?；C、{a,b}与{a,b}；D、C与C 4、 下列语句不是命题的有（ ）。
A、 x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚； D、太阳系以外的星球上有生物； E、你打算考硕士研究生吗？ 5、 (P?Q)?R的合取范式为（ ）。
A、(P??Q)?R ；B、(P?R)?(?Q?R) ； C、
(P??Q?R)?(P??Q??R)?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P??Q?R)