权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal）算法。 [典型例题]
例1 在具有n个顶点的完全图Kn中删去多少条边才能得到树？ 解：n个顶点的完全图Kn中共有n?（n-1）/2条边， n个顶点的树应有n-1条边，
于是，删去的边有：n?（n-1）/2-（n-1）=（n-1）?（n-2）/2 例2 求下面有限图中点u到各点间的最短路。（图上数字见教材
P231，第3题。）
解 u?u1 ， d(u, u1)=1, 路(u, u1)
u? u2 , d(u, u2)=9, 路(u, u4, u3, u7, u2) u? u3 , d(u, u3)=5, 路(u, u4, u3 ,) u? u4 , d(u, u4)=3, 路(u, u4 )
u? u5 , d(u, u5)=11, 路(u, u1, u5)或路 (u, u4, u3 , u7 , u2 , u5)
u? u6 , d(u, u6)=13, 路(u, u1, u5, u6)
16
u? u7 , d(u, u7)=8, 路(u, u4 , u3 , u7) u? u8 , d(u, u8)=11, 路(u, u4, u8)
u?v, d(u, v)=15, 路(u, u1, u5 , u6 ,v) 或路(u, u4 , u3 , u7 , u6 ,v)
二、考核说明
本课程的考核实行形成性考核和终结性考核的形式。形成性考核占总成绩的20%，以课程作业的形式进行（共三次，由中央电大统一布置）；终结性考核即期末考试，占总成绩的80%。总成绩为100分，60分及格。
期末考试实行全国统一闭卷考核，试卷满分为100。由中央电大统一命题，统一评分标准，统一考试时间（考试时间为120分钟）。
1、试题类型
试题类型有填空题（分数约占20%）、单项选择题（分数约占14%）、计算题（分数约占50%）和证明题（分数约占16%）。
填空题和单项选择题主要涉及基本概念、基本理论，重要性质和结论、公式及其简单计算。计算题主要考核学生的基本运算技能，要求书写计算、推论过程或理由。证明题主要考查应用概念、性质、定理及主要结论进行逻辑推理的能力，要求写出推理过程。
2、考核试卷题量分配
试卷题量在各部分的分配是：集合论约占40%，数理逻辑约占40%，图论约占20%。
17
具体课程考核情况见课程考核说明。
附录：试题类型及规范解答举例 [填空题]
1. 设R 是集合A上的二元关系，如果关系R同时具有 性、
对称性和 性，则称R是等价关系。
2. 命题公式G=（P?Q）?R，则G共有 个不同的解释；
把G在其所有解释下所取真值列成一个表，称为G
的 ；解释（?P，Q，?R）或（0，1，0）使G的真值为 。
3. 设G=（P，L）是图，如果G是连通的，并且 ，则G
是树。如果根树T的每个点v最多有两棵子树，则称T为 。
[单项选择题]（选择一个正确答案的代号，填入括号中） 1. 由集合运算定义，下列各式正确的有（ ）。
A．
X?X?Y B.X?X?Y C.X?X?Y D.Y?X?Y
2. 设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），
（b，b），（b，c），（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，则R2是R1的（ ）闭包。 A．自反 B．对称 C．传递 D．以上都不是
3. 设G是由5个顶点组成的完全图，则从G中删去（ ）条
18
边可以得到树。
A．4 B．5 C．6 D．10 [计算题] 1. 化简下式：
（A?B?C）?（（A?B）?C）?（A?B?C）?（A?B?C） 2. 通过求主析取范式判断下列命题公式是否等值。
（1）（P?Q）?（?P?Q?R）；
（2）（P?（Q?R））?（Q?（?P?R））；
3. 求图中A到其余各顶点的最短路径，并写出它们的权。
B 7 C
1
2
A 2 5 3
D
4
6
E 1 F
[证明题]
1. 利用基本等价式证明下面命题公式为恒真公式。
（（P?Q）?（Q?R））?（P?R）
2. 用形式演绎法证明：{P?Q， R?S，P?R }蕴涵Q?S。 试题答案及评分标准
19
[填空题] 1、 2、 3、
自反；传递 8；真值表；1 无回路；二叉树
[单项选择题]（选择一个正确答案的代号，填入括号中） 1、 A 2、 B 3、C [计算题] 1. 解：
（A?B?C）?（（A?B）?C）?（A?B?C）?（A?B?C） =（A?~B?~C）?（A?~B?C）?（A?B?~C）?（A?B?C） =（（A?~B）?（~C?C））?（（A?B）?（~C?C）） =（（A?~B）?E）?（（A?B）?E） E为全集 =（A?~B）?（A?B） = A?（~B?B） = A?E = A 2. 解：
（P?Q）?（?P?Q?R） ?（P?Q?（?R?R））?（?P?Q?R） ?（P?Q??R）?（P?Q?R）?（?P?Q?R） ? m6?m7?m3 ? m3?m6?m7
20
《离散数学(第三版)》方世昌-的期末复习知识点总结资料(良心出品必属精品)
