3. 在图G??V,E?中,结点总度数与边数的关系是( ) (A)deg(vi)?2E (B) deg(vi)?E(C)
?deg(v)?2E(D) ?deg(v)?iiv?Vv?VE
4. 设D是有n个结点的有向完全图,则图D的边数为( ) (A)n(n?1) (B)n(n?1) (C)n(n?1)/2 (D)n(n?1)/2 5. 无向图G是欧拉图,当且仅当( )
(A) G的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数
(C)G连通且所有结点的度数都是偶数 (D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分）
1. 求命题公式p?q?r的主合取范式与主析取范式。（6分）
解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4
主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r) ∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)= ∑1.3.5.6.7
?1??1M???A?a,b,c,d2. 设集合上的二元关系R的关系矩阵为R?0??0?（10分） r(R),s(R),t(R)的关系图。
000??011?,求r(R),s(R),t(R)的关系矩阵，并画出R，
000??001??
3 无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？（10分） 解：∵G（V,E），| E |=V，d（Vi）<3, 设至少有x个节点，由握手定理得： 2×12=∑d（Vi）<6×3+(x-6)×3 2<(x-6) =＞ x>8
故G中至少有9个节点。
4 求下面两个图的最小生成树。（12分）
5. 试判断(z,?)是否为格？说明理由。（5分）
解：（Z,≤）是格，理由如下：
对于任意a∈Z，a≤a成立，满足自反性；
对于任意a∈Z，b∈Z，若a≤b且b≤a，则a=b，满足反对称性； 对于任意a，b，c∈Z，若a≤b，b≤c，则a≤c，满足传递性；
而对于任意a，b∈Z，a≤b，b为最小上界，a为最大下界，故（Z，≤）是格。
（注：什么是格？
四．证明题（共37分）
1. 用推理规则证明A?B,(?B?C)??C,?(?A?D)??D。（10分）
）
证明： 编号 （1） （2） （3） （4） （5） （6） （7） （8）
公式 （?B∨C）∧?C ?B∨C，?C ?B A→B ?A ?（?A∧D） A∨?D ?D 依据 前提 （1） （2） （3） （3）（4） 前提 （6） （5）（6）
2. 设R是实数集，f:R?R?R,f(a,b)?a?b，g:R?R?R,g(a,b)?ab。求证：f和g都是满射，但不是单射。（10分）
证明：要证f是满射，即?y∈R,都存在（x1，x2）∈R×R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；
再证g是满射，即?y∈R，,都存在（x1，x2）∈R×R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；
最后证f不是单射，f（x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g（x1，x2）=g（x2，x1），取x1≠x2，即证得。
3. 无向图G有9个结点，每个结点的度数不是5就是6，求证：G中至少有5个6度结点或6个5度结点。（10分） 证明：设G中至多有4个6度结点且5个5度结点， ∴d（Vi）=49不是偶数， 故它不是一个图，矛盾。 （下面只供参考，个人答案）
4. 设平面上有100个点，期中任意两点间的距离至少是1，则最多有300对点距离恰好为1。（7分） 证明：设任意两点间的读书和恰好为1，则满足： ∑d（Vi）=2e d（Vi）≤6 ∴6×100≥2e e≤300
故最多只有300条边，即300对点距离恰好为1.