2010-2011离散数学(B)

试题编号：

2010-2011学年第二学期 离散数学试卷（期末）（B卷）（闭卷）

题 号 得 分 评卷人 一 二 三 四 五 六 七 八 九 十 总分 一、求命题公式(p诋q)r的主析取范式，并根据主析取范式写出

相应的主合取范式。（10分）

二、用命题推理理论构造下列推理。（10分）

sp,q； 前提:p(qr),刳结论:s?r。

离散数学试卷第 1 页 共 5 页

三、设A={a,b,c,d},R={,,,},画出R的关系图，并写出r(R)、s（R）、t(R)。(10分)

四、画出偏序集<{1,2,3,4,5,6,8,10,11,12,18,24}、整除>的哈斯图，并写出该偏序集的极大极小元。(10分)

五、判断下面推理的有效性。(10分)

不存在能表示为分数的无理数，有理数都能表示为分数，因此，有理数都不是无理数。

离散数学试卷第 2 页 共 5 页

六、设R是A上的等价关系,且A/R={{1,2,3},{4,5,6},{7}},试求(1)A; (2)R。 (10分)

七、1. 画出以（2，2，2，2，2，2）为度序列的简单图两个和非简单图1个。 (6分)

2. 画出权为1,2,3,4,5,6,7,8的一棵最优二叉树,并计算出它的权。(6分)

离散数学试卷第 3 页 共 5 页

八. 设D=为4阶有向图，V={v1,v2,v3,v4},已知D的邻接矩阵为

轾0犏犏0犏A=犏0犏犏0臌2000110100 11（1）求D中各顶点的入度与出度；

（2）求D中长度为1，3的通路数和回路数。(10分)

九、(1) 证明 若二部图Km,n(m,n32)是哈密顿图，则必有m=n。(5分)

(2) 设G为n（n≥3）阶无向简单图，边数m=证明G是哈密顿图。(5分)

1(n-1)(n-2)+2，2离散数学试卷第 4 页 共 5 页

十、(1)设G是阶数n?11的无向平面图，证明G和G不可能全是平面图。(5分)

(2)设G为n（n?3）阶极大平面图，证明G的对偶图G*是2-边连通的3-正则图。(3分)

离散数学试卷第 5 页 共 5 页