图论之二部图图形解析
*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
图论讲义第2章-连通性
第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。 §2.1 割点和割边 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。 （注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。 例如，下图中u , v 两点是其割点。 定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。 证明留作习题。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。
图的连通性总结
图的连通性总结 boboo 目录 1.图的遍历及应用 1.1.DFS遍历 1.2.DFS树的边分类 1.3.DFS树的性质 1.4.拓补排序 1.5.欧拉回路 2.无向图相关 2.1求割顶 2.2求图的桥 2.3求图的块 3.有向图相关 3.1求强连通分量（SCC划分） 3.2求传递闭包 4.最小环问题
一、图的遍历及应用 1.1 DFS遍历 DFS是求割顶、桥、强连通分量等问题的基础。 DFS对图进行染色， 白色：未访问； 灰色：访问中（正在访问它的后代）； 黑色：访问完毕 一般在具体实现时不必对图的顶点进行染色，只需进行访问开始时间和访问结束时间的记录即可，这样就可以得出需要的信息了。 -发现时间D[v]:变灰的时间 -结束时间f[v]:变黑的时间 -1<=d[v] 基于MATLAB的实现，此方法可以知道有几个连通域,并且知道各个顶点的归属。Branches中显示各个节点的归属，同一行的为同一连通分支中的节点。其第一列为它的分类数。 例如下图，有五个连通分支，1、2、3在同一个连通分支中。 这是上图的邻接矩阵，同一节点间为0。 Branches中的显示内容，第一列为连通分支数，后边跟着的是给连通分支中的节点。第一行就表示1、2、3为一个连通分支，4自己在一个连通分支中等等。 function [Branches,numBranch]=Net_Branches(ConnectMatrix) % ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ % This program is designed to count the calculate connected components in networks. % Usage [Cp_Average, Cp_Nodal] = Net_ClusteringCoefficients(ConnectMatrix,Type) % Input: % ConnectMatrix --- The connect matrix without self-edges. % Output: % Branches --- A matrix, each rows of which represents the % different connected components. % numBranch --- The numbers of connected components in network % % +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ % Refer: % Ulrik Barandes % Written by Hu Yong, Nov,2010 % E-mail: carrot.hy2010@https://www.wendangku.net/doc/a64619354.html, % based on Matlab 2008a % Version (1.0),Copywrite (c) 2010 % Input check-------------------------------------------------------------% [numNode,I] = size(ConnectMatrix); if numNode ~= I error('Pls check your connect matrix'); end % End check---------------------------------------------------------------% Node = [1:numNode]; Branches = []; while any(Node) Quence = find(Node,1); %find a non-zero number in Node set subField=[]; %one component % start search while ~isempty(Quence) currentNode = Quence(1); Quence(1) = []; %dequeue subField=[subField,currentNode]; Node(currentNode)=0; neighborNode=find(ConnectMatrix(currentNode,:)); for i=neighborNode if Node(i) ~= 0 %first found Quence=[Quence,i]; Node(i)=0; end end end subField = [subField,zeros(1,numNode-length(subField))]; Branches = [Branches;subField]; %save end numBranch = size(Branches,1); 图的连通性 图的连通性2010-07-23 21 ：02 图的连通性 第十三章图的基本概念 第三节图的连通性 一.连通性概念 图中两点的连通：如果在图G中u、v 两点有路相通，则称顶点u、v 在图G中连通。 连通图(connected graph) ：图G中任二顶点都连通。 图的连通分支(connected brch,component) ：若图G 的顶点集 V(G)可划分为若干非空子集V 1,V 2, ?,V w, 使得两顶点属于同一子集当且仅当它们在G 中连通，则称每个子图G为图G的一个连通分支(i=1,2, ?,w) 。 注：(1) 图G的连通分支是G的一个极大连通子图。 (2)图G连通当且仅当w=1。 例13.5 设有2n 个电话交换台，每个台与至少n 个台有直通线路，则该交换系统中任二台均可实现通话。 证明：构造图G如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。问题化为：已知图G有2n 个顶点，且 δ(G) ≥n，求证G连通。 事实上，假如G不连通，则至少有一个连通分支的顶点数不超过n。在此连通分支中，顶点的度至多是n–1。这与δ(G)≥n 矛盾。 证毕 例13.6 若图中只有两个奇度顶点，则它们必连通。 证明：用反证法。假如u与v 不连通，则它们必分属于不同的连通分支。将每个分支看成一个图时，其中只有一个奇度顶点。这与推论13.1 矛盾。证毕 在连通图中，连通的程度也有高有低。 例如 后面将定义一种参数来度量连通图连通程度的高低。 二.割点 定义13.2 设v∈V(G)，如果w(G–v)w(G) ，则称v 为G的一个割点。( 该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别) 。 例如 定理13.3 如果点v 是图G的一个割点，则边集E(G)可划分为两个非空子集E 1和E 2，使得G[E 1]和G[E 2]恰好有一个公共顶点 v。 推论13.2 对连通图G，顶点v 是G的割点当且仅当G–v 不连通。 以上两个结论的证明留作习题。 三.顶点割集 定义13.3 对图G，若V(G)的子集V' 使得 w(G–V')w(G), 则称V'为图G的一个顶点割集。含有k 个顶点的顶点割集称为k-顶点割集 第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §2.1 割边、割点与连通度 一、割点： 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。（该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。 例 定理2.1.1 如果点v 是图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得 ][1E G 和][2E G 恰好有一个公共顶点v 。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 以上两个结论的证明留作习题。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。 推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。 证明：设T 是G 的生成树，则T 至少有两个叶子u ,v ，由上一定理知，u ,v 都不是T 的割点，即1)()(==?T w u T w 。由于u T ?是图u G ?的生成树，故 )(1)()()(G w T w u T w u G w ===?=?， 离散数学图论作业3-图的连通性 Problem1 判断下列各图是否是强连通的，如果不是，再判断是否是弱连通的。 (1)(2)(3) Problem2 证明：简单图G是二部图（bipartite graph），当且仅当G没有包含奇数条边的回路。 Problem3 a)证明或反驳：存在函数f:N→N使得对于所有k∈N，最小度至少为f(k)的图一定是k-连通的。 b)证明或反驳：存在函数f:N→N使得对于所有k∈N，边连通度至少为f(k)的图一定是k-连通的。Problem4 。（λ(G)表示G的边连通度） 证明：κ(G)=1的r-正则图G，若r>1，总满足λ(G)≤r 2 Problem5 证明：G是2-边连通图当且仅当G中任意两个顶点之间至少有两条不含公共边的通路。 （提示：证明过程中可使用Whitney定理，但需注意和本题的差异） Problem6 证明：若G是k?边连通图，从G中任意删除k条边，最多得到2个连通分支。 Problem7 对于任意的简单连通图G， 1.证明V(G)=E(G)时，G中有且仅有1个简单回路。（可直接使用V(G)=E(G)?1时图G中无简单 回路的结论） 2.该结论能否推广为E(G)≥V(G)时G中有且仅有E(G)?V(G)+1个简单回路？ *题中简单回路不存在重复的边，可能存在大于1个重复顶点（见P573定义1） Problem8 证明：若简单图G是不连通的，则G的补图是连通图。 Problem9 证明：任意简单连通图G包含一条长度至少为min{2δ(G),|V(G)|?1}的顶点和边均不重复的通路。 （提示：证明过程中可以考虑图G中最长的[顶点和边均不重复的]通路） 实验2 划分子网与连通性测试 实验学时：2 一、实验目的 掌握IP地址的分配和划分子网的方法。 二、实验环境 用以太网交换机连接起来的Win2003操作系统计算机和Boson NetSim模拟器。 三、实验内容及步骤 1、IP地址分配 2、划分子网 3、模拟器应用 四、预备知识 1. 常见的网络设备 1.1 集线器 集线器的英文称为“Hub”。“Hub”是“中心”的意思，集线器的主要功能是对接收到的信号进行再生整形放大，以扩大网络的传输距离，同时把所有节点集中在以它为中心的节点上。它工作于OSI(开放系统互联参考模型)参考模型第一层，即“物理层”。集线器与网卡、网线等传输介质一样，属于局域网中的基础设备，采用CSMA/CD（一种检测协议）访问方式。 集线器属于纯硬件网络底层设备，基本上不具有类似于交换机的"智能记忆"能力和"学习"能力。它也不具备交换机所具有的MAC地址表，所以它发送数据时都是没有针对性的，而是采用广播方式发送。也就是说当它要向某节点发送数据时，不是直接把数据发送到目的节点，而是把数据包发送到与集线器相连的所有节点，如图1所示。 图1-1 集线器部署图 图1-2 集线器hub 1.2 网桥 网桥（Bridge）也称桥接器，是连接两个局域网的存储转发设备，用它可以完成具有相同或相似体系结构网络系统的连接。一般情况下，被连接的网络系统都具有相同的逻辑链路控制规程（LLC），但媒体访问控制协议（MAC）可以不同。网桥是数据链路层的连接设备，准确他说它工作在MAC子层上。网桥在两个局域网的数据链路层（DDL）间接帧传送信息，起桥接的作用。 图1-3 网桥 1.3 交换机 交换机(Switch)也叫交换式集线器，是一种工作在OSI第二层(数据链路层)，基于MAC (网卡的介质访问控制地址)识别、能完成封装转发数据包功能的网络设备。它通过对信息进行重新生成，并经过内部处理后转发至指定端口，具备自动寻址能力和交换作用。 交换机不懂得IP地址，但它可以“自学习”源主机的MAC地址，并把其存放在内部地 第七章 平面图 §7.1 平面图的概念 定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。 定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。 定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图G 是简单图。 定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。 定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即 其中R 1, R 2, … , R r 是G 的所有面。 证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。 1 deg()2().r i i R G ε==∑ 实验三：图的连通性判断 一、实验目的 用计算机语言编写图的连通性判断算法，可输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数，掌握Warshell 算法或矩阵幂算法的实现方法。 二、实验原理 1、Warshell 算法 Warshell 算法可解决图是否连通的问题, 而且效率很高。在该算法中，矩阵P 是判断矩阵，1=ij p 表示从i 到j 连通，0=ij p 表示从i 到j 不连通。 (1)置新矩阵 P:= C ; (2)置 i = 1; (3)对所有的j ,若1),(=i j p , 则对k=1,2,…,n , 有),(),(:),(k i p k j p k j p ∨=; (4) 1+=i i ; (5) 如i n ≥转向步骤(3), 否则停止。 2、矩阵幂算法 由于邻接阵包含了图的所有信息，和关联阵一样，是图的等价表示。可以通过对邻接阵C 做一些计算，得到图G 的一些性质。例如考虑3C 中的),(j i 的元素 )3(,j i c ，如果它不为零，由于∑∑=k j l l k k i j i c c c c l ,,,)3(,，则至少存在一组1 ,,,===j l l k k i c c c 或一个长度为3的链使端i 和端j 相连。从而，通过计算C 的各阶幂次可得到关于图是否连通的信息。 三、实验内容 1.利用MATLAB 等语言实现图的连通性判断算法，可对输入的邻接阵进行连通性以及连通分支数的判断。 2.比较Warshell 算法和矩阵幂算法在算法正确性和算法复杂度上的区别。 3.对算法进行优化。 四、采用的语言 MatLab 源代码： clear,clc; %输入邻接矩阵 中间P_2-图的边连通性 图论中边连通度是用来研究网络可靠性的一个参数,它能比较准确的刻画小规模网络的容错性,其相关结论是研究互联网的拓扑结构的有利工具.为了更好的研究图的边连通度,1932年Whitney[1]提出了线图的概念.关于线图已有很多好的结论.后来,Broersmn和Hoede [2]把线图推广,提出了路图的概念.图G的Pk-路图Pk(G)其顶点集是G中所有k长路,其中两点相邻当且仅当在G中它们公共部分是k-1长路且它们的并是k+1长路或圈.显然,k=1时,P1(G)就是图G的线图.图G的中间图M(G)的定义为[15]：顶点集是V(G)∪E(G),其中两点x与y相邻当且仅当{x,y)n E(G)≠φ且x,y在G中相邻或关联.本文中,我们把中间图M(G)的概念推广,给出中间Pk-图Mk(G)的概念.图G的中间Pk-图Mk(G)的定义为：顶点集是V(G)∪V,(Pk(G)),边集是E(Pk(G))∪Ek,其中Ek={(v,p):p∈V(Pk(G)),v 是p的一个端点.}由上面定义,我们有：k=1时,M1(G)=M(G),k=2时,M2(G)=(V(G)∪V{P2(G),E(P2(G))∪E2).如果图G中含有一个包含所有边的闭迹,称图G是欧拉图.所有顶点度数是偶数的图称为偶图；所有顶点度数是奇数的图称为奇图.本文主要证明了：(1)顶点数|V(G)|≥3的连通图G,若6(G)≥2,则P2(G)连 通,M2(G)连通,且入(M2(G))≥2.(2)设G是连通图,如果δ(G)≥3,则λ(M2(G))≥2δ(G).(3)设G是连通图,若G是欧拉图,则M2(G)也是欧拉图.(4)设G和M2(G)都是连通图,若M2(G)是欧拉图,则G是偶图或奇图.图的连通性判断
图的连通性
图论讲义2连通性
离散数学图论作业3-图的连通性
实验2划分子网与连通性测试
图论讲义第7章-平面图
(完整版)图的连通性判断matlab实验报告
中间P_2-图的边连通性