*7.5 二部图及匹配
7.5.1二部图
在许多实际问题中常用到二部图，本节先介绍二部图的基本概念和主要结论，然后介绍它的一个重要应用—匹配。
定义7.5.1 若无向图,G V E =的顶点集V 能分成两个子集1V 和2V ，满足 （1）12V V V = ，12V V φ= ；
（2）(,)e u v E ?=∈，均有1u V ∈，2v V ∈。
则称G 为二部图或偶图(Bipartite Graph 或Bigraph)，1V 和2V 称为互补顶点子集，常记为
12,,G V V E =。如果1V 中每个顶点都与2V 中所有顶点邻接，则称G 为完全二部图或完全偶图
(Complete Bipartite Graph)，并记为,r s K ，其中12,r V s V ==。
由定义可知，二部图是无自回路的图。 图7-55中，(),(),(),(),(a b c d e 都是二部图，其中(),(),(),()b c d e 是完全二部图
1,32,32,43,3,,,K K K K 。
图7-55二部图示例
显然，在完全二部图中,r s K 中，顶点数n r s =+，边数m rs =。
一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图7-56中()a 可改画成图()b ，图()c 可改画成图()d 。可以看出，它们仍是二部图。
图7-56二部图示例
定理7.5.1 无向图,G V E =为二部图的充分必要条件为G 中所有回路的长度均为偶数。
证明 先证必要性。
设G 是具有互补节点子集1V 和2V 的二部图。121(,,,,)k v v v v 是G 中任一长度为k 的回路，不妨设11v V ∈，则211m v V +∈，22m v V ∈，所以k 必为偶数，不然，不存在边1(,)k v v 。
再证充分性。
设G 是连通图，否则对G 的每个连通分支进行证明。设,G V E =只含有长度为偶数的回路，定义互补节点子集1V 和2V 如下：任取一个顶点0v V ∈，令
10{()(,)}V v v V d v v =∈∧为偶数
21V V V =-
现在证明1V 中任意两节点间无边存在。
假若存在一条边(,)i j v v E ∈，且1,i j v v V ∈，则由0v 到i v 间的最短路（长度为偶数）， 边
(,)i j v v 和j v 到0v 间的最短路（长度为偶数）所组成的回路的长度为奇数，与假设矛盾。
同理可证2V 中任意两节点间无边存在。
故G 中的每条边必具有形式(,)i j v v ，其中1i v V ∈，2j v V ∈， 即G 是具有互补节点子集1V 和2V 的一个二部图。
利用定理7.5.1可以很快地判断出图7-57中的()a 、()c 是二部图，而()b 则不是二部图。
图7-57
例7.5.1 六名间谍,,,,,a b c d e f 被擒，已知a 懂汉语、法语和日语，b 懂德语、俄语和日语，c 懂英语和法语，d 懂西班牙语，e 懂英语和德语，f 懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。 解 以六人,,,,,a b c d e f 为顶点，在懂共同语言的人的顶点间连边得图G （如图7-58()a 所示），因为G 中没有奇圈，所以G 是二部图（如图7-58()b 所示），故至少应有两间房间即可。
图7-58
7.5.2 匹配
二部图的主要应用是匹配，“匹配”是图论中的一个重要内容，它在所谓“人员分配问题”和“最优分配问题”等运筹学中的问题上有重要的应用。
首先看实际中常碰见的问题：给n 个工作人员安排m 项任务，n 个人用12{,,,}n V x x x = 表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中(1)k k ≥个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？
例如，现有12345,,,,x x x x x 五个人，12345,,,,y y y y y 五项工作。已知1x 能胜任1y 和2y ，2x 能胜任2y 和3y ，3x 能胜任2y 和5y ，4x 能胜任1y 和3y ，5x 能胜任3y 、4y 和5y 。如何安排才能使每个人都有工作做，且每项工作都有人做？
显然，我们只需构造这样的数学模型：以i x 和j y （i ，j =1，2，3，4，5）为顶点，在i x 与其胜任的工作j y 之间连边，得二部图G ，如图7-59所示，然后在G 中找一个边的子集，使得每个顶点只与一条边关联（图中粗线），问题便得以解决了。这就是所谓匹配问题，下面给出匹配的基本概念和术语。
图7-59匹配问题示意图
定义7.5.2 设无向图,G V E =，G 中有边集M ?E ，且在M 中任意两条边都没有公共的端点，称边集M 为图G 的一个匹配(Matching)。M 中一条边的两个端点，叫做在M 下是配对的。如果G 中不存在匹配1M ，使得1M M >，则称M 为最大匹配(Maximum Matching)。 对于G 的一个匹配M ，若节点v 与M 中的边关联，则称v 是M 饱和的(Saturated)，否则称v 是M 不饱和的。
定义7.5.3 设二部图12,,G V V E =，M 是G 的一个匹配。若1v V ?∈，v 均是M 饱和的，则称M 是1V 对2V 的完全匹配（简称1V ―完全匹配）；若2v V ?∈，v 均是M 饱和的，则称M 是
2V 对1V 的完全匹配（简称2V —完全匹配）。若M 既是1V ―完全匹配，又是2V ―完全匹配（即
图G 的每个顶点都是饱和的），则称M 是完全匹配(Complete Matching)。
显然，完全匹配是最大匹配，但反之不然。
例7.5.2（1）在图7-59中，边集1122354354{(,),(,),(,),(,),(,)}M x y x y x y x y x y =是一个匹配，而且是是一个最大和完全匹配。
（2）在图7-60()a 中，边集1{(1,5),(2,7),(3,9),(4,8)}M =和2{(1,6),(2,7),(3,9)M =，
(4,8)}都是图G 的最大匹配，也是1V ―完全匹配，但不是完全匹配。在图7-60()b 中，边集{(1,4),(2,5),(3,6)}M =是完全匹配。
图7-60
为了寻求二部图的最大匹配，下面交替路和可扩路两个概念。
定义7.5.4 设12,,G V V E =是一个二部图，M 是图G 的一个匹配，L 是G 中的一条路，如果L 是由属于M 和不属于M 的边交替出现组成，则称L 为G 的M 交替路(Alternating Path)。如果交替路L 的始点和终点都是M 不饱和点，则称L 为G 的M 可扩路(M —Extensible Path)。
例如，在图7-60()a 中，对于匹配{(1,6),(2,7),(3,9)}M =，路1:16273L ，2:27394L ，
3:5394L ，4:51627394L 都是M 交替路，其中34,L L 的始点和终点都是M 不饱和点，所以这
两条路是M 可扩路。
可扩路具有如下性质：可扩路的长度必为奇数，且属于M 的边比不属于M 的边少1条。 如果在一条可扩路中把属于M 中的边从匹配中去掉，把不属于M 中的边添入到匹配中， 则得到新的匹配1M ，1M 的边数比M 多１。例如，在图7-60()a 中，对于匹配
{(1,6),(2,7),(3,9)}M =，4:51627394L 是M 可扩路，将4L 中属于M 中的边(1,6)，(2,7)，(3,9)从匹配M 中去掉， 把不属于M 中的边(5,1),(6,2),(7,3),(9,4)添入到匹配M 中，则得
到新的匹配1{(5,1),(6,2),(7,3),(9,4)}M =，1M 中的边数由M 中的3条增至4条。如果图中还存在可扩路， 再按上面的步骤做， 所得到的匹配的边数又多１，一直到图G 中不存在可扩路为止。用此方法可逐步得到较大的匹配，直至得到最大匹配。这就是下面的定理。
定理7.5.2 在图G 中，M 为最大匹配的充分必要条件是不存在可扩路。 证明 先证必要性。
用反证法。假设G 中存在一条M 可扩路，则可以得到比M 的边数多１的匹配，与M 为最大匹配矛盾。所以G 中不存在M 可扩路。
再证充分性。
用反证法。假设M 不是最大匹配，则存在匹配1M ，使得1M M >。令21M M M =⊕（⊕为对称差运算），设由2M 导出的G 的子图2[]G M H =，因为M 和1M 都是G 的匹配，所以H 的任意顶点或是只与M （或1M ）中的一条边相关联，或是同时与M 的一条边及1M 的一条边相关联，其度数至多为2，于是H 的每个连通分支或者是一个边交错地属于M 与1M 的长度为偶数的回路，或者是边交错地属于M 与1M 的长度为奇数的交错路。 由于1M M >，因而H 中必有一个连通分支P ，它所含的属于1M 的边比属于M 的边多，P 不是回路（因为回路的长度均为偶数），它的起点和终点都是M 不饱和的，也一定是G 中的M 不饱和点，因此在G 中存在关于M 的可扩路，这与假设矛盾。
求一般图的最大匹配过程比较复杂，下面仅讨论如何在二部图中求最大匹配的问题。 设二部图12,,G V V E =，在G 中求最大匹配的关键是寻找可扩路。通常是先构造G 的一个匹配M ，再看1V 中有没有M 不饱和点。 如果没有，那么M 肯定是最大匹配了；如果有， 我们就从这些点出发找M 可扩路，由M 可扩路做出一个更大的匹配。寻找M 可扩路的一个有效方法是标记法， 其过程如下：
首先在G 中作一个匹配M ，用（*）标记1V 中所有M 不饱和点， 然后交替地进行以下步骤（１）和（２）。
（１）选一个1V 的新标记过的节点，比如i x ， 用（i x ）标记不通过M 中的边与i x 邻接且未标记过的2V 的所有节点。 对1V 所有新标记过的节点重复这一过程。
（２）选一个2V 的新标记过的节点，比如j y ， 用（j y ）标记通过M 中的边与j y 邻接且未标记过的1V 的所有节点。对2V 所有新标记过的节点重复这一过程。
执行以上步骤， 直至标记到一个2V 中的M 不饱和点。从该节点倒向追踪到标记有（*）的节点，就得到一条M 可扩路。于是也就得到一个边数为|M |＋１的匹配， 再返回（１）。 如果已不可能标记更多的节点，而2V 的所有标记的节点均为M 饱和点，则说明G 中已不存在M 可扩路，这时M 就是最大匹配。
例7.5.3 图7-61()a 是一个二部图， 求其最大匹配。
图7-61
解 取图7-61图()a 的一个匹配3152{(,),(,)}M x y x y =。用（*）标记1V 中所有M 不饱和点124,,x x x 。
（1）选1V 的新标记过的节点1x ，用（1x ）标记不通过M 中的边与1x 邻接且未标记过的2
V 的节点1y ；类似地，用（2x ）标记2y 。
(2) 选2V 的新标记过的节点1y ， 用（1y ）标记通过M 中的边与1y 邻接且未标记过的1
V 的节点3x ；类似地，用（2y ）标记5x 。
(3) 选1V 的新标记过的节点3x ，因为不存在不通过M 中的边与3x 邻接的2V 的节点，所以不用（3x ）标记2V 的节点；用（5x ）标记3y 或4y ，假定用（5x ）标记3y 。
3y 是M 不饱和点，标记结束。
从3y 倒向追踪到标记有（*）的节点，就得到一条M 可扩路2253x y x y 或4253x y x y ，取前者，由此得匹配1223153{(,),(,),(,)}M x y x y x y =。
对匹配1M 再用标记法（见图7-61()b 知， 图中已不存在1M 可扩路，所以1M 就是最大匹配。
定理7.5.3（霍尔定理） 二部图12,,G V V E =有1V ―完全匹配，当且仅当对1V 中任一子集A ，和所有与A 邻接的点构成的点集()N A ，恒有
()N A A ≥
证明 先证必要性。假设M 是二部图12,,G V V E =的一个1V ―完全匹配，则1V 中的每个顶点均是M 饱和的。对1V 的任一子集A ，因A 的每个顶点在M 下和()N A 中不同的顶点配对，所以有()N A A ≥。
再证充分性。假设G 是满足对任何1V 的子集A ，()N A A ≥的二部图，但G 中没有使1
V 中每个顶点饱和的完全匹配，设1M 是G 的一个最大匹配，由假设，1M 不使1V 中所有顶点饱
和。设v 是1V 中的1M 不饱和点，并设B 是与v 有关于1M 交错路相连通的所有顶点的集合。由于1M 是一最大匹配，由定理7.5.2可知：v 为B 中唯一的1M 不饱和点。
令A =B 1V ，2T B V = ，显然，{}A v -中的顶点都关于1M 饱和，即它与T 中的顶点在1M 下配对，于是1T A =-，且()N A T ?，又因()N A 中的每个顶点有关于1M 交错路与
v 相连通，因此()N A T =，所以
()1N A A A
=-< 与假设()N A A ≥矛盾。
例7.5.4 设有4个人1234,,,x x x x ，现有5项工作12345,,,,y y y y y 需要做，每个人所能胜任工作的情况如图7-62所示，问能否使每个人都能分配到一项工作？
图7-62
解 这个问题即为：二部图12,,G V V E =是否存在1V ―完全匹配。当取A =134{,,}x x x 时，
()N A =25{,}y y ，因此()N A A <，根据霍尔定理，二部图没有1V ―完全匹配，所以要使每
个人都能分配到一项工作是不可能的。
习题7.5
1．求下面两个二部图的最大匹配。
图7-63
2．假定G 是二部图，如何安排G 中顶点的次序可使G 的邻接矩阵呈0
0B C ??
???
形式，0为零矩阵。
3．某单位有7个工作空缺1234567,,,,,,p p p p p p p 要招聘，有10个应聘者1210,,,a a a 。
他们能胜任的工作岗位集合分别为：
156{,,}p p p ，267{,,}p p p ，34{,}p p ，15{,}p p ，67{,}p p ，3{}p ，23{,}p p ，13{,}p p ，1{}p ，5{}p 。如果规定每个应聘者最多只能安排一个工作，试给
出一种分配方案使落聘者最少？
4．设(,)
n m图G是二部图，证明
2
4
n
m≤。
7.6 平面图
7.6.1 平面图的定义
在一些实际问题中，常常需要考虑一些图在平面上的画法，希望图的边与边不相交或尽量少相交。如印刷电路板上的布线、线路或交通道路的设计、地下管道的铺设等。下面举一个简单的例子。
例7.6.1 一个工厂有3 个车间和 3 个仓库。为了工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？
如图7-64()a所示，A，B，C是3个车间，M，N，P是3座仓库。经过努力表明，要想建造不相交的道路是不可能的，但可以使交叉点最少（如图7-64()b所示）。此类实际问题涉及到平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。本节介绍平面图的一些基本概念和常用结论。
图7-64
定义7.6.1设,
G V E
=是一无向图。如果能把G的所有节点和边画在平面上，使得任何两条边除公共端点外没有其他的交点，则称G是一个平面图(Planar Graph)，或称该图能嵌入平面；否则，称G是一个非平面图。
直观上说所谓平面图就是可以画在平面上，使边除端点外彼此不相交的图。应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。
图7-65平面图和非平面图示例
例如，图7-65()a 是无向完全图3K ，它是平面图。图7-65()b 是无向完全图4K ，它表面上看有相交边，但是把它画成图()c ， 则可以看出它是一个平面图。图()d 是平面图。图()e 经改画后得到图()f ，图()g 经改画后得到图()h ，由定义知它们都是平面图。而图()i 、()j 是无向完全图5K ，5K 和图7-64中的两个图3,3K ，无论怎样调整边的位置，都不能使任何两边除公共端点外没有其他的交点，所以它们不是平面图，它们是两个最基本、最重要的非平面图，在平面图理论的研究中有非常重要的作用。
设G 是平面图，G 的以无交边的方式画在平面上的图称为平面图G 的平面嵌入(Imbedding)。如图7-65 中的()c 、()f 、()h 分别为图()b 、()e 、()g 的平面嵌入。
关于平面图，以下两个结论是显然的。
定理7.6.1 若G 是平面图，则G 的任何子图是平面图。
定理7.6.2 若G 是非平面图，则G 的任何母图是非平面图。
推论：无向完全图(5)n K n ≥和二部图3,(3)n K n ≥都是非平面图。
定义7.6.2 设,G V E =是平面图。将G 嵌入平面后，由G 的边将G 所在的平面划分为若干个区域，每个区域称为G 的一个面(Face)。其中面积无限的面称为无限面或外部面(Exterior Face)，面积有限的面称为有限面或内部面(Interior Face)。包围每个面的所有边组成的回路称为该面的边界(Bound)，边界长度称为该面的次数(Degree)，面R 的次数记为deg()R 。
例如，图7-65()a 共有2两个面，每个面的次数均为3。7-65()c 共有4四个面，每个面的次数均为3。图7-65()f 共有3个面，每个面的次数均为4。图7-65()h 共有6个面，每个面的次数均为3。图7-66所示平面图G 有4个面，1deg()3R =，2deg()3R =，3R 的边界为1078910e e e e e ，3deg()5R =，0R 的边界为167986542e e e e e e e e e ，0deg()9R =。
图7-66
关于面的次数，我们有下述定理。
定理7.6.3 在一个有限平面图G 中，所有面的次数之和等于边数的二倍，即
1
deg()2r
i
i R m ==∑
其中，r 为G 的面数，m 为边数。
证明 注意到等式的左端表示G 的各个面次数的总和，在计数过程中，G 的每条边或者是两个面的公共边界，为每一个面的次数增加1；或者在一个面中作为边界重复计算两次，为该面的次数增加2。因此在计算面的次数总和时，每条边都恰计算了两次，故等式成立。
由定理7.6.3可以立即得出：
推论：在任何平面图中次数为奇数的面的个数是偶数。
G 的不同平面嵌入的面的次数数列可能是不同的。图7-67中的1G ，2G 是同一个图的平面嵌入，但它们的面的次数数列分别是3,3,5,5和3,3,4,6。
图7-67
7.6.2 欧拉公式
在1750年数学家欧拉发现，任何一个凸多面体的顶点数n ，棱数m 和面数r 之间满足关系式：
2n m r -+=
这就是著名的欧拉公式。 更一般地，对任意平面图，欧拉公式依然成立。这就是下面的定理和推论。
定理7.6.4 设G 为一个连通平面图，它有n 个节点，m 条边和r 个面，则有2n m r -+=。 证明 对G 的边数m 进行归纳证明。
当m =0时，由于G 是连通的，因此G 只能是平凡图。这时，n =1，m =0，r =1，
2n m r -+=成立。
设(1)m k k =≥时，结论成立，下面证明当1m k =+时，结论也成立。 易见，一个具有1k +条边的连通平面图可以由k 条边的连通平面图添加一条边后构成。因为一个含有k 条边的连通平面图上添加一条边后仍为连通图，则有三种情况：
（1）所增边为悬挂边（见图7-68()a ），此时G 的面数不变，节点数增1，边数增1，欧拉公式成立。
（2）所增边为一个环，此时G 的面数增1（见图7-68()b ），边数增1，但节点数不变，欧拉公式成立。
（3）在图的任意两个不相邻节点间增加一条边（见图7-68()c ），此时G 的面数增1，边数增1，但节点数不变，欧拉公式成立。
图7-68
定理7.6.5 设G 是连通的(,)n m 平面图，且每个面的次数至少为(3)l l ≥，则
(2)2
l m n l ≤
--
证明 由定理7.6.3知
1
2d e g ()r
i
i m R l r ==
≥?∑
(r 为G 的面数)
再由Euler 公式
2n m r -+=
得
22m r m n l
=+-≤
故
(2)2
l m n l ≤
--。
推论1 平面图G 的平面嵌入的面数与G 的嵌入方法无关。 于是G 的一个平面嵌入的面数，可直接称为平面图G 的面数。
推论2 设G 是有n 个节点(3n ≥)，m 条边的简单平面图，则36m n ≤-。
证明 不妨设G 是连通的，否则可在G 的连通分支间加边而得到连通图G '，G '的节点数仍为n ，边数m m '≥，所以若定理对G '成立，则对G 也成立。
由于G 是有n 个节点(3n ≥)的简单连通平面图，所以G 的每一个面至少有3条边围成。如果G 中有r 个面，则面的总次数
23m r ≥
即有
23m r ≤
代入欧拉公式，可得
223
m n m -+
≥
从而得到
36m n ≤-。
推论2也可直接由定理7.6.5推出，只需令3l =即可。
推论3 若有n 个节点(3n ≥)的简单连通平面图G 不以3K 为子图，则24m n ≤-。 证明 由于G 是有n 个节点(n ≥3)的简单连通平面图，且G 中不含3K ，所以G 的每个面至少由4条边围成，即4l ≥，代入定理7.6.5，立即得
24m n ≤-。
推论4 若G 是一个简单平面图，则G 至少有一个节点的度数小于等于5。
证明 当G 的节点数小于等于6时，结论显然成立。当G 的节点数大于等于7时，设G 的最小度节点的度数为δ，若5δ>，即6δ≥，由握手定理知
2deg()6v V
m v n ∈=≥∑
故
3m n ≥
与推论2矛盾，所以图G 中至少有一个节点的度数小于等于5。
例7.6.2 证明5K 和3,3K 都不是平面图。
证明 （1）5K 的节点数n =5，边数10m =，若它是平面图，则由推论2得36m n ≤-，即 10356≤?-，这是一个矛盾不等式，故5K 不是平面图。
（2）3,3K 的节点数n =6，边数9m =，且其不含子图3K ，由推论3可知24m n ≤-，即
9264≤?-，这也是一个矛盾不等式，故3,3K 是非平面图。
上面给出的定理7.6.4和推论2、推论3、推论4都是一个图是平面图的必要条件，它们可用来判断某个图不是平面图。我们希望找出一个图是平面图的充分必要条件。经过几十年的努力，波兰数学家库拉托夫斯基（Kuratowski ）于1930年给出了平面图的一个非常简洁的充分必要条件。下面就来介绍库拉托夫斯基定理。为此先引入同胚的概念。
定义7.6.3 设G 为一个无向图，(,)e u v 是G 的一条边，在G 中删去边e ，增加新的节点w ，使,u v 均与w 相邻接，则称在G 中插入一个2度节点； 设w 为G 的一个2度节点，w 与,u v 相邻接，在G 中删去节点w 及与w 相连接的边(,),(,)w u w v ，同时增加新边(,)u v ，则称在
G 中消去一个2度节点w 。如图7-69 所示。
图7-69
定义7.6.4 如果两个无向图1G 与2G 同构或通过反复插入或消去2度节点后是同构的，则称
1G 与2G 是同胚的(Homeomorphic)。
例如，图7-70所示的4个图是同胚的。
图7-70
定理7.6.6 (库拉托夫斯基定理) 一个无向图是平面图当且仅当它不含有与5K 或3,3K 同胚的子图。
库拉托斯基定理的必要性容易看出，因为5K 和3,3K 均不是平面图，因此与5K 或3,3K 同胚的图也不是平面图。一个无向图若是平面图，则它自然不会含有非平面图作为它的子图。
库拉托夫斯基定理的充分性证明较复杂，这里不再引述。有兴趣的读者可参阅邦迪(J.A.Bondy)和默蒂(U.S.R.Murty)的《图论及其应用》。
例7.6.3 证明图7-71中的()a （彼得森图）是非平面图。
图7-71
证明 在彼得森图中有同胚于3,3K 的子图(见图7-71()b 、()c )，由库拉托夫斯基定理知, 彼
得森图不是平面图。
7.6.3 平面图的着色
平面图的着色问题，最早起源于地图的着色。在一张地图中，若相邻国家着以不同的颜色，那么最少需要多少种颜色呢？1852年，英国青年盖思瑞（Guthrie ）提出了用四种颜色可以对地图着色的猜想（以下简称四色猜想）。1879年肯普（Kempe ）给出了这个猜想的第一个证明，但到1890年希伍德（Hewood ）发现肯普证明是有错误的，然而他指出了肯普的方法虽不能证明地图着色用四种颜色就够了，但却可以证明用五种颜色就够了，即五色定理成立。此后四色猜想一直成为图论中的难题。许多人试图证明猜想都没有成功。直到1976年美国数学家阿佩尔（K.Appel ）和哈肯(W.Haken)利用计算机分析了近2000种图形和100万种情况，花费了1200个机时，进行了100多亿个逻辑判断，证明了四色猜想。从此四色猜想便被称为四色定理。但是，不依靠计算机而直接给出四色定理的证明，仍然是数学界的一个令人困惑的问题。
为了叙述图形着色的有关定理，下面先给出对偶图的概念。
定义7.6.5 给定平面图,G V E =??，其面的集合12(){,,,}n F G f f f = 。若有图
*
*
*
,G V E =??满足下列条件：
（1）对于任意一个面()i f F G ∈，其内部有且仅有一个节点**i v V ∈；
（2）对于G 中的面i f 和j f 的公共边k e ，有且仅有一条边**
k e E ∈，使得***
(,)k i j e v v =，且
*
k e 与k e 相交；
（3）当且仅当k e 只是一个面i f 的边界时，*i v 存在一个环*k e 且*
k e 与k e 相交； 则称图*G 是图G 的对偶图(Dual Graph)。
例如，在图7-72中，G 的边和节点分别用实线和“ ”表示，而它的对偶图*
G
的边和结
点分别用虚线和“· ”表示。
图7-72 从对偶图的定义可以看出，若*
*
*,G V E =??是平面图,G V E =??的对偶图，则G 也是*
G 的对偶图。
定理7.6.7一个连通平面图G 的对偶图*
G 也是平面图，而且有
*
m m =， *
n r =， *r n =，
()()*
*
d e g d e g i
G i G
v f =
，
**
(),i i f F G v V ∈∈
其中,,n m r 和***,,n m r 分别是G 和*G 的节点数，边数和面数。
证明 由定义7.6.5对偶图的构造过程可知，G *也是连通的平面图，且*n r =，*m m =和
()()**
deg deg i
G
i
G v f =显然成立，下证*
r
n =。因为G 和*
G 均是连通的平面图，所以由欧拉
公式有
2n m r -+=
***2n m r -+=
由*n r =，*m m =可得*r n =。
定义7.6.6 若图G 的对偶图*G 同构于G ，则称G 是自对偶图(Self-dual Graph)。 例如，图7-73给出了一个自对偶图。
图7-73
定理7.6.8 若平面图,G V E =??是自对偶图，且有n 个节点，m 条边，则()21m n =-。
证明 由欧拉公式知
2n m r -+=
由于图,G V E =??是自对偶图，则有n r =，从而有
22n m -=
即
()21m n =-。
从对偶图的定义容易知道，对于地图的着色问题，可以化为一种等价的对于平面图的节点的着色问题。因此，四色问题可以归结为证明：对任意平面图一定可以用四种颜色，对其节点进行着色，使得相邻节点都有不同颜色。
定义7.6.7 平面图G 的正常着色(Proper Coloring)（简称着色）是指对G 的每个节点指派一种颜色，使得相邻节点都有不同的颜色。若可用n 种颜色对图G 着色，则称G 是n —可着色的。对图G 着色时，需要的最少颜色数称为G 的着色数(Chromatic Number)，记为()G χ。
于是，四色定理可简单地叙述如下：
定理7.6.9（四色定理）任何简单平面图都是4—可着色的。 证明一个简单平面图是5—可着色的很容易。
定理7.6.10（五色定理）任何简单平面图,G V E =??，均有()5G χ≤。 证明 只需考虑连通简单平面图G 的情形。对V 施行归纳证明。
当5V ≤时，显然，()5G χ≤。
假设对所有的平面图,G V E =??，当V k ≤时有()5G χ≤。现在考虑图111,G V E =??，11V k =+的情形。由定理7.6.5的推论4可知，存在01v V ∈，使得()0deg 5v ≤。在图1G 中删
去0v ，得图10G v -。由归纳假设知，10G v -是5—可着色的，即()105G v χ-≤。因此只需证明在1G 中，节点0v 可用5种颜色中的一种着色并与其邻接点的着色都不相同即可。
若()0deg 5v <，则与0v 邻接节点数不超过4，故可用与0v 的邻接点不同的颜色对0v 着色，得到一个最多是五色的图1G 。
若()0deg 5v =，但与0v 邻接的节点的着色数不超过4，这时仍然可用与0v 的邻接点不同的颜色对0v 着色，得到一个最多是五色的图1G 。
若()0deg 5v =，且与0v 邻接的5个节点依顺时针排列为1234,,,v v v v 和5v ，它们分别着不同的颜色红、白、黄、黑和蓝。如图7-74所示。
图7-74
考虑由节点集合(){}1310V v v V G v v =∈-∧着红色或黄色所诱导的10G v -的子图13G 。若13,v v 属于13G 的不同连通分支，如图7-75所示。则将1v 所在的连通分支中的红色与黄色对调，这样并不影响10G v -的正常着色，然后将0v 涂上红色即可得到1G 的一种五着色。
若1v 和3v 属于13G 的同一个连通分支，则由节点集{}130V v 所诱导的1G 的子图
{}13013,V v E '?? 中含有一个圈
C ，而2v 和4v 不能同时在该圈的内部或外部，即2v 与4v 不是邻接点，如图7-76所示。于是，考虑由节点(){}2410V v v V G v v =∈-∧着白色或黑色所诱导子图24G ，由于圈C 的存在，24G 至少有两个连通分支，一个在C 的内部，一个在C 的外部（否则图1G 中将有边相交，与图1G 是平面图的假设矛盾），则2v 和4v 必属于24G 的不同连通分支，作与上面类似的调整，又可得到1G 的一种五着色。故()5G χ≤。由归纳原理，定理得证。
图7-75
习题7.6
1．图7-77()a和()b所示的平面图各有几个面？写出它们各面的边界及次数。
图7-77
2． 证明图7-78()a 和()b 是非平面图。
图7-78
3．证明：小于30条边的简单平面图中存在度数小于等于4的节点。
4．设G 是简单平面图，面数12,()3r G δ<≥，证明G 中存在次数小于或等于4的面。 5．设G 是一个连通平面图， 它有n 个节点，m 条边，且每个面由k 条边围成。 试证
(2)2
k n m k -=
-
6．证明具有６个节点和12条边的简单平面图，它的每一个面都是由３条边围成的。 7．设简单图G 的节点数n ≥11，则G 与G 的补图 G 中至少有一个不是平面图。
7.7 树与生成树
树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络，1857年 凯莱在计算有机化学中222n C H +的同分异构物数目时也用到了树的理论。而树在计算机科学中应用更为广泛。本节介绍树的基本知识，其中谈到的图都假定是简单图。
7.7.1 无向树
定义7.7.1 一个连通无圈无向图称为无向树(Undirected Tree) (简称为树)，记作T 。树T 中度数为1的节点称为树叶(Leaf)（或叶节点），度数大于１的节点称为分枝点(Branch Point )（或内点(Inner Point)）。 一个无圈图称为森林(Forest)。
显然若图G 是森林，则G 的每个连通分支是树。 例如，图7-79()a 和()b 所示的图是树；
()c 所示的图是森林。
图7-79 树和森林示意图
定理7.7.1 设T 是一个无向(,)n m 图，则以下关于T 的命题是等价的。 (1) T 是树；
（2）T 无圈且1m n =-； (3) T 连通且1m n =-；
（4）T 无圈，但增加任一新边，得到且仅得到一个圈。 （5）T 连通，但删去任一边便不连通(2n ≥)。
（6）T 的每一对节点间有唯一的一条通路(2n ≥)。 证明 (1) ?（2）
由树的定义可知T 无圈。下证1m n =-。对n 进行归纳证明。 当1n =时，0m =，显然1m n =-。
假设n k =时结论成立，现证明1n k =+时结论也成立。
由于树是连通而无圈的，所以至少有一个度数为1的节点v ，在T 中删去v 及其关联边，便得到k 个节点的连通无圈图。由归纳假设它有1k -条边。再将顶点v 及其关联边加回得到原图T ，所以T 中含有1k +个顶点和k 条边，故结论1m n =-成立。 所以树是无圈且1m n =-的图。
(2) ?（3）
用反证法。若T 不连通，设T 有k 个连通分支(2k ≥) 1T ，2T ， ，k T ，其节点数分别是12,,,k n n n ，边数分别为12,,,k m m m ，于是
11
,k
k
i
i i i n
n m m ====∑∑
1
1
(1)1k
k
i
i
i i m m
n
n k n ===
=
-=-<-∑∑
得出矛盾。所以T 是连通且1m n =-的图。
(3) ?（4）
首先证明T 无圈。对n 作归纳证明。 当1n =时，10m n =-=，显然无圈。
假设节点数为1n -时无圈，今考察节点数是n 时的情况。此时至少有一个节点v 其度数deg()1v =。我们删去v 及其关联边得到新图T '，根据归纳假设T '无圈，再加回v 及其关联边又得到图T ，则T 也无圈。
其次，若在连通图T 中增加一条新边(,)i j v v ，则由于T 中由i v 到j v 存在一条通路，故必有一个圈通过i v ，j v 。若这样的圈有两个，则去掉边(,)i j v v ，T 中仍存在通过i v ，j v 的圈，与T 无圈矛盾。故加上边(,)i j v v 得到一个且仅一个圈。
(4) ?（5）
若T 不连通，则存在两个节点i v 和j v ，在i v 和j v 之间没有路，若加边(,)i j v v 不会产生圈，但这与假设矛盾，故T 是连通的。又由于T 无圈，所以删去任一边，图便不连通。
(5) ?（6）
由连通性知，任意两点间有一条路径，于是有一条通路。若此通路不唯一，则T 中含有圈，删去此回路上任一边，图仍连通，这与假设不符，所以通路是唯一的。
(6) ?（1）
显然T 连通。下证T 无圈。用反证法。若T 有圈，则圈上任意两点间有两条通路，此与通路的唯一性矛盾。故T 是连通无圈图，即T 是树。
定理7.7.2 任一棵树T 中，至少有两片树叶(节点数2n ≥时)。 证明 设T 是一棵(,)n m 树（2n ≥），由定理7.7.1， 有
1
d e g (
)22(
1)22
n
i
i v m n n ===-=-∑ （1） 若T 中无树叶，则T 中每个节点的度数2≥，则
1
d e g (
)2
n
i
i v n =≥∑ （2） 若T 中只有一片树叶，则T 中只有一个节点度数为1，其他节点度数2≥，所以
1
d e g (
)2(
1)22n
i
i v n n =>-=-∑ （3）
(2)，(3)都与(1)矛盾。所以T 中至少有两片树叶。
由定理7.7.1 所刻画的树的特征可见：在节点数给定的所有图中，树是边数最少的连通图， 也是边数最多的无圈图。 由此可知，在一个(,)n m 图G 中， 若1m n <-， 则G 是不连通的； 若1m n >-，则G 必定有圈。
例7.7.1 设T 是一棵树，它有两个2度节点，一个3度节点，三个4度节点，求T 的树叶数。
解 设树T 有x 片树叶，则T 的节点数
213n x =+++ T 的边数
15m n x =-=+ 又由
1
2deg()n
i
i m v ==
∑
得 2(5)223143x x +=?+?+?+ 所以9x =，即树T 有9片树叶。
7.7.2 无向图中的生成树与最小生成树
1．无向图中的生成树
定义7.7.2 若无向(连通图) G 的生成子图是一棵树，则称该树是G 的生成树或支撑树(Spanning Tree)，记为G T 。生成树G T 中的边称为树枝。图G 中其他边称为G T 的弦。所有这些弦的集合称为G T 的补。
例如，图7-80中()b 、()c 所示的树1T 、2T 是图()a 的生成树，而()d 所示的树3T 不是图()a 的生成树。()f 、()g 所示的树是图()e 的生成树。一般的，一个图的生成树不唯一。
图7-80
考虑生成树1T ，可知1234,,,e e e e 是1T 的树枝，567,,e e e 是1T 的弦，集合567{,,}e e e 是1T 的补。生成树有其一定的实际意义。
例7.7.2 某地要兴建５个工厂，拟修筑道路连接这５处。经勘测其道路可依如图7-80()a 的无向边铺设。为使这５处都有道路相通，问至少要铺几条路？ 解：这实际上是求G 的生成树的边数问题。
一般情况下，设连通图G 有n 个节点，m 条边。由树的性质知，T 有n 个节点，n －1条树枝，1m n -+条弦。
在图7-80()a 中，5n =，则1514n -=-=，所以至少要修４条路才行。 由图7-80可见，要在一个连通图G 中找到一棵生成树，只要不断地从G 的回路上删去一条边，最后所得无回路的子图就是G 的一棵生成树。于是有以下定理。
定理7.7.3 无向图G 有生成树的充分必要条件是G 为连通图。 证明 先采用反证法来证明必要性。
若G 不连通，则它的任何生成子图也不连通，因此不可能有生成树，与G 有生成树矛盾，故G 是连通图。
再证充分性。
设G 连通，则G 必有连通的生成子图，令T 是G 的含有边数最少的生成子图，于是T 中必无回路（否则删去回路上的一条边不影响连通性，与T 含边数最少矛盾），故T 是一棵树，即生成树。
2．无向图中的最小生成树
定义7.7.3 设,G V E =是一连通的带权图，则G 的生成树G T 为带权生成树，G T 的树枝所带权之和称为生成树G T 的权(Weight)，记为()G C T 。G 中具有最小权的生成树G T 称为G 的最小生成树(Minimal Spanning Tree)。
最小生成树有很广泛地应用。例如要建造一个连接若干城市的通讯网络，已知城市i v 和j
v
之间通讯线路的造价，设计一个总造价为最小的通讯网络，就是求最小生成树G T 。
下面介绍求最小生成树G T 的克鲁斯克尔（Kr u sk a l)算法。
此方法又称为“避圈法”。其要点是，在与已选取的边不成圈的边中选取最小者。具体步骤如下：
1) 在G 中选取最小权边，置边数i ＝1。 2) 当i ＝n －1时，结束。否则，转3)。
3) 设已选择边为12,,,i e e e ，在G 中选取不同于12,,,i e e e 的边1i e +，使
12{,,,i e e e 1,}i e +无圈且1i e +是满足此条件的最小权边。
4) 置i 为i ＋1， 转2)。
证明 设0T 为由上述算法构造的一个G 的子图，它的节点是G 的n 个节点，0T 的边是
121,,,n e e e - ，且0T 无圈。由定理7.7.1可知0T 是一棵树，且为图G 的生成树。
下面证明0T 是最小生成树。
设图G 的最小生成树是T 。若T 与0T 相同，则0T 是图G 的最小生成树。若T 与0T 不同，则在0T 中至少存在一条边1i e +，使得1i e +不是T 的边，但12,,,i e e e 是T 的边。因为T 是树，我们在T 中加上边1i e +，必有一个圈C ，而0T 是树，所以C 中必存在某条边e 不在0T 中。对于树T ，若以边1i e +置换e ，则得到一棵新树T '，树T '的权1()()()()i C T C T C e C e +'=+-，因
为T 是最小生成树，故()()C T C T
'≤，即1()()0i C e C e +-≥或1()()i C e C e +≥。因为
12,,,i e e e 1,i e +是T '的边，且在12{,,,i e e e 1,}i e +中无圈，故1()()i C e C e +>不可能成立，否
则在0T 中，自12,,,i e e e 之后将取e 而不能取1i e +，与题设矛盾。于是1()()i C e C e +=，因此T '也是G 的最小生成树，但是T '与0T 的公共边比T 与0T 的公共边数多1，用T '置换T ，重复上述过程直到得到与0T 有1n -条公共边的最小生成树，这时T '就是0T ，故0T 是最小生成树。
例7.7.3 求图7-81(0)中有权图的最小生成树。
解 因为图(a)中n ＝8，所以按算法要执行n －1＝7次，其过程见图7-81(b)~(h)所示。
图7-81
离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。
3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x)
第1章命题逻辑 逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。所谓的数学方法也就是 用一套有严格定义的符号，即建立一套形式语言来研究。因此数理逻辑也称为符号逻辑。 数理逻辑的基础部分是命题逻辑和谓词逻辑。本章主要讲述命题逻辑，谓词逻辑将在第 2章进行讨论。 1.1命题及其表示 1.1.1命题的基本概念 数理逻辑研究的中心问题是推理( Inference),而推理就必然包含前提和结论，前提和 结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。在数理逻辑中，将能够判断真假的陈述句称为命题。因此命题就成为推理的基本单位。在命题逻辑中，对命 题的组成部分不再进一步细分。 定义1.1.1能够判断真假的陈述句称为命题(Proposition )。命题的判断结果称为命题的 真值，常用T(True)(或1)表示真，F(False)(或0)表示假。真值为真的命题称为真命题，真值为假的命题称为假命题。 从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。 例1.1.1判断下列句子是否为命题 (1)北京是中国的首都。 (2)请勿吸烟！ (3)雪是黑的。 (4)明天开会吗？ (5)x+y=5。 (6)我正在说谎。 (7)9+5 < 12。 (8)1+101=110。 (9)今天天气多好啊！ (10)别的星球上有生物。 解在上述的十个句子中，(2)、( 9)为祈使句，(4)为疑问句，(5 )、( 6)虽然是陈述句，但(5)没有确定的真值，其真假随x、y取值的不同而有改变，(6)是悖论(Paradox) (即由真能推出假，由假也能推出真) ，因而(2)、(4)、(5)、(6)、(9)均不是命题。(1 )、(3)、(7)、(8)、(10)都是命题，其中(10)虽然现在无法判断真假，但随着科技的进步是可以判定真假的。 需要进一步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例1.1.1的 (8) 1+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，否则为假命题。还有的命题的真假不能马上给出，如例 1.1.1的(10)，但它确实有真假意 义。 1.1.2命题分类 根据命题的结构形式，命题分为原子命题和复合命题。
2006-2007学年第2学期 2005级《离散数学2》期末考试试题(A卷) 考试时间：2007年6月班级_______________________ 学号_____________________ 姓名_____________________ 请将答案写在答题纸上，写明题号，不必抄题，字迹工整、清晰； 请在答题纸和试题纸上都写上你的班级，学号和姓名，交卷时请将试题纸、答题纸和草纸一并交上来。 一.综合体(30分，每题3分) 1. 求( 1 3 5 ) (2 5 4 ) (3 4 ) 2. 只有两个生成元的循环群一定是有限循环群吗？并说明理由。 3. 有限循环群中是否一定存在周期与群的元数相等的元素？ 4. 下面哪个是域GF( 16)的真子域 (A)GF (6) ;(B)GF ⑷;(C)GF(8);(D)GF(16) 5. 有限布尔代数的元素个数必定是如下哪个形式？ (A)2n;(B)n 2 ;(C)2 n;(D)4n. 6. 下列代数系统(S, *)中，哪个是群？ (A) S={0,1,3,5},* 是模7的乘法；(B) S是有理数集合，*运算是普通乘法； (C) S是整数集合，*是普通乘法；(D) S={1,3,4,9},* 是模11的乘法。 7. 设A={0,1,2,3,4},运算为模5加法，请给出A的所有子群。 8. n元恒等置换是奇置换还是偶置换？对换呢？ 9?请给出一个有余，但不是分配格的例子。 10.设R是模12的整数环，R={0,1,2,…,11},下面哪一个是极大理想： (A) 6R; (B)2R; (C)4R; (D)8R 二.计算题(25分，每题5分) 1. 计算分圆多项式①24(X). 2. 设(Z,+)为整数加法群，(C*,??)为非零复数的乘法群，令 f: n -i n ,是Z到C*中的同态映射，请求出f的同态核。 3. 在R上求出x+2除2X5+4X3+3X2+1所得的商式和余式。 4. 设G是3次对称群，H是由I和(13)作成的子群，求H得所有右陪集。 5. 设A={0,1,2,3,4,5}, 运算为模6加法，请给出A中所有元素的周期。 三.(10分)证明或者反驳：f(x)=3x 5+5X2+1 四.(10分)设(G, *)是群，(A, *)和(B，*)是它的两个子群，C={a*b|a € A, b€ B}.证明：若*满足交换律，则(C, *)也是(G，*)的子群。 五.(10分)设Z是整数集合，X={(a,b)|a,b € Z},定义X上的二元运算①和。 如下：对任意(ab) ,(a 2,b2)€ X,有： (a1b"e (a2,b2)= (a+a?,b1+b2), (a1bJ O (a2,b2)= (ax a2,b 1X b)，其中，+，x分别是整数加法与乘法。 证明：(X，?，O)是环，如果此环有零因子请给出它们
《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0
本科高等数学离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44
第1章集合 1.1 集合的基本概念 1. 集合、元（元素）、有限集、无限集、空集 2. 表示集合的方法：列举法、描述法 3. 定义1.1.1（子集）：给定集合A和B，如果集合A的任何一个元都是集合B中的元，则称集合A包含于B或B包含A，记为或，并称A为B的一个子集。 如果集合A和B满足，但B中有元不属于A，则称集合A真包含于B，记为，并且称A为B的一个真子集。 4. 定义1.1.2（幂集）：给定集合A，以A的所有子集为元构成的一个集合，这个集合称为A 的幂集，记为或 1.2 集合的运算 定义1.2.1（并集）：设A和B是两个集合，则包含A和B的所有元，但不包含其他元的集合，称为A和B的并集，记为. 定义1.2.2（交集）：A和B是两个集合，包含A和B的所有公共元，但不包含其他元的集合，称为A和B的交集，记为. 定义1.2.3（不相交）：A和B是两个集合，如果它们满足，则称集合A和B是不相交的。 定义1.2.4（差集）：A和B是两个集合，属于A而不属于B的所有元构成集合，称为A和B 的差集，记为. 定义1.2.5（补集）：若A是空间E的集合，则E中所有不属于A的元构成的集合称为A的补集，记为. 定义1.2.6（对称差）：A和B是两个集合，则定义A和B的对称差为 1.3 包含排斥原理 定理1.3.1设为有限集，其元素个数分别为，则 定理 1.3.2设为有限集，其元素个数分别为，则 定理1.3.3设为有限集，则 重要例题P11 例1.3.1 第2章二元关系 2.1 关系 定义2.1.1（序偶）： 若和是两个元，将它们按前后顺序排列，记为，则成为一个序偶。 ※对于序偶和，当且仅当并且时，才称和相等，记为
一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝__{3}__________________; ρ(A) - ρ(B)＝___________________{3},{1,3},{2,3},{123}______ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = _____2^(n^2)_____________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是__自反，对称，传递 ____________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2= {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸，将答题过程手工书写，并拍照上传． 一、填空题 1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15 ． 2．设给定图G(如右由图所示)，则图G的点割集是 { f }，{ e,c} ． 3．设G是一个图，结点集合为V，边集合为E，则 G的结点度数之和等于边数的两倍． 4．无向图G存在欧拉回路，当且仅当G连通且不含奇数度结 点． 5．设G=
8．结点数v与边数e满足e=v - 1 关系的无向连通图就是树． 9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i = 4 ． 二、判断说明题（判断下列各题，并说明理由．） 1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路． 答：错误。应叙述为：“如果图G是无向连通图，且其结点度数均为偶数，则图G存在一条欧拉回路。” 2．如下图所示的图G存在一条欧拉回路． 答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。 3．如下图所示的图G不是欧拉图而是汉密尔顿图．
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
离散数学（第五版）清华大学出版社第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们 都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来 的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许 多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结 的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→ｑ。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→ｑ为假命题。 （7）p→ｑ，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→ｑ为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。
1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={