*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 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 邻接且未标记过的2V 的节点1y ；类似地，用（2x ）标记2y 。
(2) 选2V 的新标记过的节点1y ， 用（1y ）标记通过M 中的边与1y 邻接且未标记过的1V 的节点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 E =的一个1V ―完全匹配，则1V 中的每个顶点均是M 饱和的。对1V 的任一子集A ，因A 的每个顶点在M 下和()N A 中不同的顶点配对，所以有()N A A ≥。
再证充分性。假设G 是满足对任何1V 的子集A ，()N A A ≥的二部图，但G 中没有使1V 中每个顶点饱和的完全匹配，设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 中，所有面的次数之和等于边数的二倍，即
1deg()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)2l m n l ≤
-- 证明 由定理7.6.3知
1
2deg()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 ≥
即有
23
m r ≤
代入欧拉公式，可得 223m 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 =，
()()**deg deg 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 ，于是
1
1,k k i i i i n
n m m ====∑∑ 11(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
deg()22(1)22n i
i v m n n ===-=-∑ （1） 若T 中无树叶，则T 中每个节点的度数2≥，则
1
d e g ()2n i
i v n =≥∑ （2） 若T 中只有一片树叶，则T 中只有一个节点度数为1，其他节点度数2≥，所以 1deg()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 =-=+
又由
12deg()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
匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes K?nig和Jen? Egerváry的工作之上创建起来的。 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 二分图： 二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。图一就是一个二分图。 匈牙利算法： 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是一种用增广路径求二分图最大匹配的算法。 Hall定理： 二部图G中的两部分顶点组成的集合分别为X, Y; X={X1, X2, X3,X4, .........,Xm}, Y={y1, y2, y3, y4 , .........,yn}, G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m) 匹配： 给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。图一中红线为就是一组匹配。 未盖点： 设Vi是图G的一个顶点，如果Vi 不与任意一条属于匹配M的边相关联，就称Vi 是一个未盖点。如图一中的a 3、b1。
二分图的最优匹配（KM算法） KM算法用来解决最大权匹配问题：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。 基本原理 该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。 KM算法的正确性基于以下定理： 若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是 Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 4）X端在交错树中，Y端不在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中x1->y4这条边） 现在的问题就是求d值了。为了使A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于： Min{A[i]+B[j]-w[i,j] | Xi在交错树中，Yi不在交错树中}。 改进 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y 顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（因为：d的定义为 min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T }
习题十 1. 设G 是一个(n ，m)简单图。证明：，等号成立当且仅当G 是完全图。 证明：（1）先证结论： 因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。■ 2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。 证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。与题设m = n+1，矛盾。因此，G 中存在顶点u ，d （u ）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
二分图最大匹配算法 令G = （X,*,Y）是一个二分图，其中，X = {x1,x2,...xm}, Y = {y1,y2,...yn}。令M为G中的任一个匹配。 1）讲X的所有不与M的边关联的顶点标上（@），并称所有的顶点为未被扫描的。转到2）。2）如果在上一步没有新的标记加到X的顶点上，则停止。否则转到3）。 3）当存在X被标记但未被扫描的顶点时，选择一个被标记但未被扫描的X的顶点，比如，xi,用(xi)标记Y的所有顶点，这些顶点被不属于M且尚未标记的边连到xi .现在，顶点xi 是被扫描的。如果不存在被标记但未被扫描的顶点，则转到4）。 4）如果在步骤3）没有新的标记被标到Y的顶点上，则停止。否则，转到5）。 5）当存在Y被标记但未被扫描的顶点时，选择Y的一个被标记但未被扫描的顶点，比如yi，用(yi)标记X的顶点，这些顶点被属于M且尚未标记的边连到yi.现在，顶点yi是被扫描的。如果不存在被标记但未被扫描的顶点，则转到2）。 也可以叙述为： [ZZ]匈牙利算法 关键在于匈牙利算法的递归过程中有很多重复计算的节点，而且这种重复无法避免，他不能向动态规划一样找到一个“序”将递归改为递推。 算法中的几个术语说明： 1。二部图： 如果图G=(V,E)的顶点集何V可分为两个集合X,Y，且满足X∪Y = V, X∩Y=Φ，则G称为二 部图； 图G的边集用E(G)表示，点集用V(G)表示。 2。匹配： 设M是E(G)的一个子集，如果M中任意两条边在G中均不邻接，则称M是G的一个匹配。M中的 —条边的两个端点叫做在M是配对的。 3。饱和与非饱和： 若匹配M的某条边与顶点v关联，则称M饱和顶点v，并且称v是M-饱和的，否则称v 是M-不 饱和的。 4。交互道： 若M是二分图G＝(V,E)的一个匹配。设从图G中的一个顶点到另一个顶点存在一条道路，这条道路是由属于M的边和不属于M的边交替出现组成的，则称这条道路为交互道。 5。可增广道路： 若一交互道的两端点为关于M非饱和顶点时，则称这条交互道是可增广道路。显然，一条边的两端点非饱和，则这条边也是可增广道路。 6。最大匹配： 如果M是一匹配，而不存在其它匹配M'，使得|M'|>|M|，则称M是最大匹配。其中|M|表
云南大学数学与统计学院 实 验 报 告 一、实验目的 掌握二部图边染色数问题和二部图最大匹配问题的求解算法，给出二部图的边染色方案 二、实验环境 VS2010（C++） 三、实验内容 给定一个二部图()E V G ,=，求边染色数()G 'χ，并给出染色方案。 四、 实验过程 A.二部图边染色问题求解思想 1） 对于给定的二部图G ，利用二部图最大匹配算法求得G 的一个最大匹配M 1，对G 1=G-M 1再利用二部图匹配算法求得G 1的一个最大匹配M 2,..., 这样可以得到图G 的边子集被划分成()G ?个集合?M M M ,...,,21，从而可对G 进行()G ?染色。根据定理6.1，设()E T S G ;,=是一个二部图，则()()G G ?='χ，其中()G ?为G 的最大的度。 2) 二部图最大匹配算法 设图G=(S,T;E)为二部图，可用反圈法求二部图的匹配 ① 选初值：取(){}的未盖点 是关于M |0u S u X ∈= ② 在()()k X Φ中选边j i u u 原则，这里()()() k j k i X V u X u -∈∈,： 若()S X u k i ?∈，则只能选以i u 为端点的非M 边 若()T X u k i ?∈，则只能选以i u 为端点的M 边 ③ 若在某步出现下列情形之一停止 情形1：()k X 中有T 型未盖点，即已找到增广路P ，进行增广匹配，构造新的匹配 ()()()()M P E P E M P E M M -?-=⊕=)(' 情形2：上述情形1不存在，而()()k X Φ中无边可选，说明G 不存在关于M 的增广路，进而M 为最大匹配。 B.实现过程 对任意给定的一个图，首先判断它是否为二部图，若是二部图，则给出二部图的边染色方案，若不是二部图，程序结束。二部图的S 集和T 集的划分，这里采用如下定义： (){}(){}是奇数，是偶数v u d V u T v u d V u S ,|,|∈=∈=，计算两点之间的最短距离用到的是
*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 个顶点的完全图只有一个，记为n K 。 偶图（二部图）：具有二分类(,)X Y 的图，他的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。 完全偶图 ：指具有二分类(,)X Y 的简单偶图，其中X 的每个顶点与Y 的每个顶点相连。若,X m Y n ==，则这样额完全偶图记为：,m n K 。 k —正则图：设(,)G V E =为简单图，如果对所有的结点v V ∈，有()d v k =，称G 为k —正则图。 完全图和完全偶图,n n K 均是正则图。 图划分：若一个n 阶简单图G 各点的度为i d ，则分正整数k 为n 个部分的划分i d ∑称为是图划分。 子图：边集合和点集合均是原图的子集，且待判定图中的边的重数不超过原图中对应的边的重数。 生成子图：点集合相等，边集合为原图子集的图。 导出子图：由顶点集为原图G 真子集的所有点，及两端点均在该集合中的边的全体组成的 子图V ‘。 '[]G V 和G v -。 边导出子图：由原图G 边的真子集，该图中边的断点全体为顶点组成的子图E ‘。 '[]G E 和{}G e -。 图的运算： 并，交，差，对称差，联图，积图，合成图，极图 路与图的联通性： 途径： 迹：边互不相同的途径。 路：边和点都互不相同的途径。 连通的：两个顶点之间存在路。 连通图：每一对顶点之间都有一条路。
二分图的概念 二分图又称作二部图，是图论中的一种特殊模型。 设G=(V, E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分图。 二分图的性质 定理：当且仅当无向图G的每一个回路的次数均是偶数时，G才是一个二分图。如果无回路，相当于任一回路的次数为0，故也视为二分图。 二分图的判定 如果一个图是连通的，可以用如下的方法判定是否是二分图： 在图中任选一顶点v，定义其距离标号为0，然后把它的邻接点的距离标号均设为1，接着把所有标号为1的邻接点均标号为2（如果该点未标号的话），如图所示，以此类推。 标号过程可以用一次BFS实现。标号后，所有标号为奇数的点归为X部，标号为偶数的点归为Y部。 接下来，二分图的判定就是依次检查每条边，看两个端点是否是一个在X部，一个在Y部。如果一个图不连通，则在每个连通块中作判定。 二分图匹配 给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 图中加粗的边是数量为2的匹配。
最大匹配 选择边数最大的子图称为图的最大匹配问题(maximal matching problem) 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。 图中所示为一个最大匹配，但不是完全匹配。 增广路径 增广路径的定义：设M为二分图G已匹配边的集合，若P是图G中一条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。 增广路径是一条“交错轨”。也就是说, 它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且起点和终点还没有被选择过，这样交错进行,显然P有奇数条边（为什么？）
二部图 定义：图),(E V G =称为二部图(bipartite graph)，如果V 是两个互不相交的集合21,V V 的开集，且1V 和2V 中的顶点互不相邻. 这样的二部图也常称为),(21V V -二部图. 定义：图G 的匹配是由G 中没有公共顶点构成的集合，与匹配M 中的边关联的顶点称为是被M -浸润的(saturated by M)，其余的顶点称为未被M -浸润的(M-unsaturated). 图G 的一个完美匹配(perfect matching)是浸润的所有顶点的匹配. 图G 的边数最多的匹配称为一个最大匹配(maximum matching). 例如在上图中，粗边给出了一个匹配1M ，显然两条细边给出了一个最大匹配2M . 定义：设M 是图G 的一个匹配. 如果路径P 的边交替出现在M 和不出现在M 中，则称P 是一条M -交错路径(M-alternating path). 两个顶点都未被M -浸润的交错路径称为M -增广路径(M-augmenting path). 在上例中存在1M -增广路径，2M 是最大匹配，而不存在2M -增广路径，这不是偶然的. 因为可以让（留作习题）：图G 的一个匹配M 是最大匹配⇔G 中无M -增广路径. 定义：图G 的一个顶点覆盖(covering)是一些顶点构成的集合)(G V ⊆κ，使得G 的任何一边都有一个顶点含于κ. 一个顶点覆盖κ称为最小顶点覆盖，是指不存在覆盖'κ，使得κκ<'. 设κ是G 的一个顶点覆盖，M 是G 的一个匹配，显然M ≥κ. 我们关心对于最大匹配的最小顶点覆盖来说，等式是否成立. 在图1(a)中，等式成立，而图1(b)中最小顶点覆盖大小为3，而最大匹配大小为2. 注意图1(a)为二部图，图1(b)为有5条边的圈，从而不是二部图（可以一个图G 是二部图⇔G 中不含奇数边的图，证明留作习题）.对于二部图，我们有下面一般的结论： 定理：设G 是),(Y X -二部图，则G 的最大匹配的大小等于G 的最小顶点覆盖的大小(könig 1931).
第1章 图论预备知识 1.1 解：(1) p={φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} (2) p={,{a},{{b,c}},{a,{b,c}}} (3) p={,{}} (4) p={,{},{{}},{,{}}} (5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}} 1.2 解：(1) 真 (2) 假 (3)假 (4)假 1.3 解：(1) 不成立，A={1} B={1,2} C={2} (2) 不成立，A={1} B={1,2} C={1,3} 1.4 证明：设(x,y)∈(A ∩B)X(C ∩D) 说明x ∈A ∩B,y ∈C ∩D 由于 x ∈A,y ∈C 所以 (x,y) ∈A X C 由于x ∈B,y ∈D 所以 (x,y) ∈B X D 所以 (x,y) ∈（A X C ）∩（B X D ） 反过来，如果（x,y ）∈(A X C) ∩（B X D ） 由于 (x,y) ∈（A X C ）所以 x ∈A,y ∈C 由于 (x,y) ∈（B X D ）所以x ∈B,y ∈D 所以x ∈(A ∩B) y ∈(C ∩D) 所以 (x,y) ∈(A ∩B)X(C ∩D) 所以(A ∩B)X(C ∩D)= (A X C) ∩（B X D ） 1.5 解：Hasse 图 φφφφφφφφφ
极大元{9,24,10,7} 极小元{3,2,5,7} 最大元{24} 最小元{2} 1.6 解 (2)关系图为： (3)不存在最大元，最小元为{2} 1.7 解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>} (2)略 (3)I A ⊆R 故R 是自反的。 <1,2>∈R <2,3>R 但是<1,3> ∉R 故不满足传递性 1.8 解：(1) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>，<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (2) 不成立 A={1,3} B={1} C={2,4} D={2} 则左式={<3,4>} 右式={<1,4>,<3,2>,<3,4>} (3) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>,<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (4) 成立 证明：设
基于加权二部图匹配的中文段落相似度计算 张绍阳;曹家波;王子凡;曲卫东 【摘要】In order to improve the low accuracy of the statistical method that is represented by the traditional Vector Space Model(VSM)and based on word frequency in Chinese paragraph similarity computing, this thesis proposes a method to compute Chinese paragraph similarity on the basis of weighted bipartite graph matching. The similarity comput-ing method will be divided into two levels:paragraphs and sentences. Thus, sentences can be treated as paragraphs and calculated the similarity by using bipartite graph matching. First of all, it utilizes key words extraction algorithm to extract the main vocabulary backbone of the sentences, using the main vocabulary as vertex of weighted bipartite graph to calcu-late similarity of sentences. Secondly, it calculates the paragraph similarity by using the sentence as a vertex of weighted bipartite graph, and the similarity between sentences as the weight coefficient between the vertex of weighted bipartite graph. Experimental results show that the proposed method has been greatly increased in accuracy compared with VSM, in virtue of its ability to identify synonyms accurately and match two similar words in different locations of paragraphs automatically.%为了改进传统以向量空间模型(VSM)为代表的基于词频统计的方法在中文段落相似度计算时存在的精度不高问题,在基于加权二部图匹配的思想上提出了一种计算中文段落之间相似度的方法.该方法将相似度计算分为段落和句子两个层次,将句子作为简单段落看待,也使用二部图匹配进行相似度计算.首先利用句子主干词汇提取算法来提取句子的主
关于二部图与匹配问题的探究 一、二部图的基本观点 二部图是一种特殊的图结构，其中的顶点可以被分为两个互 不相交的集合（通常表示为U和V），集合U中的顶点与集合V 中的顶点之间没有边相连。二部图可以用数学方式表示为G=(U, V, E)，其中U和V表示两个顶点集合，E表示边的集合。 二部图的一个关键性质是，一个边的两个顶点务必分别属于 两个不同的集合。这个观点在实际中有浩繁应用，比如在婚姻匹 配问题中，假设有一组男性和一组女性，我们可以用二部图来表 示可能的婚姻干系。 二、匹配问题的定义与应用 在二部图G=(U, V, E)中，我们称一个边的集合M为一个匹配，若果M中的边两两之间没有公共顶点。换句话说，任意两条 边都不毗连同一个顶点。匹配问题的目标是找到一个具有最大边 数的匹配M，或者找到一个最小边数的匹配。 匹配问题在实际中有浩繁应用。例如，在网络中，我们可以 将二部图中的两个顶点集合U和V分别表示为发送方和接收方， 边表示毗连发送方和接收方的通信链路。这时，匹配问题等价于 如何合理分配通信链路，使得网络的容量得到最大利用。 另一个应用是在任务分配问题中。假设有一组任务和一组工 作者，每个任务需要特定的技能，每个工作者也具有特定的技能。
二部图可以用来表示任务与工作者之间的技能匹配状况。匹配问 题就变成了如何将任务分配给工作者，使得每个任务都能被合适 的工作者完成。 三、匹配问题的经典算法与改进 匹配问题的探究已经有了很长的历史，可以追溯到20世纪 40时期。最初，匈牙利算法是解决匹配问题最常用的算法之一。 该算法基于增广路径的观点，通过不息寻找增广路径并更新匹配，最终得到最大匹配。 然而，匈牙利算法存在一些局限性。起首，它只能解决二部 图中的最大匹配问题，不适用于其他相关问题。其次，匈牙利算 法的时间复杂度较高，不适用于大规模问题。因此，探究者们提 出了一系列改进算法，如Kuhn-Munkres算法和Hopcroft-Karp算 法等。 Kuhn-Munkres算法是一种针对二部图的最大权匹配问题的改 进算法。它基于线性规划的思想，通过构造相应的对偶图，并通 过对偶图上的最小权完美匹配求解原问题。 Hopcroft-Karp算法是解决平凡匹配问题的改进算法。它利用 了二部图的性质，将匹配问题转化为路径问题，并通过增广路径 的查找来优化匹配。 此外，还有一些启发式算法被提出，如遗传算法和模拟退火 算法等。这些算法通过引入随机和局部查找的策略，在一定程度 上提高了解决匹配问题的效率和质量。 总结：
完全二部图K9，n的点可区别E-全染色 完全二部图K9，n的点可区别E-全染色 染色问题是图论中一个经典且重要的问题，研究染色问题有助于我们进一步了解图的特性和性质。其中，二部图是一类特殊的图，它的顶点可以分为两个不相交的集合，并且边只能连接两个集合之间的顶点。而完全二部图是一种特殊的二部图，其中任意两个顶点都有边相连。 本文将探讨完全二部图K9，n的点可区别E-全染色的问题。在完全二部图K9中，我们有9个顶点，分为两个不相交 的集合，即A集合和B集合。为了便于讨论，我们假设A集合中有a个顶点，B集合中有b个顶点，那么n = a + b。 首先，我们来考虑当完全二部图K9中的顶点数为9时， 是否存在一种染色方式，使得所有的顶点都能够区别开来。要使得任意两个相邻顶点的颜色不能相同，即相邻顶点之间的边的两个端点不能染成同样的颜色。那么我们需要至少有9种不同的颜色，分别对应于图中的9个顶点。因为完全二部图K9 中每个顶点都与另一个集合中的所有顶点相连，所以我们需要至少有9种不同的颜色来染色。 接下来，我们考虑当完全二部图K9中的顶点数为n时， 是否存在一种染色方式，使得所有的顶点都能够区别开来。类似地，我们需要考虑集合A中的a个顶点和集合B中的b个顶点。根据之前的假设，n = a + b。 当a = 1时，即集合A中只有一个顶点，那么集合B中必须有n - 1个顶点。此时，完全二部图K9就变成了一个完全 图Kn。对于完全图Kn，我们知道它的染色数为n。所以，对 于完全二部图K9中的染色问题，当a = 1时，它的染色数也
为n。即完全二部图K9，n的点可区别E-全染色。 当a > 1时，我们需要进一步讨论。以K9为例，我们考 虑如何分别染色A集合和B集合。根据之前的假设，A集合中 有a个顶点，所以我们至少需要有a种不同的颜色来染色A集合中的顶点。同样地，B集合中有b个顶点，我们至少需要有 b种不同的颜色来染色B集合中的顶点。 对于A集合中的顶点，每个顶点都与B集合中的b个顶点相连，而B集合中的顶点又与A集合中的a个顶点相连。所以，对于A集合中的每个顶点来说，它与B集合中的每个顶点都不相连，因此它们所染的颜色都应该不同。同理，对于B集合中的每个顶点来说，它们所染的颜色也应该不同。 因此，我们可以得出结论：完全二部图K9，n的点可区别 E-全染色。无论是对于完全二部图K9还是对于完全二部图K9，n的点可区别E-全染色都成立。 总之，完全二部图K9，n的点可区别E-全染色是一种特 殊的染色方式，在此种方式下，能够使得无论是完全二部图 K9还是完全二部图K9，n的点都能够被区别开来。这一结论 有助于我们对完全二部图和染色问题有更深入的了解，也有助于我们进一步探讨其他相关的图论问题 综上所述，完全二部图K9，n的点可区别E-全染色是一 种特殊的染色方式，能够使得无论是完全二部图K9还是完全 二部图K9，n的点都能够被区别开来。这种染色方式在图论中具有重要意义，对于理解完全二部图和染色问题有着深入的帮助。同时，这也为进一步探讨其他相关的图论问题提供了基础
完全二部图优美性质探索 把丽娜;刘倩;刘信生;姚兵 【摘要】The bipartite graphs of graph theory and graph labellings are widely used in practical applications,especially recently the graph labelling has been applied to design a new type of graphical password.Firstly, some complete bipartite graphs are constructed by combinatoric and series methods.A new labelling,called edge-odd-magical total labelling,is found and it is proved that the combinatoric complete bipartite graphs admit the edge-odd-magical total labelling.Moreover,series complete bipartite graphs are graceful,or (k ,d)-graceful.%图论的二部图及其标号在实际应用中较多,尤其最近图标号被应用于新型的图形密码设计.首先构造出了组合完全二部图与串联完全二部图,发现了一种叫做奇边魔幻全标号的标号,并给出了组合完全二部图具有奇边魔幻全标号的证明.此外,得出了串联完全二部图是优美图、(k,d)-优美图的结论. 【期刊名称】《大连理工大学学报》 【年(卷),期】2017(057)006 【总页数】6页(P657-662) 【关键词】树;完全二部图;优美标号;(k,d)-优美标号 【作者】把丽娜;刘倩;刘信生;姚兵
图论第二章和第四章书后练习题
2.2 给出满足下列条件的图或说明这样的图为什么不存在 (a)没有奇点的图。 (b)所有顶点的度为三的图。 (c)阶至少为5的图G ,且对于G 中任意两个邻接的顶点,,v u 均有u deg v deg ≠。 (d)阶至少为5的非完全图H ,且对于H 中任意两个不邻接的顶点,,v u 均有u deg v deg ≠。 解：（a ） （b ） (c) (d) 2.4 给出一个阶为6且边数为10的图G ,满足.4)(,3)(=∆=G G δ 解：所求图如下所示：
2.6 在一个阶为)1(3≥n n 的图中，若度为n n ,1-和1+n 的顶点数个数均为n ，则n 必为偶数。 证：∵n-1+n+n+1=3n; ∴图中仅有度为n+1,n,n-1三种度的顶点 ∑deg(v)=(n-1)n+n*n+(n+1)n=3n 2 由图论第一定理知，3n 2 为偶数 则n 为偶数。 2.8 设G 为n 阶图，若对G 中任意三个互不邻接的顶点v u ,和w ，都有 u deg ,1deg deg -≥++n w v 则G 一定是连通的吗？ 解：不一定，如下图： 2.10 我们已经知道，若n 阶图G 的任意两个不邻接的顶点u 和v 都满足 ,2deg deg -≥+n v u 则G 可能不连通。 (a) 证明：存在n 阶的连通图G ，它满足：对G 中两个任意不邻接的顶点u 和v ，都有,2deg deg -≥+n v u 且G 有两个不邻接的顶点x 和y ，使得y x deg deg +=2n -。 (b) 证明：若n 阶图G 的任意两个不邻接的顶点u 和v 都满足,2deg deg -≥+n v u 则G 至多有两个连通分支。 (c) (b)中的界是紧的吗？ （a ）证：假设deg deg 1u v n +≤-，则由定理4可知G 不是联通的，这与已知矛盾。 ∴原结论正确。 （b ）证：假设存在G1，G2,G3 三个连通分支，其阶数分别为n1,n2,n3,且n1+n2+n3≤n;
图和子图 图 图 G = (V , E)， 其中 V = {νv v v ,......,,21 } V ---顶点集， ν---顶点数 E = {e e e 12,,......,ε} ---边集， ε---边数 例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。 称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。 称顶点a 与e 相邻。称有公共端点的一些边彼此相邻，例如p 与af 。 环（loop ，selfloop ）：如边 l 。 棱（link ）：如边ae 。 重边：如边p 及边q 。 简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：νε ()(),()().G V G G E G ==。 习题 1.1.1 若G 为简单图，则 εν≤⎛⎝ ⎫ ⎭ ⎪2 。 1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。 同构 在下图中， 图G 恒等于图H , 记为 G = H ⇔ V （G)=V(H), E(G)=E(H)。 图G 同构于图F ⇔ V(G)与V(F), E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。 记为 G ≅F 。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 d e f G = (V, E) p q a b c r a y z x w b c d e G =(V , E ) x w b c d e a y z H =(V ‟, E ‟)x ‟ d ‟ w ‟a ‟ b ‟ c ‟ y ‟e ‟z ‟ F =(V ‟‟, E ‟‟)