三、证明 50%
n2m?4。1、设G是（n,m）简单二部图，则（10分）
2、设G为具有n个结点的简单图，且
m?1(n?1)(n?2)2，则G是连通图。（10分）
3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：
+ 0 1 0 0 1 1 1 0
· 0 0 1 0 0 1 0 1 证明它是一个环，并且是一个域。（14分） 4、 [L,?,?]是一代数格，“≤”为自然偏序，则[L，≤]是偏序格。（16分）
四、10%
设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x2?x3)是布尔代数[{0,1},?,?,?]上的一个布尔表达式，试写出E(x1,x2,x3)的析取范式和合取范式（10分）
五、10%
如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。
答案：
一、填空 15%（每小题3分）
1、n-1；2、n(k+1)-2m；3、如右图；4、0 ；5、臂力小者 二、选择 15%（每小题 3分）
题目 答案 1 D 2 C 3 A 4 A 5 D
三、证明 50% （1） 证：设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） 证：反证法：若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
与假设矛盾。所以G连通。 （3） （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}，·]是半群 乘：由“· ”运算表知封闭
群： （0·0）·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）= 0；
（0·1）·0=0·（1·0）=0 ； （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}，+，·]是整环，故它是域。
4、证：（1 ）“≤”是偏序关系， ≤ 自然偏序 ?a,b?L①反自反性：由代数格幂等关系：a?a?a?a?a。 ②反对称性：?a,b?L 若 a?b,b?a 即：a?b?a,则 a?a?b?b?a?b b?a ③传递性：a?b,b?c则：
a?b?a
b?a?b，
a?c?(a?b)?ca?b即a?b?a?a?(b?c) 结合律?a?b b?c即b?c?b?a a?b即a?b?a
?a?c
（2）?x,y?L在L中存在{x,y}的下（上）确界
设x,y?L则：x?y?inf{x,y}
事实上：x?(x?y)?(x?x)?y?x?y
?x?y?x同理可证:x?y?y
若{x , y }有另一下界c，则c?(x?y)?(c?x)?y?c?y?c
?c?x?y ?x?y是{x , y }最大下界，即x?y?inf{x,y}
同理可证上确界情况。 四、14% 解：函数表为：
x1 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x3 0 1 0 1 0 1 0 1 E(x1,x2,x3) 0 1 0 1 0 1 1 1 E(x1,x2,x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)析取范式：
?(x1?x2?x3)?(x1?x2?x3)
合取范式：E(x1,x2,x3)?(x1?x?2?x3)?(x1?x2?x3)?(x1?x2?x3)
五、10%
解： 用库斯克（Kruskal）算法求产生的最优树。算法为：
w(v1,v7)?1w(v7,v2)?4w(v7,v3)?9w(v3,v4)?3w(v4,v5)?17w(v1,v6)?23结果如图：
选e1?v1v7选e2?v7v2选e3?v7v3选e?v3v4选e?v4v5选e?v1v6
树权C(T)=23+1+4+9+3+17=57（万元）即为总造价 试卷七试题与答案