江南大学离散数学考卷A
江 南 大 学 考
考试形式开卷（ ）、闭卷（ ），在选项上打（√）
开课教研室 命题教师 命题时间 使用学期
1
试 卷 专 用 纸
总张数 教研室主任审核签字
江 南 大 学 考
2
试 卷 专 用 纸
4.设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（ ）
5.图 中 从v1到v3长度为3 的通路有（ ）条。
A． 0； B． 1；
C． 2；
D． 3。
6.在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。 A．1；
B．2；
C．3；
D．4 。
7.设S{ 1, 2, 3 }，定义SS上的等价关系
R{a,b,c,d | a,bSS,c,dSS,adbc}则由 R产 生的，
则SS上一个划分共有（ ）个分块
A．4； B．5； C．6； D．9 。 8.设S{ 1, 2, 3 }，S上关系R的关系图为
江 南 大 学 考
则R具有（ ）性质。
A．自反性、对称性、传递性；
B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 。 9.在如下各图中（ ）欧拉图。
10.设A={1，2，3}，则A上的二元关系有（ ）个。 A． 23 ； B． 32 ； C． 233； D． 322。
三、计算解答题〖40分〗
1．(10)设P→(Q∧┑R)∧(┑P→R)，画出真值表，并求主合取范式。
3
试 卷 专 用 纸
2. （7分）设集合A={a，b，c，d}上的关系R={ , , , }用矩阵运算求出R的传递闭包t (R)。 3. （10分）权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。
江 南 大 学 考
4.(8分)如下图所示的赋权图表示某七个城市v1,v2,,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。(求最小生成树及权)
5.(5分)给出下图的欧拉路（按算法的方法） V1
v3 e3 v4
4
试 卷 专 用 纸
四、证明题〖20分〗
1. (6分)设T是无回路的连通图，证明：ev1，其中e是边数，v 是 结点数。
2. (7分)f和g都是群到的同态映射，证明是的一个子群。其中C={x|xG1且f(x)g(x)}
3. (7分)设G=为连通图，且e∈ E。证明：当且仅当e是G的割边时，e才在G的每棵生成树中。