第 10章 几种典型图第 10章 几种典型图
10.1 欧拉图
10.2 哈密顿图
10.3 平面图
10.4 二分图
10.5 例题选解习 题 十第 10章 几种典型图
10.1 欧 拉 图欧拉图的概念是瑞士数学家欧拉 （ LeonhardEuler）
在研究哥尼斯堡 （ K nigsberg） 七桥问题时形成的 。 在当时的哥尼斯堡城,有七座桥将普莱格尔 （ Pregel） 河中的两个小岛与河岸连接起来 （ 见图 10.1.1（ a））,
当时那里的居民热衷于一个难题：一个散步者从任何一处陆地出发,怎样才能走遍每座桥一次且仅一次,
最后回到出发点？
第 10章 几种典型图这个问题似乎不难,谁都想试着解决,但没有人成功 。 人们的失败使欧拉猜想：也许这样的解是不存在的,1936年他证明了自己的猜想 。
为了证明这个问题无解,欧拉用 A,B,C,D四个顶点代表陆地,用连接两个顶点的一条弧线代表相应的桥,从而得到一个由四个顶点,七条边组成的图
（ 见图 10.1.1（ b））,七桥问题便归结成：在图 10.1.1
（ b） 所示的图中,从任何一点出发每条边走一次且仅走一次的通路是否存在 。
第 10章 几种典型图欧拉指出,从某点出发再回到该点,那么中间经过的顶点总有进入该点的一条边和走出该点的一条边,
而且路的起点与终点重合,因此,如果满足条件的路存在,则图中每个顶点关联的边必为偶数 。 图 10.1.1
（ b） 中每个顶点关联的边均是奇数,故七桥问题无解 。
欧拉阐述七桥问题无解的论文通常被认为是图论这门数学学科的起源 。
第 10章 几种典型图图 10.1.1
B
C
( a )
A
D
A
B
D
C
( b )
第 10章 几种典型图
1.欧拉无向图定义 10.1.1 设 G=〈 V,E〉 是连通图,经过 G中每一条边一次且仅一次的通路 （ 起点,终点不重合 ） 称为欧拉通路 （ 欧拉开迹 ）,有欧拉通路的图称半欧拉图；
经过每一条边一次且仅一次的回路称为欧拉回路 （ 欧拉闭迹 ）,有欧拉回路的图称欧拉图 。 一条欧拉通路即为一条行遍图中每条边的简单通路 （ 迹 ）,亦即一笔画问题 。
第 10章 几种典型图定理 10.1.1 设 G是连通图,G是欧拉图当且仅当 G
的所有顶点均是偶度数点 。
证明 先证必要性 。
设 G中有欧拉回路,v0e1v1e2v2…eiviei+1…ekv0,其中顶点可重复出现,边不可重复出现 。 在序列中,每出现一个顶点 vi,它关联两条边,而 vi可以重复出现,所以 d（ vi） 为偶数 。
第 10章 几种典型图再证充分性 。
若图 G是连通的,则可以按下列步骤构造一条欧拉回路：
（ 1）从任一顶点 v0开始，取关联于 v0的边 e1到 v1，
因为所有顶点为偶度数点，且 G是连通的，所以可继续取关联于 v1的边 e2到 v2……每条边均是前面未取过的，直到回到顶点 v0，得一简单回路 l1,v0e1v1e2v2…eiviei+1…ekv0。
第 10章 几种典型图
（ 2） 若 l1行遍 G中所有的边,则 l1就是 G中欧拉回路,即 G为欧拉图,否则 G-l1=G1不是空集,G1中每个顶点均是偶度数点,又 G连通,G1与 l1必有一个顶点 vi
重合,在 G1中从 vi出发重复步骤 （ 1）,可得一简单回路 l2,vie′1u1e′2…vi。
（ 3） 若 l1∪ l2=G,则 G即为欧拉图,欧拉回路为
l1∪ l2,v0e1v1e2v2…eivie′1u1e′2…viei+1vi+1…ekv0,否则,重复步骤 （ 2）,直到构造一条行遍 G中所有边的回路为止,此回路即为欧拉回路,G是欧拉图 。
第 10章 几种典型图定理 10.1.2 设 G是连通图,则 G是半欧拉图当且仅当 G中有且仅有两个奇度数顶点 。
证明 证法类同定理 10.1.1。 只是步骤 （ 1） 从一个奇度数顶点 v0开始,取关联于 v0的边 e1到 v1……直到另一个奇度数顶点 vk为止,得一条简单通路 l1。 其他步骤与定理 10.1.1同 。 最后构造出一条行遍 G中所有边的简单通路,即为欧拉通路,G是半欧拉图 。
定理提供了判断欧拉图和半欧拉图的方法,由此易知,哥尼斯堡七桥问题无解 。
例如,图 10.1.2中 （ a） 是欧拉图,图 （ b） 是半欧拉图,图 （ c） 既非欧拉图也非半欧拉图 。
第 10章 几种典型图图 10.1.2
e
1 0
e
1
e
9
e
3
e
4
e
2
e
5
e
6
e
7
e
8
( a ) ( b ) ( c )
1
0
5 4
3
2
第 10章 几种典型图当给定了一个欧拉图后,如何找出它的一条欧拉回路？ 下面的 Fleury（ 于 1921年提出 ） 算法解决了这个问题,这个算法的实质是,避桥,。
设 G是欧拉图 。
（ 1） 任选 G的一个顶点 v0为起点,并设零条边的通路为 l0=v0。
（ 2） 设已选好的简单通路为 li=v0e1v1e2v2…eivi,则按下述方法从 E-{e1,e2,…,ei}中选取边 ei+1：
第 10章 几种典型图
① ei+1与 vi关联；
② 除非没有别的边可选择,否则 ei+1不是 Gi=G-
{e1,e2,…,ei}的割边 （ 桥 ） 。
（ 3） 当第 (2)步不能继续进行时 （ 所有的边已走遍 ）,算法终止 。
第 10章 几种典型图
【 例 10.1.1】 找出图 10.1.2（ a） 所示图 G的一条欧拉回路 。
解 从 v0出发,先找到 l3=v0e1v1e2v4e3v6,因为此时在
G3=G-{e1,e2,e3}中,关联 v6的边 e9和 e10均是割边,所以只能选取 e4,继续下去,最后可得一条欧拉回路：
l=v0e1v1e2v4e3v5e4v2e5v4e6v3e7v2e8v1e9v5e10v0
第 10章 几种典型图最后介绍一下,中国邮递员问题,（ the Chinese
Postman Problem）。我国数学家管梅谷于 1962年首先提出这个问题，并得到一些结果，得到世界同行们的承认。该问题是说：邮递员从邮局出发在他的管辖区域内投递邮件，然后回到邮局。自然，他必须走过他所辖区域内的每一条街道至少一次。在此前提下，希望找到一条尽可能短的路线。
第 10章 几种典型图设 G=〈 V,E,w〉 是一带权图,l是 G的一条回路,
称 为 l的权 。 中国邮递员问题就是在带非负权的连通图中找到一条权最小的行遍所有边的回路,
称此回路为最佳周游 。
若 G是欧拉图,则 G中的任何一条欧拉回路均是最佳周游,而寻找欧拉回路的 Fleury算法为解决这一问题提供了切实可行的方法 。 对于非欧拉图,也有相应的算法,限于篇幅不再介绍 。
()
i
i
el
e?
第 10章 几种典型图
2.欧拉有向图定义 10.1.2 设 G是连通有向图,若 G中有经过所有边一次且仅一次的有向通路 （ 起点,终点不重合 ）,
则称为有向欧拉通路,具有有向欧拉通路的图称为半欧拉有向图；若 G中有经过所有边一次且仅一次的有向回路,则称为有向欧拉回路,具有有向欧拉回路的图称为欧拉有向图 。
显然,如果 G是欧拉有向图,则 G必是强连通图 。
第 10章 几种典型图类似于定理 10.1.1,10.1.2,可得下面定理：
定理 10.1.3 设 G是连通有向图,则 G是欧拉有向图当且仅当 G中的每个顶点 v均有 d+（ v） =d-（ v） 。
定理 10.1.4 设 G是连通有向图,则 G是半欧拉有向图当且仅当 G中恰有两个奇度数顶点,其中一个入度比出度大 1,另一个出度比入度大 1,而其他顶点的出度等于入度 。
例如,图 10.1.3中 （ a） 是欧拉有向图,图 （ b） 是半欧拉有向图,图 （ c） 既非欧拉有向图也非半欧拉有向图 。
第 10章 几种典型图图 10.1.3
( a ) ( b ) ( c )
第 10章 几种典型图
【 例 10.1.2】 计算机鼓轮设计问题,
设计旋转鼓轮,要将鼓轮表面分成 16个扇区,如图 10.1.4（ a） 所示,每块扇区用导体 （ 阴影区 ） 或绝缘体 （ 空白区 ） 制成,如图 10.1.4（ b） 所示,四个触点 a,b,c和 d与扇区接触时,接触导体输出 1,接触绝缘体输出 0。 鼓轮顺时针旋转,触点每转过一个扇区就输出一个二进制信号 。 问鼓轮上的 16个扇区应如何安排导体或绝缘体,使得鼓轮旋转一周,触点输出一组不同的二进制信号？
第 10章 几种典型图显然，图 10.1.4（ b）所示，旋转时得到的信号依次为 0010,1001,0100,0010,…，在这里,0010出现了两次，所以这个鼓轮是不符合设计要求的。按照题目要求，鼓轮的 16个位置与触点输出的 16个四位二进制信号应该一一对应，亦即 16个二进制数排成一个循环序列，使每四位接连数字所组成的 16个四位二进制子序列均不相同。这个循环序列通常称为笛波滤恩
（ DeBruijn）序列。如图 10.1.4（ c）所示,16个扇区所对应的二进制循环序列正是笛波滤恩序列。
第 10章 几种典型图图 10.1.4
( a ) ( b )
a
b
c
d
( c )
a
b
c
d
第 10章 几种典型图图 10.1.5
0 0 1 1 0 0
0 0 0
0 1 1 1 1 0
1 0 1
0 1 0
1 1 1
e
1 5
＝ 1 1 1 1
e
1 4
＝ 1 1 1 0
e
6
＝ 0 1 0 1
e
7
＝ 0 1 1 1
e
1 1
＝ 1 0 1 1 e
1 3
＝ 1 1 0 1
e
1 2
＝ 1 1 0 0
e
1 0
＝ 1 0 1 0e
5
＝ 0 1 0 1e
3
＝ 0 0 1 1
e
2
＝ 0 0 1 0 e
4
＝ 0 1 0 0
e
1
＝ 0 0 0 1 e
8
＝ 1 0 0 0
e
9
＝ 1 0 0 1
e
0
＝ 0 0 0 0
第 10章 几种典型图
10.2 哈密顿图哈密顿图的概念源于 1859年爱尔兰数学家威廉 ·哈密顿爵士（ SirWillianHamilton）提出的一个,周游世界,的游戏。这个游戏把一个正十二面体的二十个顶点看成是地球上的二十个城市，棱线看成连接城市的道路，要求游戏者沿着棱线走，寻找一条经过所有顶点（即城市）一次且仅一次的回路，如图 10.2.1（ a）
所示。也就是在图 10.2.1（ b）中找一条包含所有顶点的初级回路，图中的粗线所构成的回路就是这个问题的回答。
第 10章 几种典型图图 10.2.1
( a ) ( b )
第 10章 几种典型图定义 10.2.1 若图 G中有一条经过所有顶点一次且仅一次的回路,则称该回路为哈密顿回路,称 G为哈密顿图；若图 G中有一条经过所有顶点一次且仅一次的通路,
则称此通路为哈密顿通路,称 G为半哈密顿图 。
乍一看,哈密顿图与欧拉图有某种对偶性 （ 点与边的对偶性 ）,但实际上,前者的存在性问题比后者难得多 。 迄今为止,寻找到一个判断哈密顿图的切实可用的充分必要条件仍是图论中尚未解决的主要问题之一 。 人们只是分别给出了一些必要条件和充分条件 。
第 10章 几种典型图定理 10.2.1 若 G是哈密顿图,则对于顶点集 V的每一个非空子集 S,均成立
P（ G-S） ≤|S|
其中,P（ G-S） 是 G-S的连通分支数,|S|是 S中顶点的个数 。
第 10章 几种典型图证明 设 C是图 G中的一条哈密顿回路,S是 V的任
a1∈ S,C-{a1}是一条初级通路，若再删去 a2∈ S，则当 a1,a2邻接时,P（ C-{a1,a2}） =1＜
2；而当 a1,a2不邻接时,P（ C-{a1,a2}） =2，即
P（ C-{a1,a2}） ≤2=|{a1,a2}|
如此做下去,归纳可证
P（ C-S） ≤|S|
因为 C-S是 G-S的生成子图，所以
P（ G-S） ≤P（ C-S） ≤|S|。
第 10章 几种典型图图 10.2.2
第 10章 几种典型图这个定理给出的只是一个无向图是哈密顿图的必要条件,亦即哈密顿图必满足这个条件,满足这个条件的不一定是哈密顿图 。
例如,著名的彼得森 （ Petersen） 图 （ 如图 10.2.2所示 ） 不是哈密顿图,但对任意的 S V,S≠,均满足
P(C-S)≤|S|
然而,不满足这个条件的必定不是哈密顿图 。
第 10章 几种典型图
【 例 10.2.1】 含有割点的图必定不是哈密顿图 。
证明 设 v是图 G中的割点,则
P（ G-v） ≥2＞ |{v}|
因此,图 G不是哈密顿图 。
下面介绍无向图中有哈密顿通路的充分条件 。
第 10章 几种典型图定理 10.2.2 若 G是 n（ n≥3） 个顶点的简单图,对于每一对不相邻的顶点 u,v,满足
d（ u） +d（ v） ≥n-1
则 G中存在一条哈密顿通路 。
证明 首先证明 G是连通图。假设 G非连通，则 G至少有两个连通分支 G1,G2，设 G1中有 n1个顶点,G2中有 n2 v1(V（ G1 v2(V（ G2），因为 d
（ v1） ≤n1-1,d（ v2） ≤n2-1，故 d（ v1） +d（ v2） ≤n1+n2-
2＜ n-1，这与题设条件矛盾，因此,G必连通。
第 10章 几种典型图其次,再证 G中含有哈密顿通路 。 设?是 G中任意一条有 m-1条边的初级通路,v1v2…vm若 m=n,则 l就是 G中的一条哈密顿通路；若 m〈 n,我们来扩充此路 。
（ 1） 如果通路的两个端点 v1,vm还与路?之外的顶点邻接,则延伸此通路 。
（ 2） 如果 v1,vm均只与原通路?上的顶点邻接,如下可证,G中有一条包含 l的长度为 m的回路 。
若 v1与 vm邻接,则 v1v2…vmv1即所求之回路 。
若 v1与 vi1,vi2…,vip邻接,1＜ i1,i2,…,ip＜ m，
考虑 vm：
第 10章 几种典型图图 10.2.3
( a )
( b )
( c )
1 2 i － 1
1 1
i
m
m
m
1
i
1
1
k － 1
k － 1
k
k
k ＋ 1
k ＋ 1
i － 1
1
第 10章 几种典型图重复过程 （ 1）,（ 2）,不断扩充通路 l,直至它的长度为 n-1,这时便得到 G中的一条哈密顿通路 。 证毕仿此可证：
定理 10.2.3 若 G是 n（ n≥3） 个顶点的简单图,对于每一对不相邻的顶点 u,v,满足
d（ u） +d（ v） ≥n
则 G中存在一条哈密顿回路 。 即 G是哈密顿图 。
推论 1 设 G是 n（ n≥3） 阶无向简单图,若 δ（ G）
≥n/2,则 G是哈密顿图 。
推论 2 完全图 Kn（ n≥3） 均是哈密顿图 。
第 10章 几种典型图
【 例 10.2.2】 设 n≥2,有 2n个人参加宴会,每个人至少认识其中的 n个人,怎样安排座位,使大家围坐在一起时,每个人的两旁坐着的均是与他相识的人？
解 每个人用一个顶点表示，若二人相识，则在其所表的顶点间连边。这样得到一个 2n阶的无向图，因为 δ（ G） ≥n u,v∈ V（ G）,d（ u） +d（ v）
≥2n，故图中存在一条哈密顿回路，这条回路恰好对应一个座位的适当安排。
第 10章 几种典型图定理 10.2.4 当 n为不小于 3的奇数时,Kn上恰有 (n-
1)/2条互无任何公共边的哈密顿回路 。
证明 假设 Kn的 n个顶点如图 10.2.4所示排成一个正
（ n-1） 边形 （ 因为 n是奇数,这是可行的 ）,并给出了一条哈密顿回路,v1v2…vnv1。
第 10章 几种典型图图 10.2.4
n
1
4
5
3
2
n － 2
n － 1
n － 3
第 10章 几种典型图顺时针分别旋转（旋转时顶点的标记不动）
3
3603 6 0 2 3 6 0
2,,,
1 1 1
n
n n n
如图 10.2.4所示 。
每旋转一次便产生一条哈密顿回路,且它们之间没有公共边 。 图 10.2.5演示了 n=5时的情景 (图 （ b） 是图 （ a）
旋转 90° 后所得 ),因此,合乎要求的哈密顿回路共有 1+
(n-3)/2=(n-1)/2条 。
第 10章 几种典型图图 10.2.5
( a ) ( b )
4
52
1
3
4
2
1
5
3
第 10章 几种典型图货郎担问题与哈密顿图密切相关的是货郎担问题 。
设有 n个村镇,已知每两个村镇之间的距离 。 一个货郎自某个村镇出发巡回售货,问这个货郎应该如何选择路线,使每个村镇经过一次且仅一次,并且总的行程最短 。 即在一个带权完全图中,找一个权最小的哈密顿图 。
第 10章 几种典型图在 n个顶点的带权完全图中,所有不同的哈密顿回路 （ 包括有公共边的情况 ） 总数是 1/2 (n-1)！ 个 。 在如此众多的哈密顿回路中求一个总的权为最小的哈密顿回路,它的工作量是相当大的,这种求最优解的有效率的算法至今尚未找到 。 下面我们给出一个较好的近似算法 ——最邻近算法 。
设 G=〈 V,E,w〉 是 n个顶点的带权完全图,w是从 E
到正整数集 Z+的函数,对 V中的任何三个顶点 vi,vj，
vk w(vi,vj） +w（ vj,vk） ≥w（ vi,vk）
求最小权的哈密顿回路的最邻近算法步骤如下：
第 10章 几种典型图
（ 1） 任选一点 v0作起点,找一个与 v0最近的相邻顶点 vx,得到一条一边构成的路径 。
（ 2） 设 vx是新加到这条路中的一点,从不在此路中的所有顶点中,选一个与 vx最近的相邻点,将它与 vx连成一边,构成一条新的路径 。 重复过程 （ 2）,直到 G
中所有顶点都在所构成的路径中 。
（ 3） 连接 v0和最后加到路中的顶点,构成一条回路,
它就是带权的哈密顿回路 。
第 10章 几种典型图
【 例 10.2.3】 图 10.2.6（ a） 是一带权无向完全图,
用最邻近法求一条最短哈密顿回路 。
解 算法步骤按图 10.2.6（ b）,（ c）,（ d）,
（ e）,（ f） 的粗线边依次给出,图 （ f） 即所求之带权哈密顿回路,权为 47。
表面上看,最邻近算法,是很合理的,其实不然 。
例如图 10.2.6（ a） 的最短哈密顿回路应该是图 10.2.6
（ g） 所示,它的权为 35,这表明,最邻近算法,可能产生误差 。
第 10章 几种典型图图 10.2.6
5
4
9
8
9
( g )
4
7
8
16
( e )
4
12
7
8
16
( f )
a
b
c d
e
5 5
4
12
9
7
8
8
16
9
( a )
4
( b )
4
7
( c )
4
7
8
( d )
第 10章 几种典型图
10.3 平 面 图定义 10.3.1 若一个图能画在平面上使它的边互不相交 （ 除在顶点处 ）,则称该图为平面图,或称该图能嵌入平面 。
例如图 10.3.1（ a） 是平面图 G,它能嵌入平面上,
如图 10.3.1（ b） 所示 G1,G1是 G的平面嵌入 。
第 10章 几种典型图图 10.3.1
( a ) ( b )
第 10章 几种典型图并非所有的图都能嵌入平面，图 10.3.2（ a）表示的就是非平面图，这个图对应于一个有名的问题 ——公用事业问题。设有三座房子 a,b,c和三个公共设施 d、
e,f，能否使每座房子与每个公共设施之间均有道路连接而无交叉。实践证明这是做不到的，如图 10.3.2（ b）
说明（ a）无法嵌入平面，此图为二分图 K3,3，它是一个非平面图。还有一个重要的非平面图，如图 10.3.2
（ c）、（ d）所示，它就是完全图 K5。 K3,3和 K5又称为库拉托斯基图，它们是波兰数学家库拉托斯基
（ Kuratowsky）发现的典型的非平面图。
第 10章 几种典型图图 10.3.2
( a ) ( b )
a b c
d e f
( c ) ( d )
c d c d
b e
a
a b c
d e f
a
b e
第 10章 几种典型图定义 10.3.2 平面图 G嵌入平面后将平面划分成若干个连通的区域,每一个区域称为 G的一个面,其中面积无限的区域称为外部面或无限面 （ 常记为 R0）,面积有限的称为内部面或有限面,记作 Ri（ i=1,2,…,n）,
包围每个面的所有边所构成的回路称该面的边界,边界的长度称该面的次数,面 Ri的次数记作 deg（ Ri） 。
例如,图 10.3.1（ b） 共有六个面,每个面的次数均为 3。 图 10.3.3所示平面图 G有四个面,deg（ R1） =3，
deg（ R2） =3,deg（ R3） =5,deg（ R0） =9。
第 10章 几种典型图图 10.3.3
R
2
R
1
R
0
R
3
第 10章 几种典型图定义 10.3.3 设 G为一个简单平面图,如果在 G的任意两个不相邻的顶点间再加一条边,所得图为非平面图,则称 G为极大平面图 。
例如,完全图 Kn当 n≤4是都是极大平面图 。 K5在任意删去一条边后,为极大平面图 。 极大平面图有如下的一些性质：
（ 1） 极大平面图均是连通图 。
（ 2） 极大平面图中 （ n≥3）,不含割点和桥 。
第 10章 几种典型图
（ 3）任何 n（ n≥3）阶极大平面图，每个面（包括无限面）的次数均为 3，反之亦然。
（ 4） 最小 （ 含顶点数最少 ） 的极大平面图是 K5。
定义 10.3.4 设 G是非平面图,若在 G中任意删去一条边后,所得图为平面图,则称 G是极小非平面图 。
例如 K5和 K3,3均是极小非平面图 。
定理 10.3.1 在一个平面图 G中,所有面的次数之和为边数的二倍,即
1
de g ( ) 2
r
i
i
Rm
其中,r为 G的面数,m为边数。
第 10章 几种典型图证明 对于 G中的每一条边 e,e或是两个面的公共边,
或是在一个面中为悬挂边被作为边界计算两次,故定理成立 。 证毕定理 10.3.2 设连通平面图 G有 n个顶点,m条边和 r个面,则
n-m+r=2 ——Euler公式证明 施归纳于 G的边数 m。
m=0时,G为平凡图,n=1,r=1,公式成立 。
第 10章 几种典型图设 m=k-1（ k≥1） 时公式成立,现在考虑 m=k时的情况 。 因为在连通图上增加一条边仍为连通图,则有三种情况：
（ 1） 所增边为悬挂边,此时 G的面数不变,顶点数增 1,公式成立 。
（ 2） 在图的任意两个不相邻点间增加一条边,此时 G的面数增 1,边数增 1,但顶点数不变,公式成立 。
（ 3） 所增边为一个环,此时 G的面数增 1,边数增 1，
但顶点数不变,公式成立 。
第 10章 几种典型图定理 10.3.3 设 G是连通的（ n,m）平面图且每个面的次数至少为 l（ l≥3），则
( 2)2lmnl
证明 由定理 10.3.1知
1
2 de g ( )
r
i
i
m R l r
(r为 G的面数 )
再由 Euler公式
n-m+r=2
第 10章 几种典型图于是有
( 2)2lmnl
22 mr m n
l
故第 10章 几种典型图推论 1 设 G是 （ n,m） 连通平面简单图 （ n≥3）,
则
m≤3n-6。
证明 由于 G是 n≥3的连通平面简单图,所以 G的每个面至少由 3条边围成,即 l≤3,代入定理 10.3.3,得
m≤3n-6 证毕第 10章 几种典型图推论 2 极大连通平面图的边数 m=3n-6。
证明 因为极大平面图的每一个面的次数均是 3,所以 3r=2m,代入 Euler公式有
m=3n-6 证毕推论 3 若连通平面简单图 G不以 K3为子图，则
m≤2n-4。
证明 由于 G中不含 K3,所以 G的每个面至少由 4条边围成,即 l≤4,代入定理 10.3.3,得
m≤2n-4 证毕第 10章 几种典型图推论 4 K5和 K3,3是非平面图 。
证明 假设 K5是平面图,由推论 1可知应有 m≤3n-6，
而当 n=5,m=10时,这是不可能的,所以 K5是非平面图 。
假设 K3,3是平面图,因其不含子图 K3,由推论 2可知,
当 n=6,m=9时,m≤2n-4是不可能的,所以 K3,3是非平面图 。 证毕第 10章 几种典型图定理 10.3.4 在平面简单图 G中至少有一个顶点 v0，
d（ v0） ≤5。
证明 不妨设 G是连通的,否则就其一个连通分支讨论再推广至全图 。 用反证法证明 。
假设一个平面简单图的所有顶点度数均大于 5,又由欧拉公式推论 1知 3n-6≥m,所以
6 1 2 2 ( ) 6
V
n m d n
这是不可能的 。 因此平面简单图中至少有一个顶点 v0，其度数 d（ v0） ≤5。
证毕第 10章 几种典型图找出一个图是平面图的充分必要条件的研究曾经持续了几十年,直到 1930年库拉托斯基给出了平面图的一个非常简洁的特征,先介绍一些预备知识 。
在一个无向图 G的边上,插入一个新的度数为 2的顶点,使一条边分成两条边,或者对于关联同一个度数为 2的顶点的两条边,去掉这个 2度顶点,使两条边变成一条边,如图 10.3.4（ a）,（ b） 所示,这些都不会改变图原有的平面性,如图 10.3.4（ c）,（ d） 所示 。
图 10.3.4所表示的称为,图的同胚,。
第 10章 几种典型图图 10.3.4
( d )( c )( b )( a )
第 10章 几种典型图定义 10.3.5 如果两个图 G1和 G2同构,或者通过反复插入或删除度数为 2的顶点后同构,则称 G1和 G2同胚 。
由于同胚的两个图具有相同的平面性,而 K5和 K3,3
是典型的非平面图,因此有：
定理 10.3.5（ Kuratowsky定理 ） 一个图是平面图的充分必要条件是它不含与 K5或 K3,3同胚的子图 。 证明略 。
第 10章 几种典型图
【 例 10.3.1】 证明图 10.3.5中的 （ a） 和 （ d） 不是平面图 。
解 图 (a）是著名的彼得森（ Pertersen）图，去掉其中的两条边后得子图（ b），该子图同胚于 K3,3
（ c）。因此彼得森图不是平面图。图（ d）图中含有子图（ e），图（ e）图同构于 K3,3 （ f）。
库拉托斯基定理虽然简单漂亮,但实现起来并不容易,特别是顶点数较多的时候,还有许多这方面的研究工作要做 。
第 10章 几种典型图图 10.3.5
a
f
g j
h i
b e
c d
a
f
g j
h i
b e
c d
( a ) ( b )
a h i
j
d
efb
g
c
( c )
( f )
1 2
5 6
( e )( d )
3 4
1 2
5 6
3 4
1
2 5
6
3
4
第 10章 几种典型图
1.对偶图平面图有一个很重要的特性,任何平面图都有一个与之对应的平面图,称为它的对偶图 。 下面提到的平面图均以它的平面嵌入表示 。
定义 10.3.6 设平面图 G=〈 V,E〉 有 r个面 R1,R2,…，
Rr,则用下面方法构造的图 G*=〈 V*,E*〉 称为 G的对偶图：
（ 1 Ri∈ G，在 Ri内取一顶点 v*i∈ V*,i=1，
2,…,r。
（ 2 e∈ E。
第 10章 几种典型图
① 若 e是 G中两个不同面 Ri和 Rj的公共边,则在 G*中画一条与 e交叉的边 （ v*i,v*j） ；
② 若 e是一个面 Ri内的边 （ 即 Ri是桥 ）,则在 G*中画一条与 e交叉的环 （ v*i,v*i） 。
例如,图 10.3.6（ a） 和 （ b） 中,G*是 G的对偶图,
G的边用实线表示,G*的边用虚线表示,顶点用实心点表示 。
第 10章 几种典型图图 10.3.6
( a ) ( b )
第 10章 几种典型图定义 10.3.7 若平面图 G与其对偶图 G*同构,则称 G
是自对偶图 。
例如,图 10.3.6（ b） 实线图所示的 4阶 3度正则图就是一个自对偶图 。
定理 10.3.6 设 G*是连通平面图 G的对偶图,n*，
m*,r*和 n,m,r分别是 G*和 G的顶点数，边数和面数，
则 n*=r,m*=m,r*=n，且 d（ v*i） =deg（ Ri）,i=1，
2,…,r。
第 10章 几种典型图证明 由定义 10.3.6对偶图的构造过程可知,n*=r，
m*=m和 d（ vi） =deg（ Ri） 显然成立,下证 r*=n。 因为
G和 G*均是连通的平面图,所以由欧拉公式有
n-m+r=2
n*-m*+r*=2
由 n*=r,m*=m可得 r*=n。 证毕由于平面图 G的对偶图 G*也是平面图,因此同样可对 G*求对偶图,记作 G**,如果 G是连通的,则 G**
与 G之间有如下关系 。
第 10章 几种典型图定理 10.3.7 G是连通平面图当且仅当 G**同构于 G。
证明略 。
由对偶图的构造过程可知,平面图 G的任何两个对偶图必同构 。 但是若平面图 G1和 G2是同构的,其对偶图 G*1和 G*2未必同构 。 如图 10.3.7中两个平面图 G1和 G2
是同构的,但由于 G1（ 如图 10.3.7（ a） 所示 ） 中有一个面次数为 5,而 G2（ 如图 10.3.7（ b） 所示 ） 中没有这样的面,因此 G1和 G2不会同构 。
第 10章 几种典型图图 10.3.7
a
b c
de
f
G
1
G
2
b
a
c
d
e
f
( a ) ( b )
第 10章 几种典型图
2.着色问题在地图上,相邻国家涂不同的颜色,最少需要多少种颜色？ 100多年前,有人提出了,四色猜想,,即只用四种颜色就能做到,但一直无法证明,直到 1976
年美国数学家才用电子计算机证明了这一猜想 。
地图着色自然是对平面图的面着色,利用对偶图,
可将其转化为相对简单的顶点着色问题,即对图中相邻的顶点涂不同的颜色 。
第 10章 几种典型图定义 10.3.8 设 G是一个无自环的图,给 G的每个顶点指定一种颜色,使相邻顶点颜色不同,称为对 G的一个正常着色 。 图 G的顶点可用 k种颜色正常着色,称 G
是 k― 可着色的 。
使 G是 k― 可着色的数 k的最小值称为 G的色数,记作 χ（ G） 。 如果 χ（ G） =k,则称 G是 k― 色的 。
第 10章 几种典型图设 G无自环且连通,如果有多重边,则可删去多重边,用一条边代替,因此下面考虑的都是连通简单图 。
有几类图的色数是很容易确定的,即：
定理 10.3.8
（ 1） G是零图当且仅当 χ（ G） =1。
（ 2）对于完全图 Kn，有 χ（ Kn） =n，而 χ（ ） =1。
（ 3） 对于 n个顶点构成的回路 Cn,当 n为偶数时,χ
（ Cn） =2；当 n为奇数时,χ（ Cn） =3。
（ 4） 对于顶点数大于 1的树 T,有 χ（ T） =2。
nK
第 10章 几种典型图到现在还没有一个简单的方法可以确定任一图 G是
n― 色的 。 但韦尔奇 ·鲍威尔 （ WelchPowell） 给出了一种对图的着色方法,步骤如下：
（ 1） 将图 G中的顶点按度数递减次序排列 。
（ 2） 用第一种颜色对第一顶点着色,并将与已着色顶点不邻接的顶点也着第一种颜色 。
（ 3）按排列次序用第二种颜色对未着色的顶点重复（ 2）。用第三种颜色继续以上做法，直到所有的顶点均着上色为止。
第 10章 几种典型图图 10.3.8
a
g
h
f
d
c
b
e
第 10章 几种典型图
【 例 10.3.2】 用韦尔奇 ·鲍威尔法对图 10.3.8中的图着色 。
（ 1） 各顶点按度数递减次序排列,c,a,e,f,b,h,g,d。
（ 2） 对 c和与 c不邻接的 e,b着第一种颜色 。
（ 3） 对 a和与 a不邻接的 g,d着第二种颜色 。
（ 4） 对 f和与 f不邻接的 h着第三种颜色 。
第 10章 几种典型图定理 10.3.9 如果图 G的顶点的度数最大的为 Δ
（ G）,则 χ（ G） ≤1+Δ（ G） 。
证明 施归纳于 G的顶点度数 。
当 n=2时,G有一条边,Δ（ G） =1,G是 2― 可着色的,所以 χ（ G） ≤1+Δ（ G） 。 假设对于 n-1个顶点的图,结论成立 。
第 10章 几种典型图现假设 G有 n个顶点,顶点的最大度数为 Δ（ G）,
如果删去任一顶点 v及其关联的边,得到 n-1个顶点的图,它的最大度数至多是 Δ（ G）,由归纳假设,该图是 1+Δ（ G） ― 可着色的,再将 v及其关联的边加到该图上,使其还原成图 G,顶点 v的度数至多是 Δ（ G）,
v的相邻点最多着上 Δ（ G） 种颜色,然后 v着上第 1+Δ
（ G） 种颜色,因此 G是 1+Δ（ G） ― 可着色的,故
χ（ G） ≤1+Δ（ G） 。 证毕第 10章 几种典型图定理 10.3.8所给出的色数的上界是很弱的，例如树
T,χ（ T） =2，而 Δ（ T）可以很大。布鲁克斯（ Brooks）
在 1941年证明了这样的结果，使
χ（ G） =1+Δ（ G）的图只有两类：或是奇回路，或是完全图。
定理 10.3.10 任何平面图是 5― 可着色的 。
证明 不妨设 G是简单平面图 。 施归纳于 G的顶点数 n。 当 n≤5时结论显然成立 。
第 10章 几种典型图假设对所有 n-1个顶点的平面图是 5― 可着色的。
现考虑有 n个顶点的平面图 G，由定理 10.3.4可知，在 G
中存在着顶点 v0,d（ v0） ≤5。由归纳假设,G-v0是 5-可着色的，在给定了 G-v0的一种着色后，将 v0及其关联的边加到原图中，得到 G，分两种情况考虑：
第 10章 几种典型图
（ 1） 如果 d（ v0） ＜ 5,则 v0的相邻点已着上的颜色小于等于 4种,所以 v0可以着另一种颜色,是 G是 5― 可着色的 。
（ 2） 如果 d（ v0） =5,则将 v0的邻接点依次记为 v1，
v2,…,v5,并且对应 vi着第 i色,如图 10.3.9（ a） 所示 。
第 10章 几种典型图图 10.3.9
1
2
34
5
4
3
1
1
3
1
3
1
5 2
( a ) ( b )
1
2
0
34
5
2
0
34
5
1
第 10章 几种典型图设 H13为 G-v0的一个子图,它是由着色 1和 3的顶点集导出的子图 。 如果 v1和 v3属于 H13的不同分支,将 v1所在分支中着色 1的顶点与着色 3的顶点颜色对换,这时
v1着色 3,这并不影响 G-v0的正常着色 。 然后将 v0着色 1，
因此 G是 5― 可着色的 。
第 10章 几种典型图如果 v1和 v3属于 H13的同一分支,则在 G中存在一条从 v1到 v3的路,它的所有顶点着色 1或 3。 这条路与路
v1v0v3一起构成一条回路,如图 10.3.9（ b） 所示 。 它或者把 v2围在它里面,或者同时把 v4和 v5围在它里面 。 由于 G是平面图,在上面任一种情况下,都不存在连接 v2
和 v4并且顶点着色 2或 4的一条路 。
第 10章 几种典型图现在设 H24为 G-v0的另一个子图,它是由着色 2和 4的顶点导出的子图,则 v2和 v4属于 H24的不同分支 。 于是在 v2
所在分支中将着色 2的顶点和着色 4的顶点颜色对换,
v2着色 4,这样导出了 G-v0的另一种正常着色,然后在
v0着色 2,同样可得 G是 5― 可着色的 。
第 10章 几种典型图
10.4 二 分 图定义 10.4.1 若无向图 G=〈 V,E〉 的顶点集 V能分成两个子集 V1和 V2,满足
（ 1） V=V1∪ V2,V1∩V2= ；
（ 2） e=（ u,v） ∈ E,均有 u∈ V1,v∈ V2。
则称 G为二分图,V1和 V2称为互补顶点子集,常记为 G=〈 V1,V2,E〉 。 如果 V1中每个顶点都与 V2中所有顶点邻接,则称 G为完全二分图,并记为 Kr,s,其中
r=|V1|,s=|V2|。
第 10章 几种典型图例如,图 10.4.1中的三个图均是二分图,其中图 （ b）
是完全二分图 K3,3,图 （ c） 是 K2,4。
显然,在完全二分图中 Kr,s中,顶点数 n=r+s,边数 m=rs。
一个无向图如果能画成上面的样式,很容易判定它是二分图 。 有些图虽然表面上不是上面的样式,但经过改画就能成为上面的样式,仍可判定它是一个二分图,如图 10.4.2中 （ a） 可改画成图 （ b）,图 （ c）
可改画成图 （ d） 。 可以看出,它们仍是二分图 。
第 10章 几种典型图图 10.4.1
( a ) ( b ) ( c )
第 10章 几种典型图图 10.4.2
( c ) ( d )( b )( a )
a b c
d e f
a c e
b d f
1 2
3
45
6
1 3 5
2 4 6
第 10章 几种典型图定理 10.4.1 非平凡无向图 G是二分图当且仅当 G中无奇数长度的回路 。
证明 先证必要性 。 设 G=〈 V1,V2,E〉 为二分图,
对 G中任一长度为 k的回路 c,vi1vi2…vikvi1,不妨假设
vi1∈ V1,则必有 vi2∈ V2,vi3∈ V1,…,即下标为奇数的顶点属于 V1,下标为偶数的顶点属于 V2,因为 （ vik，
vi1） ∈ c,所以 k为偶数 。 因此,G中任一回路的长度为偶数 。
第 10章 几种典型图再证充分性 。 设 G中无奇数长度的回路,不妨设 G
是连通图,将 G的顶点集 V按下面要求分成两个子集 V1
和 V2：
V1={vi|vi∈ V且 vi与某一给定顶点 v0的距离是偶数 }，
V2=V1-V2
第 10章 几种典型图
【 例 10.4.1】 六名间谍 a,b,c,d,e,f被擒,已知 a懂汉语,法语和日语,b懂德语,俄语和日语,c懂英语和法语,d懂西班牙语,e懂英语和德语,f懂俄语和西班牙语,问至少用几个房间监禁他们,能使在一个房间里的人不能直接对话 。
解 以六人 a,b,c,d,e,f为顶点,在有共同懂得语言的人的顶点间连边得图 G（ 如图 10.4.3（ a） 所示 ）,因为 G中没有奇圈,所以 G是二分图 （ 如图
10.4.3（ b） 所示 ）,故至少应有两间房间即可 。
第 10章 几种典型图图 10.4.3
a b
f
e d
c
( a )
a e f
b c d
( b )
第 10章 几种典型图
【 例 10.4.2】 设 （ n,m） 图 G是二分图,证明 m≤n2/4。
证明 设 G=〈 V1,V2,E〉,|V1|=n1,|V2|=n2，则
n=n1+n2,m≤n1n2。
由 （ a-b） 2=a2+b2-2ab≥0,得
22
2
abab (1)
将 a2+b2+2ab=（ a+b） 2代入 （ 1） 式,得
2( ) 2
2
a b a bab
第 10章 几种典型图二分图的主要应用是匹配,,匹配,是图论中的一个重要内容,它在所谓,人员分配问题,和,最优分配问题,等运筹学中的问题上有重要的应用 。
2
22
12
12
()
4
()
44
ab
ab
n n n
m n n
推得所以第 10章 几种典型图首先看实际中常碰见的问题：给 n个工作人员安排 m
项任务,n个人用 X={x1,x2,…,xn}表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中 k
（ k≥1）个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？
第 10章 几种典型图图 10.4.4
x
1
x
2
x
3
x
4
x
5
y
5
y
4
y
3
y
2
y
1
第 10章 几种典型图例如,现有 x1,x2,x3,x4,x5五个人,y1,y2,y3，
y4,y5五项工作 。 已知 x1能胜任 y1和 y2,x2能胜任 y2和 y3，
x3能胜任 y2和 y5,x4能胜任 y1和 y3,x5能胜任 y3,y4和 y5。
如何安排才能使每个人都有工作做,且每项工作都有人做？
第 10章 几种典型图显然,我们只需做这样的数学模型：以 xi和 yj（ i，
j=1,2,3,4,5） 为顶点,在 xi与其胜任的工作 yj之间连边,得二分图 G,如图 10.4.4所示,然后在 G中找一个边的子集,使得每个顶点只与一条边关联 （ 图中粗线 ）,问题便得以解决了 。 这就是所谓匹配问题,下面给出一些基本概念和术语,假设 G是任一无向图 。 匹配 设 M是 E（ G） 的一个子集,如果 M中任二边在 G中均不邻接,则称 M是 G的一个匹配 。 M中一条边的两个端点,叫做在 M是配对的 。
第 10章 几种典型图饱和与非饱和 若匹配 M的某条边与顶点 v关联,则称 M饱和顶点 v,且称 v是 M― 饱和的 。 否则称 v是 M―
不饱和的 。
完美匹配 G中每一个顶点都是关于匹配 M饱和的 。
完全匹配 设二分图 G=〈 V1,,V2,E〉,M是 G中匹配,v∈ V1,v均是 M― 饱和的,则称 M是 V1对 V2的完全匹配 （ V1― 完全匹配 ） v∈ V2,v均是 M― 饱和的,则称 M是 V2对 V1的完全匹配 （ V2-完全匹配 ） 。
若 M既是 V1― 完全匹配,又是 V2― 完全匹配,则称 M是完全匹配 。
第 10章 几种典型图交互道 若 M是图 G的一个匹配,设从 G中的一个顶点到另一个顶点存在一条通路,这条通路由属于 M和不属于 M的边交替出现组成,则称此通路为交互道 。
如图 10.4.5（ a），实线边属于 M,x1y1x3y2x2y3x4y4
是一条由 x1到 y4的交互道。可增广道 若一交互道的两个端点均为 M― 不饱和点，则称其为可增广道。
显然,一条边的二端点非饱和,则这条边是可增广道 。
如图 10.4.5（ b），实线边属于 M,x2y1x1y2x4y4x5y5
是可增广道,x3y6也是可增广道。
第 10章 几种典型图图 10.4.5
x
1
x
2
x
3
x
4
y
4
y
3
y
2
y
1
( a )
x
1
x
2
x
3
x
4
x
5
y
5
y
4
y
3
y
2
y
1
y
6
( b )
第 10章 几种典型图性质 可增广道的长度必为奇数,且属于 M的边比不属于 M的边多 1条 。
对于可增广道，只要改变一下匹配关系，即只要将此道上虚、实边对换，得新的匹配 M′，则 M′中的边数比 M中的边数多 1条。如图 10.4.6（ b）中的可增广道按上述方法得新的交互道 x2y1x1y2x4y4x5y5，如图 10.4.5，
实边是匹配，中的边数由 M中的 3条增至 4条。用此方法可逐步得到较大的匹配。
第 10章 几种典型图图 10.4.6
x
1
x
2
x
3
x
4
x
5
y
5
y
4
y
3
y
2
y
1
y
6
第 10章 几种典型图定理 10.4.2 在图 G中,M为最大匹配的充分必要条件是不存在可增广道 。
证明 必要性用反证法立即可得 。
再证充分性 。 用反证法,假设 M不是最大匹配,则存在匹配 M1,使得 |M1|＞ |M|。 设由 M M1（
差运算 ） 导出的子图 G［ M M1］ 记为 H,它的每个分支或者是交错道,或者是交错回路 。
第 10章 几种典型图因为 M和 M1都是 G的匹配,H中每个顶点的度数至多为 2,于是每个分支中的每个顶点的度数至多为 2，
所以每个分支或者是回路,或者是路,且其上的边交错地属于 M和 M1。 由于 |M1|＞ |M|,因而 H中必有一条路,
它的起点和终点都是关于 M未饱和的,也一定是 G中关于 M未饱和的顶点,因此在 G中存在关于 M的可增广道,
这与假设矛盾 。
第 10章 几种典型图定理 10.4.3（ 霍尔定理 ） 二分图 G=〈 V1,V2,E〉
有 V1― 完全匹配,当且仅当对 V1中任一子集 A,和所有与 A邻接的点构成的点集 N（ A）,恒有
|N（ A） |≥|A|
证明 先证必要性 。 假设 V1中的每个顶点关于匹配
M均饱和,并设 A是 V1的子集,因 A的每个顶点在 M下和 N（ A） 中不同的顶点配对,所以有 |N（ A） |≥|A|。
第 10章 几种典型图再证充分性 。 假设 G是满足对任何 V1的子集 A,|N
（ A） |≥|A|的二分图,但 G中没有使 V1中每个顶点饱和的完全匹配,设 M1是 G的一个最大匹配,由假设,M1
不使 V1中所有顶点饱和 。 设 v是 V1中的 M1― 不饱和点,
并设 B是与 v有关于 M1交错道相连通的所有顶点的集合 。
由于 M1是一最大匹配,由定理 10.4.2可知,v为 B中唯一的 M1― 不饱和点 。
第 10章 几种典型图令 A=B∩V1,T=B∩V2,显然,A-{v}中的顶点都关于 M1饱和,即它与 T中的顶点在 M1下配对,于是
|T|=|A|-1
且 N（ A） T,又因 N（ A） 中的每个顶点有关于
M1交错路与 v相连通,因此 N（ A） =T所以
|N（ A） |=|A|-1＜ |A|
与假设 |N（ A） |≥|A|矛盾。证毕
第 10章 几种典型图图 10.4.7
x
1
x
2
x
3
x
4
y
5
y
4
y
3
y
2
y
1
第 10章 几种典型图
【 例 10.4.3】 设有 4个人 x1,x2,x3,x4，现有 5项工作 y1,y2,y3,y4,y5需要做，每个人所能胜任那几项工作的情况如图 10.4.7所示，问能否使每个人都能分配到一项工作？
解 这个问题即为：二分图 G=〈 V1,V2,E〉 是否存在 V1― 完全匹配。当取 A={x1,x3,x4}时,N（ A）
={y2,y5}，因此 |N（ A） |＜ |A|，根据霍尔定理，二分图没有 V1― 完全匹配，所以要使每个人都能分配到一项工作是不可能的。
第 10章 几种典型图
【 例 10.4.4】 证明 k― 正则二分图 （ k＞ 0） 有完全匹配 。
证明 设 G=〈 V1,V2,E〉 为 k― 正则二分图,则
k·|V1|=|E|=k·|V2| 即 |V1|=|V2|
A V1,设 E1是 A中顶点所关联的边的集合,E2是
N（ A） 中顶点所关联的边的集合,根据 N（ A） 的定义,
必有
| E1|≤|E2|
第 10章 几种典型图于是
k·|N（ A） |=|E2|=|E1|=k·|A
因此
|N（ A） |≥|A|
由霍尔定理知,G有 V1― 完全匹配 M,因为 |V1|=|V2|，
所以 M也是 V2― 完全匹配,即 G有完全匹配 。 证毕第 10章 几种典型图检查一个二分图是否满足相异条件有时是相当麻烦的,下面的定理给出了判断一个二分图 G=〈 V1,V2，
E〉 是否存在 V1― 完全匹配的充分条件,一般称为,t
条件,,这个条件比较容易检查,但它不是必要条件 。
第 10章 几种典型图定理 10.4.4 设 G=〈 V1,V2,E〉 是二分图,如果能找到一个正整数 t,使得对于 V1中的任何顶点 x有 d（ x）
≥t,并且对于 V2中的任何顶点 y有 d（ y） ≤t,则 G中有
V1― 完全匹配 。
证明 由条件知,V1中的每个顶点至少与 V2中的 t个顶点邻接,而 V2中的每个顶点至多与 V1中的 t个顶点邻接,因此,A V1,必有
|N（ A） |≥|A|
所以 G中有 V1― 完全匹配。证毕
第 10章 几种典型图
10.5 例题选解
【 例 10.5.1】 判断下列各命题是否是真命题 。
（ 1） 完全图 Kn（ n≥1） 都是欧拉图 。
（ 2） n（ n≥1） 阶有向完全图都是有向欧拉图 。
（ 3） 二分图 G=〈 V1,V2,E〉 必不是欧拉图 。
（ 4） 完全图 Kn（ n≥1） 都是哈密顿图 。
（ 5）完全二分图 Kr,s（ r≥1,s≥1）都是哈密顿图。
第 10章 几种典型图
（ 6） 存在哈密顿回路的有向图都是强连通图 。
（ 7） 若 G*是平面图 G的对偶图,则 G也是 G*的对偶图 。
（ 8） 完全二分图 Kr,s（ r≥1,s≥1） 都不是平面图 。
（ 9） n（ n≥5） 阶无向完全图都是非平面图 。
（ 10） n（ n≥2） 阶无向树都是二分图 。
第 10章 几种典型图解答与分析
（ 1） 假命题 。 完全图 Kn每个顶点的度数均是 n-1，
当 n是大于等于 2的偶数时,Kn的每个顶点的度数均为
n-1是奇数,故此时 Kn不是欧拉图 。
（ 2） 真命题 。 由定义知有向完全图 G必是连通图,
G的任意两个顶点间均有一对方向相反的边相连,即 G
的每个点的出度和入度均相等,因此必是有向欧拉图 。
第 10章 几种典型图
（ 3） 假命题 。 当 G是连通的二分图,且 |V1|,|V2|均为偶数时,G的每个顶点度数均是偶数,此时的 G是欧拉图 。
（ 4） 假命题 。 当 n=2时,K2中没有哈密顿回路,故并非完全图 Kn（ n≥1） 都是哈密顿图 。
（ 5） 假命题 。 当 r≠s时,Kr,s都不是哈密顿图 。 证：
不妨设 |V1|=r＜ s=|V2|,去掉 V1中所有顶点后得到的 Kr,s
的子图的连通分支数为 s,因此,
p（ G-V1） =s＞ |V1|,不满足哈密顿图的必要条件 。
第 10章 几种典型图
（ 6） 真命题 。 哈密顿回路是行遍图中每一个顶点的回路,因此,存在哈密顿回路的有向图都是强连通图 。
（ 7） 假命题 。 G是平面图,但不一定是连通图,而
G的对偶图 G*总是连通的,所以,当 G不连通时 G不是
G*的对偶图 。
（ 8） 假命题 。 完全二分图 Kr,s（ r≥1,s≥1） 当 r与 s
均大于等于 3时,因其中含有子图 K3,3必是非平面图,
但完全二分图 K1,1,K2,2,K2,3,K3,2都是平面图 。
第 10章 几种典型图
（ 9） 真命题 。 n（ n≥5） 阶无向完全图中均含有子图 K5,所以都是非平面图 。
(10)真命题 。 n（ n≥2） 阶无向树中无奇数长度的回路,因此均是二分图 。
第 10章 几种典型图
【 例 10.5.2】 有 11个学生计划几天都在一个圆桌上共进晚餐,并且希望每次晚餐时,每个学生两边邻座的人都不相同,按此要求,他们在一起共进晚餐最多几天？
分析 以 11个顶点表示人,边表示相邻而坐的二人,则任意一人与其他人相邻就座的所有情况,就是 11个顶点的完全图；一次晚餐的就座方式,就是 K11中的一个哈密顿圈；每次晚餐时,每个学生两边邻座的人都不相同,
就是在 K11中的每个哈密顿圈没有公共边,问题归结为在 K11中最多有多少个没有公共边的哈密顿圈 。
第 10章 几种典型图因为 11人的坐法只由他们之间的相邻关系决定,排成圆形时,仅与排列顺序有关 。 因此对各种做法,可认为一人的座位不变,将其设为 1号,并不妨放在圆心,
其余 10人放在圆周上 。 于是不同的哈密顿圈,可由圆周上不同编号的旋转而得到 。
解 11个顶点的完全图共有 11× (11-1)/2=55条边,
在 K11中每条哈密顿圈的长度为 11,则没有公共边的哈密顿圈数是 55/11=5条,即最多有 5天 。 此 5条不同的哈密顿圈可由下面方式作图得到：
第 10章 几种典型图设有一条哈密顿圈 1-2-3…11-1,将此图的顶点标号旋转 360° /10,2× 360° /10,3× 360° /10,
4× 360° /10,就得到另外四个图 （ 如图 10.5.1所示 ） 。
每个图对应一条哈密顿圈 。 如果 11个人标记为 1，
2,…,11,5天中排列情况如下：
第 10章 几种典型图图 10.5.1
6
4
2 3
5
7
9
1110
8
1
2
3
5 7
9
11
10
86
4
1
8
6
4 2
3
5
7
911
10
1
4
2
3 5
7
9
11
108
6
1
10
8
6 4
2
3
5
79
11
1
第 10章 几种典型图
1 2 3 4 5 6 7 8 9 1 0 1 1
1 4 2 6 3 8 5 1 0 7 1 1 9
1 6 4 8 2 1 0 3 1 1 5 9 7
1 8 6 1 0 4 1 1 2 9 3 7 5
1 1 0 8 1 1 6 9 4 7 2 5 3
第 10章 几种典型图
【 例 10.5.3】 证明：在由 6个结点和 12条边组成的连通简单平面图 G中,每个面的度数均为 3。
解 G是简单图,所以所有面的最小度 k=deg（ R）
≥3。 又由于 G连通,故
v-e+r=2 （ v,e,r分别为点数,边数和面数 ）
v=6,e=12,所以 r=8 。 由 握 手 定 理
2e=24=Σdeg（ R） ≥kr=8k,解得 k≤3。 因此,有 k=3,即
G的最小度等于 3。 不难证明,面的最大度 k′=3。 因为否则将有 3r＜ 2e,得出 24＜ 24的矛盾,故每个面的度数均为 3。
第 10章 几种典型图习 题 十
1.判别图 10.1中各图是否是欧拉图或半欧拉图,并说明理由 。
第 10章 几种典型图图 10.1
( a ) ( b ) ( c )
第 10章 几种典型图
2.构造简单欧拉图,使其顶点数 n和边数 m满足下列条件,
（ 1） n,m均为奇数 。
（ 2） n,m均为偶数 。
（ 3） n为奇数,m为偶数。
第 10章 几种典型图图 10.2
第 10章 几种典型图
3,(1)图 10.2中的边能剖分成两条路 （ 边不重合 ）,
试给出这样的剖分 。
(2)设 G是一个有 k个奇度数顶点的无向图,问最少加几条边到 G中去,能使所得图有一条欧拉回路,说明对图 9.2如何做到这一点 。
4.对于 σ=3,n=3,构造一个笛波滤恩序列,并画出 G3,3。
第 10章 几种典型图
5.构造简单无向图 G,使其满足下列条件：
（ 1） G是欧拉图,但不是哈密顿图 。
（ 2） G是哈密顿图,但不是欧拉图 。
（ 3） G既是欧拉图,同时也是哈密顿图 。
（ 4） G即不是欧拉图也不是哈密顿图 。
6.判别图 10.3中各图是否是哈密顿图或半哈密顿图，并说明理由。
第 10章 几种典型图图 10.3
( a ) ( b ) ( c )
第 10章 几种典型图
7.证明：若 G是半哈密顿图,则对于 V的任何子集 S
均有
P（ G-S） ≤|S|+1
8.设简单图 G=〈 V,E〉 且 |V|=n,|E|=m,若有
m≥C2n-2+2,则 G是哈密顿图 。
9.若 G是平面图,有 k个连通分支,证明,n-m+r=k+1。
10.证明图 10.1（ b） 不是平面图 。
11.证明图 10.3（ c） 不是平面图 。
第 10章 几种典型图
12.证明：小于 30条边的平面简单图中存在度数小于等于 4的顶点 。
13.若将平面分成 β个面,要求每两个面均相邻,
则 β最大为多少？
14.设 G是 n个顶点的简单连通平面图,n≥4。 已知
G中不含长度为 3的初级回路,证明 G中一定存在顶点 v，
d（ v） ≤3。
15.设 G是 11个顶点的无向简单图,证明 G或必为非平面图 。
16.设 G是简单平面图,面数 r＜ 12,δ（ G） ≥3,证明 G中存在次数小于或等于 4的面 。
第 10章 几种典型图
17.画出图 10.4中各图的对偶图。
图 10.4
( a ) ( b ) ( c )
第 10章 几种典型图
18.求出上题中对各图的面着色的最少色数 。
19.用韦尔奇 ·鲍威尔法对图 10.5中各图着色，求图的着色数。
20.假定 G是二分图,如何安排 G中顶点的次序可使
G的邻接矩阵呈 为矩阵,0为零矩阵 。
21.证明一个图能被两种颜色正常着色,当且仅当它不包含长度为奇数的回路 。
0
0
B
C
第 10章 几种典型图图 10.5
C
B
A
H G
F
E
D
1 2 3
6
4 5
7
9
11
12 13
10
8
( a ) ( b )
第 10章 几种典型图
22.今有工人甲,乙,丙,任务 a,b,c。 已知甲能胜任 a,b,c,乙能胜任 a,b,丙能胜任 b,c。 能给出几种不同的安排方案,使每个工人去完成他们能胜任的任务？
23.判断图 10.1,图 10.3,图 10.4中各图是否是二分图 。
24.某单位有 7个空缺 p1,p2,…,p7要招聘,有 10个应聘者 m1,m2,…,m10,他们适合的工作岗位集合分别为：
{p1,p5,p6},{p2,p6,p7},{p3,p4},{p1,p5},{p6，
p7},{p3},{p2,p3},{p1,p3},{p1},{p5}。 如何安排能使落聘者最少？
10.1 欧拉图
10.2 哈密顿图
10.3 平面图
10.4 二分图
10.5 例题选解习 题 十第 10章 几种典型图
10.1 欧 拉 图欧拉图的概念是瑞士数学家欧拉 （ LeonhardEuler）
在研究哥尼斯堡 （ K nigsberg） 七桥问题时形成的 。 在当时的哥尼斯堡城,有七座桥将普莱格尔 （ Pregel） 河中的两个小岛与河岸连接起来 （ 见图 10.1.1（ a））,
当时那里的居民热衷于一个难题：一个散步者从任何一处陆地出发,怎样才能走遍每座桥一次且仅一次,
最后回到出发点？
第 10章 几种典型图这个问题似乎不难,谁都想试着解决,但没有人成功 。 人们的失败使欧拉猜想：也许这样的解是不存在的,1936年他证明了自己的猜想 。
为了证明这个问题无解,欧拉用 A,B,C,D四个顶点代表陆地,用连接两个顶点的一条弧线代表相应的桥,从而得到一个由四个顶点,七条边组成的图
（ 见图 10.1.1（ b））,七桥问题便归结成：在图 10.1.1
（ b） 所示的图中,从任何一点出发每条边走一次且仅走一次的通路是否存在 。
第 10章 几种典型图欧拉指出,从某点出发再回到该点,那么中间经过的顶点总有进入该点的一条边和走出该点的一条边,
而且路的起点与终点重合,因此,如果满足条件的路存在,则图中每个顶点关联的边必为偶数 。 图 10.1.1
（ b） 中每个顶点关联的边均是奇数,故七桥问题无解 。
欧拉阐述七桥问题无解的论文通常被认为是图论这门数学学科的起源 。
第 10章 几种典型图图 10.1.1
B
C
( a )
A
D
A
B
D
C
( b )
第 10章 几种典型图
1.欧拉无向图定义 10.1.1 设 G=〈 V,E〉 是连通图,经过 G中每一条边一次且仅一次的通路 （ 起点,终点不重合 ） 称为欧拉通路 （ 欧拉开迹 ）,有欧拉通路的图称半欧拉图；
经过每一条边一次且仅一次的回路称为欧拉回路 （ 欧拉闭迹 ）,有欧拉回路的图称欧拉图 。 一条欧拉通路即为一条行遍图中每条边的简单通路 （ 迹 ）,亦即一笔画问题 。
第 10章 几种典型图定理 10.1.1 设 G是连通图,G是欧拉图当且仅当 G
的所有顶点均是偶度数点 。
证明 先证必要性 。
设 G中有欧拉回路,v0e1v1e2v2…eiviei+1…ekv0,其中顶点可重复出现,边不可重复出现 。 在序列中,每出现一个顶点 vi,它关联两条边,而 vi可以重复出现,所以 d（ vi） 为偶数 。
第 10章 几种典型图再证充分性 。
若图 G是连通的,则可以按下列步骤构造一条欧拉回路：
（ 1）从任一顶点 v0开始，取关联于 v0的边 e1到 v1，
因为所有顶点为偶度数点，且 G是连通的，所以可继续取关联于 v1的边 e2到 v2……每条边均是前面未取过的，直到回到顶点 v0，得一简单回路 l1,v0e1v1e2v2…eiviei+1…ekv0。
第 10章 几种典型图
（ 2） 若 l1行遍 G中所有的边,则 l1就是 G中欧拉回路,即 G为欧拉图,否则 G-l1=G1不是空集,G1中每个顶点均是偶度数点,又 G连通,G1与 l1必有一个顶点 vi
重合,在 G1中从 vi出发重复步骤 （ 1）,可得一简单回路 l2,vie′1u1e′2…vi。
（ 3） 若 l1∪ l2=G,则 G即为欧拉图,欧拉回路为
l1∪ l2,v0e1v1e2v2…eivie′1u1e′2…viei+1vi+1…ekv0,否则,重复步骤 （ 2）,直到构造一条行遍 G中所有边的回路为止,此回路即为欧拉回路,G是欧拉图 。
第 10章 几种典型图定理 10.1.2 设 G是连通图,则 G是半欧拉图当且仅当 G中有且仅有两个奇度数顶点 。
证明 证法类同定理 10.1.1。 只是步骤 （ 1） 从一个奇度数顶点 v0开始,取关联于 v0的边 e1到 v1……直到另一个奇度数顶点 vk为止,得一条简单通路 l1。 其他步骤与定理 10.1.1同 。 最后构造出一条行遍 G中所有边的简单通路,即为欧拉通路,G是半欧拉图 。
定理提供了判断欧拉图和半欧拉图的方法,由此易知,哥尼斯堡七桥问题无解 。
例如,图 10.1.2中 （ a） 是欧拉图,图 （ b） 是半欧拉图,图 （ c） 既非欧拉图也非半欧拉图 。
第 10章 几种典型图图 10.1.2
e
1 0
e
1
e
9
e
3
e
4
e
2
e
5
e
6
e
7
e
8
( a ) ( b ) ( c )
1
0
5 4
3
2
第 10章 几种典型图当给定了一个欧拉图后,如何找出它的一条欧拉回路？ 下面的 Fleury（ 于 1921年提出 ） 算法解决了这个问题,这个算法的实质是,避桥,。
设 G是欧拉图 。
（ 1） 任选 G的一个顶点 v0为起点,并设零条边的通路为 l0=v0。
（ 2） 设已选好的简单通路为 li=v0e1v1e2v2…eivi,则按下述方法从 E-{e1,e2,…,ei}中选取边 ei+1：
第 10章 几种典型图
① ei+1与 vi关联；
② 除非没有别的边可选择,否则 ei+1不是 Gi=G-
{e1,e2,…,ei}的割边 （ 桥 ） 。
（ 3） 当第 (2)步不能继续进行时 （ 所有的边已走遍 ）,算法终止 。
第 10章 几种典型图
【 例 10.1.1】 找出图 10.1.2（ a） 所示图 G的一条欧拉回路 。
解 从 v0出发,先找到 l3=v0e1v1e2v4e3v6,因为此时在
G3=G-{e1,e2,e3}中,关联 v6的边 e9和 e10均是割边,所以只能选取 e4,继续下去,最后可得一条欧拉回路：
l=v0e1v1e2v4e3v5e4v2e5v4e6v3e7v2e8v1e9v5e10v0
第 10章 几种典型图最后介绍一下,中国邮递员问题,（ the Chinese
Postman Problem）。我国数学家管梅谷于 1962年首先提出这个问题，并得到一些结果，得到世界同行们的承认。该问题是说：邮递员从邮局出发在他的管辖区域内投递邮件，然后回到邮局。自然，他必须走过他所辖区域内的每一条街道至少一次。在此前提下，希望找到一条尽可能短的路线。
第 10章 几种典型图设 G=〈 V,E,w〉 是一带权图,l是 G的一条回路,
称 为 l的权 。 中国邮递员问题就是在带非负权的连通图中找到一条权最小的行遍所有边的回路,
称此回路为最佳周游 。
若 G是欧拉图,则 G中的任何一条欧拉回路均是最佳周游,而寻找欧拉回路的 Fleury算法为解决这一问题提供了切实可行的方法 。 对于非欧拉图,也有相应的算法,限于篇幅不再介绍 。
()
i
i
el
e?
第 10章 几种典型图
2.欧拉有向图定义 10.1.2 设 G是连通有向图,若 G中有经过所有边一次且仅一次的有向通路 （ 起点,终点不重合 ）,
则称为有向欧拉通路,具有有向欧拉通路的图称为半欧拉有向图；若 G中有经过所有边一次且仅一次的有向回路,则称为有向欧拉回路,具有有向欧拉回路的图称为欧拉有向图 。
显然,如果 G是欧拉有向图,则 G必是强连通图 。
第 10章 几种典型图类似于定理 10.1.1,10.1.2,可得下面定理：
定理 10.1.3 设 G是连通有向图,则 G是欧拉有向图当且仅当 G中的每个顶点 v均有 d+（ v） =d-（ v） 。
定理 10.1.4 设 G是连通有向图,则 G是半欧拉有向图当且仅当 G中恰有两个奇度数顶点,其中一个入度比出度大 1,另一个出度比入度大 1,而其他顶点的出度等于入度 。
例如,图 10.1.3中 （ a） 是欧拉有向图,图 （ b） 是半欧拉有向图,图 （ c） 既非欧拉有向图也非半欧拉有向图 。
第 10章 几种典型图图 10.1.3
( a ) ( b ) ( c )
第 10章 几种典型图
【 例 10.1.2】 计算机鼓轮设计问题,
设计旋转鼓轮,要将鼓轮表面分成 16个扇区,如图 10.1.4（ a） 所示,每块扇区用导体 （ 阴影区 ） 或绝缘体 （ 空白区 ） 制成,如图 10.1.4（ b） 所示,四个触点 a,b,c和 d与扇区接触时,接触导体输出 1,接触绝缘体输出 0。 鼓轮顺时针旋转,触点每转过一个扇区就输出一个二进制信号 。 问鼓轮上的 16个扇区应如何安排导体或绝缘体,使得鼓轮旋转一周,触点输出一组不同的二进制信号？
第 10章 几种典型图显然，图 10.1.4（ b）所示，旋转时得到的信号依次为 0010,1001,0100,0010,…，在这里,0010出现了两次，所以这个鼓轮是不符合设计要求的。按照题目要求，鼓轮的 16个位置与触点输出的 16个四位二进制信号应该一一对应，亦即 16个二进制数排成一个循环序列，使每四位接连数字所组成的 16个四位二进制子序列均不相同。这个循环序列通常称为笛波滤恩
（ DeBruijn）序列。如图 10.1.4（ c）所示,16个扇区所对应的二进制循环序列正是笛波滤恩序列。
第 10章 几种典型图图 10.1.4
( a ) ( b )
a
b
c
d
( c )
a
b
c
d
第 10章 几种典型图图 10.1.5
0 0 1 1 0 0
0 0 0
0 1 1 1 1 0
1 0 1
0 1 0
1 1 1
e
1 5
＝ 1 1 1 1
e
1 4
＝ 1 1 1 0
e
6
＝ 0 1 0 1
e
7
＝ 0 1 1 1
e
1 1
＝ 1 0 1 1 e
1 3
＝ 1 1 0 1
e
1 2
＝ 1 1 0 0
e
1 0
＝ 1 0 1 0e
5
＝ 0 1 0 1e
3
＝ 0 0 1 1
e
2
＝ 0 0 1 0 e
4
＝ 0 1 0 0
e
1
＝ 0 0 0 1 e
8
＝ 1 0 0 0
e
9
＝ 1 0 0 1
e
0
＝ 0 0 0 0
第 10章 几种典型图
10.2 哈密顿图哈密顿图的概念源于 1859年爱尔兰数学家威廉 ·哈密顿爵士（ SirWillianHamilton）提出的一个,周游世界,的游戏。这个游戏把一个正十二面体的二十个顶点看成是地球上的二十个城市，棱线看成连接城市的道路，要求游戏者沿着棱线走，寻找一条经过所有顶点（即城市）一次且仅一次的回路，如图 10.2.1（ a）
所示。也就是在图 10.2.1（ b）中找一条包含所有顶点的初级回路，图中的粗线所构成的回路就是这个问题的回答。
第 10章 几种典型图图 10.2.1
( a ) ( b )
第 10章 几种典型图定义 10.2.1 若图 G中有一条经过所有顶点一次且仅一次的回路,则称该回路为哈密顿回路,称 G为哈密顿图；若图 G中有一条经过所有顶点一次且仅一次的通路,
则称此通路为哈密顿通路,称 G为半哈密顿图 。
乍一看,哈密顿图与欧拉图有某种对偶性 （ 点与边的对偶性 ）,但实际上,前者的存在性问题比后者难得多 。 迄今为止,寻找到一个判断哈密顿图的切实可用的充分必要条件仍是图论中尚未解决的主要问题之一 。 人们只是分别给出了一些必要条件和充分条件 。
第 10章 几种典型图定理 10.2.1 若 G是哈密顿图,则对于顶点集 V的每一个非空子集 S,均成立
P（ G-S） ≤|S|
其中,P（ G-S） 是 G-S的连通分支数,|S|是 S中顶点的个数 。
第 10章 几种典型图证明 设 C是图 G中的一条哈密顿回路,S是 V的任
a1∈ S,C-{a1}是一条初级通路，若再删去 a2∈ S，则当 a1,a2邻接时,P（ C-{a1,a2}） =1＜
2；而当 a1,a2不邻接时,P（ C-{a1,a2}） =2，即
P（ C-{a1,a2}） ≤2=|{a1,a2}|
如此做下去,归纳可证
P（ C-S） ≤|S|
因为 C-S是 G-S的生成子图，所以
P（ G-S） ≤P（ C-S） ≤|S|。
第 10章 几种典型图图 10.2.2
第 10章 几种典型图这个定理给出的只是一个无向图是哈密顿图的必要条件,亦即哈密顿图必满足这个条件,满足这个条件的不一定是哈密顿图 。
例如,著名的彼得森 （ Petersen） 图 （ 如图 10.2.2所示 ） 不是哈密顿图,但对任意的 S V,S≠,均满足
P(C-S)≤|S|
然而,不满足这个条件的必定不是哈密顿图 。
第 10章 几种典型图
【 例 10.2.1】 含有割点的图必定不是哈密顿图 。
证明 设 v是图 G中的割点,则
P（ G-v） ≥2＞ |{v}|
因此,图 G不是哈密顿图 。
下面介绍无向图中有哈密顿通路的充分条件 。
第 10章 几种典型图定理 10.2.2 若 G是 n（ n≥3） 个顶点的简单图,对于每一对不相邻的顶点 u,v,满足
d（ u） +d（ v） ≥n-1
则 G中存在一条哈密顿通路 。
证明 首先证明 G是连通图。假设 G非连通，则 G至少有两个连通分支 G1,G2，设 G1中有 n1个顶点,G2中有 n2 v1(V（ G1 v2(V（ G2），因为 d
（ v1） ≤n1-1,d（ v2） ≤n2-1，故 d（ v1） +d（ v2） ≤n1+n2-
2＜ n-1，这与题设条件矛盾，因此,G必连通。
第 10章 几种典型图其次,再证 G中含有哈密顿通路 。 设?是 G中任意一条有 m-1条边的初级通路,v1v2…vm若 m=n,则 l就是 G中的一条哈密顿通路；若 m〈 n,我们来扩充此路 。
（ 1） 如果通路的两个端点 v1,vm还与路?之外的顶点邻接,则延伸此通路 。
（ 2） 如果 v1,vm均只与原通路?上的顶点邻接,如下可证,G中有一条包含 l的长度为 m的回路 。
若 v1与 vm邻接,则 v1v2…vmv1即所求之回路 。
若 v1与 vi1,vi2…,vip邻接,1＜ i1,i2,…,ip＜ m，
考虑 vm：
第 10章 几种典型图图 10.2.3
( a )
( b )
( c )
1 2 i － 1
1 1
i
m
m
m
1
i
1
1
k － 1
k － 1
k
k
k ＋ 1
k ＋ 1
i － 1
1
第 10章 几种典型图重复过程 （ 1）,（ 2）,不断扩充通路 l,直至它的长度为 n-1,这时便得到 G中的一条哈密顿通路 。 证毕仿此可证：
定理 10.2.3 若 G是 n（ n≥3） 个顶点的简单图,对于每一对不相邻的顶点 u,v,满足
d（ u） +d（ v） ≥n
则 G中存在一条哈密顿回路 。 即 G是哈密顿图 。
推论 1 设 G是 n（ n≥3） 阶无向简单图,若 δ（ G）
≥n/2,则 G是哈密顿图 。
推论 2 完全图 Kn（ n≥3） 均是哈密顿图 。
第 10章 几种典型图
【 例 10.2.2】 设 n≥2,有 2n个人参加宴会,每个人至少认识其中的 n个人,怎样安排座位,使大家围坐在一起时,每个人的两旁坐着的均是与他相识的人？
解 每个人用一个顶点表示，若二人相识，则在其所表的顶点间连边。这样得到一个 2n阶的无向图，因为 δ（ G） ≥n u,v∈ V（ G）,d（ u） +d（ v）
≥2n，故图中存在一条哈密顿回路，这条回路恰好对应一个座位的适当安排。
第 10章 几种典型图定理 10.2.4 当 n为不小于 3的奇数时,Kn上恰有 (n-
1)/2条互无任何公共边的哈密顿回路 。
证明 假设 Kn的 n个顶点如图 10.2.4所示排成一个正
（ n-1） 边形 （ 因为 n是奇数,这是可行的 ）,并给出了一条哈密顿回路,v1v2…vnv1。
第 10章 几种典型图图 10.2.4
n
1
4
5
3
2
n － 2
n － 1
n － 3
第 10章 几种典型图顺时针分别旋转（旋转时顶点的标记不动）
3
3603 6 0 2 3 6 0
2,,,
1 1 1
n
n n n
如图 10.2.4所示 。
每旋转一次便产生一条哈密顿回路,且它们之间没有公共边 。 图 10.2.5演示了 n=5时的情景 (图 （ b） 是图 （ a）
旋转 90° 后所得 ),因此,合乎要求的哈密顿回路共有 1+
(n-3)/2=(n-1)/2条 。
第 10章 几种典型图图 10.2.5
( a ) ( b )
4
52
1
3
4
2
1
5
3
第 10章 几种典型图货郎担问题与哈密顿图密切相关的是货郎担问题 。
设有 n个村镇,已知每两个村镇之间的距离 。 一个货郎自某个村镇出发巡回售货,问这个货郎应该如何选择路线,使每个村镇经过一次且仅一次,并且总的行程最短 。 即在一个带权完全图中,找一个权最小的哈密顿图 。
第 10章 几种典型图在 n个顶点的带权完全图中,所有不同的哈密顿回路 （ 包括有公共边的情况 ） 总数是 1/2 (n-1)！ 个 。 在如此众多的哈密顿回路中求一个总的权为最小的哈密顿回路,它的工作量是相当大的,这种求最优解的有效率的算法至今尚未找到 。 下面我们给出一个较好的近似算法 ——最邻近算法 。
设 G=〈 V,E,w〉 是 n个顶点的带权完全图,w是从 E
到正整数集 Z+的函数,对 V中的任何三个顶点 vi,vj，
vk w(vi,vj） +w（ vj,vk） ≥w（ vi,vk）
求最小权的哈密顿回路的最邻近算法步骤如下：
第 10章 几种典型图
（ 1） 任选一点 v0作起点,找一个与 v0最近的相邻顶点 vx,得到一条一边构成的路径 。
（ 2） 设 vx是新加到这条路中的一点,从不在此路中的所有顶点中,选一个与 vx最近的相邻点,将它与 vx连成一边,构成一条新的路径 。 重复过程 （ 2）,直到 G
中所有顶点都在所构成的路径中 。
（ 3） 连接 v0和最后加到路中的顶点,构成一条回路,
它就是带权的哈密顿回路 。
第 10章 几种典型图
【 例 10.2.3】 图 10.2.6（ a） 是一带权无向完全图,
用最邻近法求一条最短哈密顿回路 。
解 算法步骤按图 10.2.6（ b）,（ c）,（ d）,
（ e）,（ f） 的粗线边依次给出,图 （ f） 即所求之带权哈密顿回路,权为 47。
表面上看,最邻近算法,是很合理的,其实不然 。
例如图 10.2.6（ a） 的最短哈密顿回路应该是图 10.2.6
（ g） 所示,它的权为 35,这表明,最邻近算法,可能产生误差 。
第 10章 几种典型图图 10.2.6
5
4
9
8
9
( g )
4
7
8
16
( e )
4
12
7
8
16
( f )
a
b
c d
e
5 5
4
12
9
7
8
8
16
9
( a )
4
( b )
4
7
( c )
4
7
8
( d )
第 10章 几种典型图
10.3 平 面 图定义 10.3.1 若一个图能画在平面上使它的边互不相交 （ 除在顶点处 ）,则称该图为平面图,或称该图能嵌入平面 。
例如图 10.3.1（ a） 是平面图 G,它能嵌入平面上,
如图 10.3.1（ b） 所示 G1,G1是 G的平面嵌入 。
第 10章 几种典型图图 10.3.1
( a ) ( b )
第 10章 几种典型图并非所有的图都能嵌入平面，图 10.3.2（ a）表示的就是非平面图，这个图对应于一个有名的问题 ——公用事业问题。设有三座房子 a,b,c和三个公共设施 d、
e,f，能否使每座房子与每个公共设施之间均有道路连接而无交叉。实践证明这是做不到的，如图 10.3.2（ b）
说明（ a）无法嵌入平面，此图为二分图 K3,3，它是一个非平面图。还有一个重要的非平面图，如图 10.3.2
（ c）、（ d）所示，它就是完全图 K5。 K3,3和 K5又称为库拉托斯基图，它们是波兰数学家库拉托斯基
（ Kuratowsky）发现的典型的非平面图。
第 10章 几种典型图图 10.3.2
( a ) ( b )
a b c
d e f
( c ) ( d )
c d c d
b e
a
a b c
d e f
a
b e
第 10章 几种典型图定义 10.3.2 平面图 G嵌入平面后将平面划分成若干个连通的区域,每一个区域称为 G的一个面,其中面积无限的区域称为外部面或无限面 （ 常记为 R0）,面积有限的称为内部面或有限面,记作 Ri（ i=1,2,…,n）,
包围每个面的所有边所构成的回路称该面的边界,边界的长度称该面的次数,面 Ri的次数记作 deg（ Ri） 。
例如,图 10.3.1（ b） 共有六个面,每个面的次数均为 3。 图 10.3.3所示平面图 G有四个面,deg（ R1） =3，
deg（ R2） =3,deg（ R3） =5,deg（ R0） =9。
第 10章 几种典型图图 10.3.3
R
2
R
1
R
0
R
3
第 10章 几种典型图定义 10.3.3 设 G为一个简单平面图,如果在 G的任意两个不相邻的顶点间再加一条边,所得图为非平面图,则称 G为极大平面图 。
例如,完全图 Kn当 n≤4是都是极大平面图 。 K5在任意删去一条边后,为极大平面图 。 极大平面图有如下的一些性质：
（ 1） 极大平面图均是连通图 。
（ 2） 极大平面图中 （ n≥3）,不含割点和桥 。
第 10章 几种典型图
（ 3）任何 n（ n≥3）阶极大平面图，每个面（包括无限面）的次数均为 3，反之亦然。
（ 4） 最小 （ 含顶点数最少 ） 的极大平面图是 K5。
定义 10.3.4 设 G是非平面图,若在 G中任意删去一条边后,所得图为平面图,则称 G是极小非平面图 。
例如 K5和 K3,3均是极小非平面图 。
定理 10.3.1 在一个平面图 G中,所有面的次数之和为边数的二倍,即
1
de g ( ) 2
r
i
i
Rm
其中,r为 G的面数,m为边数。
第 10章 几种典型图证明 对于 G中的每一条边 e,e或是两个面的公共边,
或是在一个面中为悬挂边被作为边界计算两次,故定理成立 。 证毕定理 10.3.2 设连通平面图 G有 n个顶点,m条边和 r个面,则
n-m+r=2 ——Euler公式证明 施归纳于 G的边数 m。
m=0时,G为平凡图,n=1,r=1,公式成立 。
第 10章 几种典型图设 m=k-1（ k≥1） 时公式成立,现在考虑 m=k时的情况 。 因为在连通图上增加一条边仍为连通图,则有三种情况：
（ 1） 所增边为悬挂边,此时 G的面数不变,顶点数增 1,公式成立 。
（ 2） 在图的任意两个不相邻点间增加一条边,此时 G的面数增 1,边数增 1,但顶点数不变,公式成立 。
（ 3） 所增边为一个环,此时 G的面数增 1,边数增 1，
但顶点数不变,公式成立 。
第 10章 几种典型图定理 10.3.3 设 G是连通的（ n,m）平面图且每个面的次数至少为 l（ l≥3），则
( 2)2lmnl
证明 由定理 10.3.1知
1
2 de g ( )
r
i
i
m R l r
(r为 G的面数 )
再由 Euler公式
n-m+r=2
第 10章 几种典型图于是有
( 2)2lmnl
22 mr m n
l
故第 10章 几种典型图推论 1 设 G是 （ n,m） 连通平面简单图 （ n≥3）,
则
m≤3n-6。
证明 由于 G是 n≥3的连通平面简单图,所以 G的每个面至少由 3条边围成,即 l≤3,代入定理 10.3.3,得
m≤3n-6 证毕第 10章 几种典型图推论 2 极大连通平面图的边数 m=3n-6。
证明 因为极大平面图的每一个面的次数均是 3,所以 3r=2m,代入 Euler公式有
m=3n-6 证毕推论 3 若连通平面简单图 G不以 K3为子图，则
m≤2n-4。
证明 由于 G中不含 K3,所以 G的每个面至少由 4条边围成,即 l≤4,代入定理 10.3.3,得
m≤2n-4 证毕第 10章 几种典型图推论 4 K5和 K3,3是非平面图 。
证明 假设 K5是平面图,由推论 1可知应有 m≤3n-6，
而当 n=5,m=10时,这是不可能的,所以 K5是非平面图 。
假设 K3,3是平面图,因其不含子图 K3,由推论 2可知,
当 n=6,m=9时,m≤2n-4是不可能的,所以 K3,3是非平面图 。 证毕第 10章 几种典型图定理 10.3.4 在平面简单图 G中至少有一个顶点 v0，
d（ v0） ≤5。
证明 不妨设 G是连通的,否则就其一个连通分支讨论再推广至全图 。 用反证法证明 。
假设一个平面简单图的所有顶点度数均大于 5,又由欧拉公式推论 1知 3n-6≥m,所以
6 1 2 2 ( ) 6
V
n m d n
这是不可能的 。 因此平面简单图中至少有一个顶点 v0，其度数 d（ v0） ≤5。
证毕第 10章 几种典型图找出一个图是平面图的充分必要条件的研究曾经持续了几十年,直到 1930年库拉托斯基给出了平面图的一个非常简洁的特征,先介绍一些预备知识 。
在一个无向图 G的边上,插入一个新的度数为 2的顶点,使一条边分成两条边,或者对于关联同一个度数为 2的顶点的两条边,去掉这个 2度顶点,使两条边变成一条边,如图 10.3.4（ a）,（ b） 所示,这些都不会改变图原有的平面性,如图 10.3.4（ c）,（ d） 所示 。
图 10.3.4所表示的称为,图的同胚,。
第 10章 几种典型图图 10.3.4
( d )( c )( b )( a )
第 10章 几种典型图定义 10.3.5 如果两个图 G1和 G2同构,或者通过反复插入或删除度数为 2的顶点后同构,则称 G1和 G2同胚 。
由于同胚的两个图具有相同的平面性,而 K5和 K3,3
是典型的非平面图,因此有：
定理 10.3.5（ Kuratowsky定理 ） 一个图是平面图的充分必要条件是它不含与 K5或 K3,3同胚的子图 。 证明略 。
第 10章 几种典型图
【 例 10.3.1】 证明图 10.3.5中的 （ a） 和 （ d） 不是平面图 。
解 图 (a）是著名的彼得森（ Pertersen）图，去掉其中的两条边后得子图（ b），该子图同胚于 K3,3
（ c）。因此彼得森图不是平面图。图（ d）图中含有子图（ e），图（ e）图同构于 K3,3 （ f）。
库拉托斯基定理虽然简单漂亮,但实现起来并不容易,特别是顶点数较多的时候,还有许多这方面的研究工作要做 。
第 10章 几种典型图图 10.3.5
a
f
g j
h i
b e
c d
a
f
g j
h i
b e
c d
( a ) ( b )
a h i
j
d
efb
g
c
( c )
( f )
1 2
5 6
( e )( d )
3 4
1 2
5 6
3 4
1
2 5
6
3
4
第 10章 几种典型图
1.对偶图平面图有一个很重要的特性,任何平面图都有一个与之对应的平面图,称为它的对偶图 。 下面提到的平面图均以它的平面嵌入表示 。
定义 10.3.6 设平面图 G=〈 V,E〉 有 r个面 R1,R2,…，
Rr,则用下面方法构造的图 G*=〈 V*,E*〉 称为 G的对偶图：
（ 1 Ri∈ G，在 Ri内取一顶点 v*i∈ V*,i=1，
2,…,r。
（ 2 e∈ E。
第 10章 几种典型图
① 若 e是 G中两个不同面 Ri和 Rj的公共边,则在 G*中画一条与 e交叉的边 （ v*i,v*j） ；
② 若 e是一个面 Ri内的边 （ 即 Ri是桥 ）,则在 G*中画一条与 e交叉的环 （ v*i,v*i） 。
例如,图 10.3.6（ a） 和 （ b） 中,G*是 G的对偶图,
G的边用实线表示,G*的边用虚线表示,顶点用实心点表示 。
第 10章 几种典型图图 10.3.6
( a ) ( b )
第 10章 几种典型图定义 10.3.7 若平面图 G与其对偶图 G*同构,则称 G
是自对偶图 。
例如,图 10.3.6（ b） 实线图所示的 4阶 3度正则图就是一个自对偶图 。
定理 10.3.6 设 G*是连通平面图 G的对偶图,n*，
m*,r*和 n,m,r分别是 G*和 G的顶点数，边数和面数，
则 n*=r,m*=m,r*=n，且 d（ v*i） =deg（ Ri）,i=1，
2,…,r。
第 10章 几种典型图证明 由定义 10.3.6对偶图的构造过程可知,n*=r，
m*=m和 d（ vi） =deg（ Ri） 显然成立,下证 r*=n。 因为
G和 G*均是连通的平面图,所以由欧拉公式有
n-m+r=2
n*-m*+r*=2
由 n*=r,m*=m可得 r*=n。 证毕由于平面图 G的对偶图 G*也是平面图,因此同样可对 G*求对偶图,记作 G**,如果 G是连通的,则 G**
与 G之间有如下关系 。
第 10章 几种典型图定理 10.3.7 G是连通平面图当且仅当 G**同构于 G。
证明略 。
由对偶图的构造过程可知,平面图 G的任何两个对偶图必同构 。 但是若平面图 G1和 G2是同构的,其对偶图 G*1和 G*2未必同构 。 如图 10.3.7中两个平面图 G1和 G2
是同构的,但由于 G1（ 如图 10.3.7（ a） 所示 ） 中有一个面次数为 5,而 G2（ 如图 10.3.7（ b） 所示 ） 中没有这样的面,因此 G1和 G2不会同构 。
第 10章 几种典型图图 10.3.7
a
b c
de
f
G
1
G
2
b
a
c
d
e
f
( a ) ( b )
第 10章 几种典型图
2.着色问题在地图上,相邻国家涂不同的颜色,最少需要多少种颜色？ 100多年前,有人提出了,四色猜想,,即只用四种颜色就能做到,但一直无法证明,直到 1976
年美国数学家才用电子计算机证明了这一猜想 。
地图着色自然是对平面图的面着色,利用对偶图,
可将其转化为相对简单的顶点着色问题,即对图中相邻的顶点涂不同的颜色 。
第 10章 几种典型图定义 10.3.8 设 G是一个无自环的图,给 G的每个顶点指定一种颜色,使相邻顶点颜色不同,称为对 G的一个正常着色 。 图 G的顶点可用 k种颜色正常着色,称 G
是 k― 可着色的 。
使 G是 k― 可着色的数 k的最小值称为 G的色数,记作 χ（ G） 。 如果 χ（ G） =k,则称 G是 k― 色的 。
第 10章 几种典型图设 G无自环且连通,如果有多重边,则可删去多重边,用一条边代替,因此下面考虑的都是连通简单图 。
有几类图的色数是很容易确定的,即：
定理 10.3.8
（ 1） G是零图当且仅当 χ（ G） =1。
（ 2）对于完全图 Kn，有 χ（ Kn） =n，而 χ（ ） =1。
（ 3） 对于 n个顶点构成的回路 Cn,当 n为偶数时,χ
（ Cn） =2；当 n为奇数时,χ（ Cn） =3。
（ 4） 对于顶点数大于 1的树 T,有 χ（ T） =2。
nK
第 10章 几种典型图到现在还没有一个简单的方法可以确定任一图 G是
n― 色的 。 但韦尔奇 ·鲍威尔 （ WelchPowell） 给出了一种对图的着色方法,步骤如下：
（ 1） 将图 G中的顶点按度数递减次序排列 。
（ 2） 用第一种颜色对第一顶点着色,并将与已着色顶点不邻接的顶点也着第一种颜色 。
（ 3）按排列次序用第二种颜色对未着色的顶点重复（ 2）。用第三种颜色继续以上做法，直到所有的顶点均着上色为止。
第 10章 几种典型图图 10.3.8
a
g
h
f
d
c
b
e
第 10章 几种典型图
【 例 10.3.2】 用韦尔奇 ·鲍威尔法对图 10.3.8中的图着色 。
（ 1） 各顶点按度数递减次序排列,c,a,e,f,b,h,g,d。
（ 2） 对 c和与 c不邻接的 e,b着第一种颜色 。
（ 3） 对 a和与 a不邻接的 g,d着第二种颜色 。
（ 4） 对 f和与 f不邻接的 h着第三种颜色 。
第 10章 几种典型图定理 10.3.9 如果图 G的顶点的度数最大的为 Δ
（ G）,则 χ（ G） ≤1+Δ（ G） 。
证明 施归纳于 G的顶点度数 。
当 n=2时,G有一条边,Δ（ G） =1,G是 2― 可着色的,所以 χ（ G） ≤1+Δ（ G） 。 假设对于 n-1个顶点的图,结论成立 。
第 10章 几种典型图现假设 G有 n个顶点,顶点的最大度数为 Δ（ G）,
如果删去任一顶点 v及其关联的边,得到 n-1个顶点的图,它的最大度数至多是 Δ（ G）,由归纳假设,该图是 1+Δ（ G） ― 可着色的,再将 v及其关联的边加到该图上,使其还原成图 G,顶点 v的度数至多是 Δ（ G）,
v的相邻点最多着上 Δ（ G） 种颜色,然后 v着上第 1+Δ
（ G） 种颜色,因此 G是 1+Δ（ G） ― 可着色的,故
χ（ G） ≤1+Δ（ G） 。 证毕第 10章 几种典型图定理 10.3.8所给出的色数的上界是很弱的，例如树
T,χ（ T） =2，而 Δ（ T）可以很大。布鲁克斯（ Brooks）
在 1941年证明了这样的结果，使
χ（ G） =1+Δ（ G）的图只有两类：或是奇回路，或是完全图。
定理 10.3.10 任何平面图是 5― 可着色的 。
证明 不妨设 G是简单平面图 。 施归纳于 G的顶点数 n。 当 n≤5时结论显然成立 。
第 10章 几种典型图假设对所有 n-1个顶点的平面图是 5― 可着色的。
现考虑有 n个顶点的平面图 G，由定理 10.3.4可知，在 G
中存在着顶点 v0,d（ v0） ≤5。由归纳假设,G-v0是 5-可着色的，在给定了 G-v0的一种着色后，将 v0及其关联的边加到原图中，得到 G，分两种情况考虑：
第 10章 几种典型图
（ 1） 如果 d（ v0） ＜ 5,则 v0的相邻点已着上的颜色小于等于 4种,所以 v0可以着另一种颜色,是 G是 5― 可着色的 。
（ 2） 如果 d（ v0） =5,则将 v0的邻接点依次记为 v1，
v2,…,v5,并且对应 vi着第 i色,如图 10.3.9（ a） 所示 。
第 10章 几种典型图图 10.3.9
1
2
34
5
4
3
1
1
3
1
3
1
5 2
( a ) ( b )
1
2
0
34
5
2
0
34
5
1
第 10章 几种典型图设 H13为 G-v0的一个子图,它是由着色 1和 3的顶点集导出的子图 。 如果 v1和 v3属于 H13的不同分支,将 v1所在分支中着色 1的顶点与着色 3的顶点颜色对换,这时
v1着色 3,这并不影响 G-v0的正常着色 。 然后将 v0着色 1，
因此 G是 5― 可着色的 。
第 10章 几种典型图如果 v1和 v3属于 H13的同一分支,则在 G中存在一条从 v1到 v3的路,它的所有顶点着色 1或 3。 这条路与路
v1v0v3一起构成一条回路,如图 10.3.9（ b） 所示 。 它或者把 v2围在它里面,或者同时把 v4和 v5围在它里面 。 由于 G是平面图,在上面任一种情况下,都不存在连接 v2
和 v4并且顶点着色 2或 4的一条路 。
第 10章 几种典型图现在设 H24为 G-v0的另一个子图,它是由着色 2和 4的顶点导出的子图,则 v2和 v4属于 H24的不同分支 。 于是在 v2
所在分支中将着色 2的顶点和着色 4的顶点颜色对换,
v2着色 4,这样导出了 G-v0的另一种正常着色,然后在
v0着色 2,同样可得 G是 5― 可着色的 。
第 10章 几种典型图
10.4 二 分 图定义 10.4.1 若无向图 G=〈 V,E〉 的顶点集 V能分成两个子集 V1和 V2,满足
（ 1） V=V1∪ V2,V1∩V2= ；
（ 2） e=（ u,v） ∈ E,均有 u∈ V1,v∈ V2。
则称 G为二分图,V1和 V2称为互补顶点子集,常记为 G=〈 V1,V2,E〉 。 如果 V1中每个顶点都与 V2中所有顶点邻接,则称 G为完全二分图,并记为 Kr,s,其中
r=|V1|,s=|V2|。
第 10章 几种典型图例如,图 10.4.1中的三个图均是二分图,其中图 （ b）
是完全二分图 K3,3,图 （ c） 是 K2,4。
显然,在完全二分图中 Kr,s中,顶点数 n=r+s,边数 m=rs。
一个无向图如果能画成上面的样式,很容易判定它是二分图 。 有些图虽然表面上不是上面的样式,但经过改画就能成为上面的样式,仍可判定它是一个二分图,如图 10.4.2中 （ a） 可改画成图 （ b）,图 （ c）
可改画成图 （ d） 。 可以看出,它们仍是二分图 。
第 10章 几种典型图图 10.4.1
( a ) ( b ) ( c )
第 10章 几种典型图图 10.4.2
( c ) ( d )( b )( a )
a b c
d e f
a c e
b d f
1 2
3
45
6
1 3 5
2 4 6
第 10章 几种典型图定理 10.4.1 非平凡无向图 G是二分图当且仅当 G中无奇数长度的回路 。
证明 先证必要性 。 设 G=〈 V1,V2,E〉 为二分图,
对 G中任一长度为 k的回路 c,vi1vi2…vikvi1,不妨假设
vi1∈ V1,则必有 vi2∈ V2,vi3∈ V1,…,即下标为奇数的顶点属于 V1,下标为偶数的顶点属于 V2,因为 （ vik，
vi1） ∈ c,所以 k为偶数 。 因此,G中任一回路的长度为偶数 。
第 10章 几种典型图再证充分性 。 设 G中无奇数长度的回路,不妨设 G
是连通图,将 G的顶点集 V按下面要求分成两个子集 V1
和 V2：
V1={vi|vi∈ V且 vi与某一给定顶点 v0的距离是偶数 }，
V2=V1-V2
第 10章 几种典型图
【 例 10.4.1】 六名间谍 a,b,c,d,e,f被擒,已知 a懂汉语,法语和日语,b懂德语,俄语和日语,c懂英语和法语,d懂西班牙语,e懂英语和德语,f懂俄语和西班牙语,问至少用几个房间监禁他们,能使在一个房间里的人不能直接对话 。
解 以六人 a,b,c,d,e,f为顶点,在有共同懂得语言的人的顶点间连边得图 G（ 如图 10.4.3（ a） 所示 ）,因为 G中没有奇圈,所以 G是二分图 （ 如图
10.4.3（ b） 所示 ）,故至少应有两间房间即可 。
第 10章 几种典型图图 10.4.3
a b
f
e d
c
( a )
a e f
b c d
( b )
第 10章 几种典型图
【 例 10.4.2】 设 （ n,m） 图 G是二分图,证明 m≤n2/4。
证明 设 G=〈 V1,V2,E〉,|V1|=n1,|V2|=n2，则
n=n1+n2,m≤n1n2。
由 （ a-b） 2=a2+b2-2ab≥0,得
22
2
abab (1)
将 a2+b2+2ab=（ a+b） 2代入 （ 1） 式,得
2( ) 2
2
a b a bab
第 10章 几种典型图二分图的主要应用是匹配,,匹配,是图论中的一个重要内容,它在所谓,人员分配问题,和,最优分配问题,等运筹学中的问题上有重要的应用 。
2
22
12
12
()
4
()
44
ab
ab
n n n
m n n
推得所以第 10章 几种典型图首先看实际中常碰见的问题：给 n个工作人员安排 m
项任务,n个人用 X={x1,x2,…,xn}表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中 k
（ k≥1）个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？
第 10章 几种典型图图 10.4.4
x
1
x
2
x
3
x
4
x
5
y
5
y
4
y
3
y
2
y
1
第 10章 几种典型图例如,现有 x1,x2,x3,x4,x5五个人,y1,y2,y3，
y4,y5五项工作 。 已知 x1能胜任 y1和 y2,x2能胜任 y2和 y3，
x3能胜任 y2和 y5,x4能胜任 y1和 y3,x5能胜任 y3,y4和 y5。
如何安排才能使每个人都有工作做,且每项工作都有人做？
第 10章 几种典型图显然,我们只需做这样的数学模型：以 xi和 yj（ i，
j=1,2,3,4,5） 为顶点,在 xi与其胜任的工作 yj之间连边,得二分图 G,如图 10.4.4所示,然后在 G中找一个边的子集,使得每个顶点只与一条边关联 （ 图中粗线 ）,问题便得以解决了 。 这就是所谓匹配问题,下面给出一些基本概念和术语,假设 G是任一无向图 。 匹配 设 M是 E（ G） 的一个子集,如果 M中任二边在 G中均不邻接,则称 M是 G的一个匹配 。 M中一条边的两个端点,叫做在 M是配对的 。
第 10章 几种典型图饱和与非饱和 若匹配 M的某条边与顶点 v关联,则称 M饱和顶点 v,且称 v是 M― 饱和的 。 否则称 v是 M―
不饱和的 。
完美匹配 G中每一个顶点都是关于匹配 M饱和的 。
完全匹配 设二分图 G=〈 V1,,V2,E〉,M是 G中匹配,v∈ V1,v均是 M― 饱和的,则称 M是 V1对 V2的完全匹配 （ V1― 完全匹配 ） v∈ V2,v均是 M― 饱和的,则称 M是 V2对 V1的完全匹配 （ V2-完全匹配 ） 。
若 M既是 V1― 完全匹配,又是 V2― 完全匹配,则称 M是完全匹配 。
第 10章 几种典型图交互道 若 M是图 G的一个匹配,设从 G中的一个顶点到另一个顶点存在一条通路,这条通路由属于 M和不属于 M的边交替出现组成,则称此通路为交互道 。
如图 10.4.5（ a），实线边属于 M,x1y1x3y2x2y3x4y4
是一条由 x1到 y4的交互道。可增广道 若一交互道的两个端点均为 M― 不饱和点，则称其为可增广道。
显然,一条边的二端点非饱和,则这条边是可增广道 。
如图 10.4.5（ b），实线边属于 M,x2y1x1y2x4y4x5y5
是可增广道,x3y6也是可增广道。
第 10章 几种典型图图 10.4.5
x
1
x
2
x
3
x
4
y
4
y
3
y
2
y
1
( a )
x
1
x
2
x
3
x
4
x
5
y
5
y
4
y
3
y
2
y
1
y
6
( b )
第 10章 几种典型图性质 可增广道的长度必为奇数,且属于 M的边比不属于 M的边多 1条 。
对于可增广道，只要改变一下匹配关系，即只要将此道上虚、实边对换，得新的匹配 M′，则 M′中的边数比 M中的边数多 1条。如图 10.4.6（ b）中的可增广道按上述方法得新的交互道 x2y1x1y2x4y4x5y5，如图 10.4.5，
实边是匹配，中的边数由 M中的 3条增至 4条。用此方法可逐步得到较大的匹配。
第 10章 几种典型图图 10.4.6
x
1
x
2
x
3
x
4
x
5
y
5
y
4
y
3
y
2
y
1
y
6
第 10章 几种典型图定理 10.4.2 在图 G中,M为最大匹配的充分必要条件是不存在可增广道 。
证明 必要性用反证法立即可得 。
再证充分性 。 用反证法,假设 M不是最大匹配,则存在匹配 M1,使得 |M1|＞ |M|。 设由 M M1（
差运算 ） 导出的子图 G［ M M1］ 记为 H,它的每个分支或者是交错道,或者是交错回路 。
第 10章 几种典型图因为 M和 M1都是 G的匹配,H中每个顶点的度数至多为 2,于是每个分支中的每个顶点的度数至多为 2，
所以每个分支或者是回路,或者是路,且其上的边交错地属于 M和 M1。 由于 |M1|＞ |M|,因而 H中必有一条路,
它的起点和终点都是关于 M未饱和的,也一定是 G中关于 M未饱和的顶点,因此在 G中存在关于 M的可增广道,
这与假设矛盾 。
第 10章 几种典型图定理 10.4.3（ 霍尔定理 ） 二分图 G=〈 V1,V2,E〉
有 V1― 完全匹配,当且仅当对 V1中任一子集 A,和所有与 A邻接的点构成的点集 N（ A）,恒有
|N（ A） |≥|A|
证明 先证必要性 。 假设 V1中的每个顶点关于匹配
M均饱和,并设 A是 V1的子集,因 A的每个顶点在 M下和 N（ A） 中不同的顶点配对,所以有 |N（ A） |≥|A|。
第 10章 几种典型图再证充分性 。 假设 G是满足对任何 V1的子集 A,|N
（ A） |≥|A|的二分图,但 G中没有使 V1中每个顶点饱和的完全匹配,设 M1是 G的一个最大匹配,由假设,M1
不使 V1中所有顶点饱和 。 设 v是 V1中的 M1― 不饱和点,
并设 B是与 v有关于 M1交错道相连通的所有顶点的集合 。
由于 M1是一最大匹配,由定理 10.4.2可知,v为 B中唯一的 M1― 不饱和点 。
第 10章 几种典型图令 A=B∩V1,T=B∩V2,显然,A-{v}中的顶点都关于 M1饱和,即它与 T中的顶点在 M1下配对,于是
|T|=|A|-1
且 N（ A） T,又因 N（ A） 中的每个顶点有关于
M1交错路与 v相连通,因此 N（ A） =T所以
|N（ A） |=|A|-1＜ |A|
与假设 |N（ A） |≥|A|矛盾。证毕
第 10章 几种典型图图 10.4.7
x
1
x
2
x
3
x
4
y
5
y
4
y
3
y
2
y
1
第 10章 几种典型图
【 例 10.4.3】 设有 4个人 x1,x2,x3,x4，现有 5项工作 y1,y2,y3,y4,y5需要做，每个人所能胜任那几项工作的情况如图 10.4.7所示，问能否使每个人都能分配到一项工作？
解 这个问题即为：二分图 G=〈 V1,V2,E〉 是否存在 V1― 完全匹配。当取 A={x1,x3,x4}时,N（ A）
={y2,y5}，因此 |N（ A） |＜ |A|，根据霍尔定理，二分图没有 V1― 完全匹配，所以要使每个人都能分配到一项工作是不可能的。
第 10章 几种典型图
【 例 10.4.4】 证明 k― 正则二分图 （ k＞ 0） 有完全匹配 。
证明 设 G=〈 V1,V2,E〉 为 k― 正则二分图,则
k·|V1|=|E|=k·|V2| 即 |V1|=|V2|
A V1,设 E1是 A中顶点所关联的边的集合,E2是
N（ A） 中顶点所关联的边的集合,根据 N（ A） 的定义,
必有
| E1|≤|E2|
第 10章 几种典型图于是
k·|N（ A） |=|E2|=|E1|=k·|A
因此
|N（ A） |≥|A|
由霍尔定理知,G有 V1― 完全匹配 M,因为 |V1|=|V2|，
所以 M也是 V2― 完全匹配,即 G有完全匹配 。 证毕第 10章 几种典型图检查一个二分图是否满足相异条件有时是相当麻烦的,下面的定理给出了判断一个二分图 G=〈 V1,V2，
E〉 是否存在 V1― 完全匹配的充分条件,一般称为,t
条件,,这个条件比较容易检查,但它不是必要条件 。
第 10章 几种典型图定理 10.4.4 设 G=〈 V1,V2,E〉 是二分图,如果能找到一个正整数 t,使得对于 V1中的任何顶点 x有 d（ x）
≥t,并且对于 V2中的任何顶点 y有 d（ y） ≤t,则 G中有
V1― 完全匹配 。
证明 由条件知,V1中的每个顶点至少与 V2中的 t个顶点邻接,而 V2中的每个顶点至多与 V1中的 t个顶点邻接,因此,A V1,必有
|N（ A） |≥|A|
所以 G中有 V1― 完全匹配。证毕
第 10章 几种典型图
10.5 例题选解
【 例 10.5.1】 判断下列各命题是否是真命题 。
（ 1） 完全图 Kn（ n≥1） 都是欧拉图 。
（ 2） n（ n≥1） 阶有向完全图都是有向欧拉图 。
（ 3） 二分图 G=〈 V1,V2,E〉 必不是欧拉图 。
（ 4） 完全图 Kn（ n≥1） 都是哈密顿图 。
（ 5）完全二分图 Kr,s（ r≥1,s≥1）都是哈密顿图。
第 10章 几种典型图
（ 6） 存在哈密顿回路的有向图都是强连通图 。
（ 7） 若 G*是平面图 G的对偶图,则 G也是 G*的对偶图 。
（ 8） 完全二分图 Kr,s（ r≥1,s≥1） 都不是平面图 。
（ 9） n（ n≥5） 阶无向完全图都是非平面图 。
（ 10） n（ n≥2） 阶无向树都是二分图 。
第 10章 几种典型图解答与分析
（ 1） 假命题 。 完全图 Kn每个顶点的度数均是 n-1，
当 n是大于等于 2的偶数时,Kn的每个顶点的度数均为
n-1是奇数,故此时 Kn不是欧拉图 。
（ 2） 真命题 。 由定义知有向完全图 G必是连通图,
G的任意两个顶点间均有一对方向相反的边相连,即 G
的每个点的出度和入度均相等,因此必是有向欧拉图 。
第 10章 几种典型图
（ 3） 假命题 。 当 G是连通的二分图,且 |V1|,|V2|均为偶数时,G的每个顶点度数均是偶数,此时的 G是欧拉图 。
（ 4） 假命题 。 当 n=2时,K2中没有哈密顿回路,故并非完全图 Kn（ n≥1） 都是哈密顿图 。
（ 5） 假命题 。 当 r≠s时,Kr,s都不是哈密顿图 。 证：
不妨设 |V1|=r＜ s=|V2|,去掉 V1中所有顶点后得到的 Kr,s
的子图的连通分支数为 s,因此,
p（ G-V1） =s＞ |V1|,不满足哈密顿图的必要条件 。
第 10章 几种典型图
（ 6） 真命题 。 哈密顿回路是行遍图中每一个顶点的回路,因此,存在哈密顿回路的有向图都是强连通图 。
（ 7） 假命题 。 G是平面图,但不一定是连通图,而
G的对偶图 G*总是连通的,所以,当 G不连通时 G不是
G*的对偶图 。
（ 8） 假命题 。 完全二分图 Kr,s（ r≥1,s≥1） 当 r与 s
均大于等于 3时,因其中含有子图 K3,3必是非平面图,
但完全二分图 K1,1,K2,2,K2,3,K3,2都是平面图 。
第 10章 几种典型图
（ 9） 真命题 。 n（ n≥5） 阶无向完全图中均含有子图 K5,所以都是非平面图 。
(10)真命题 。 n（ n≥2） 阶无向树中无奇数长度的回路,因此均是二分图 。
第 10章 几种典型图
【 例 10.5.2】 有 11个学生计划几天都在一个圆桌上共进晚餐,并且希望每次晚餐时,每个学生两边邻座的人都不相同,按此要求,他们在一起共进晚餐最多几天？
分析 以 11个顶点表示人,边表示相邻而坐的二人,则任意一人与其他人相邻就座的所有情况,就是 11个顶点的完全图；一次晚餐的就座方式,就是 K11中的一个哈密顿圈；每次晚餐时,每个学生两边邻座的人都不相同,
就是在 K11中的每个哈密顿圈没有公共边,问题归结为在 K11中最多有多少个没有公共边的哈密顿圈 。
第 10章 几种典型图因为 11人的坐法只由他们之间的相邻关系决定,排成圆形时,仅与排列顺序有关 。 因此对各种做法,可认为一人的座位不变,将其设为 1号,并不妨放在圆心,
其余 10人放在圆周上 。 于是不同的哈密顿圈,可由圆周上不同编号的旋转而得到 。
解 11个顶点的完全图共有 11× (11-1)/2=55条边,
在 K11中每条哈密顿圈的长度为 11,则没有公共边的哈密顿圈数是 55/11=5条,即最多有 5天 。 此 5条不同的哈密顿圈可由下面方式作图得到：
第 10章 几种典型图设有一条哈密顿圈 1-2-3…11-1,将此图的顶点标号旋转 360° /10,2× 360° /10,3× 360° /10,
4× 360° /10,就得到另外四个图 （ 如图 10.5.1所示 ） 。
每个图对应一条哈密顿圈 。 如果 11个人标记为 1，
2,…,11,5天中排列情况如下：
第 10章 几种典型图图 10.5.1
6
4
2 3
5
7
9
1110
8
1
2
3
5 7
9
11
10
86
4
1
8
6
4 2
3
5
7
911
10
1
4
2
3 5
7
9
11
108
6
1
10
8
6 4
2
3
5
79
11
1
第 10章 几种典型图
1 2 3 4 5 6 7 8 9 1 0 1 1
1 4 2 6 3 8 5 1 0 7 1 1 9
1 6 4 8 2 1 0 3 1 1 5 9 7
1 8 6 1 0 4 1 1 2 9 3 7 5
1 1 0 8 1 1 6 9 4 7 2 5 3
第 10章 几种典型图
【 例 10.5.3】 证明：在由 6个结点和 12条边组成的连通简单平面图 G中,每个面的度数均为 3。
解 G是简单图,所以所有面的最小度 k=deg（ R）
≥3。 又由于 G连通,故
v-e+r=2 （ v,e,r分别为点数,边数和面数 ）
v=6,e=12,所以 r=8 。 由 握 手 定 理
2e=24=Σdeg（ R） ≥kr=8k,解得 k≤3。 因此,有 k=3,即
G的最小度等于 3。 不难证明,面的最大度 k′=3。 因为否则将有 3r＜ 2e,得出 24＜ 24的矛盾,故每个面的度数均为 3。
第 10章 几种典型图习 题 十
1.判别图 10.1中各图是否是欧拉图或半欧拉图,并说明理由 。
第 10章 几种典型图图 10.1
( a ) ( b ) ( c )
第 10章 几种典型图
2.构造简单欧拉图,使其顶点数 n和边数 m满足下列条件,
（ 1） n,m均为奇数 。
（ 2） n,m均为偶数 。
（ 3） n为奇数,m为偶数。
第 10章 几种典型图图 10.2
第 10章 几种典型图
3,(1)图 10.2中的边能剖分成两条路 （ 边不重合 ）,
试给出这样的剖分 。
(2)设 G是一个有 k个奇度数顶点的无向图,问最少加几条边到 G中去,能使所得图有一条欧拉回路,说明对图 9.2如何做到这一点 。
4.对于 σ=3,n=3,构造一个笛波滤恩序列,并画出 G3,3。
第 10章 几种典型图
5.构造简单无向图 G,使其满足下列条件：
（ 1） G是欧拉图,但不是哈密顿图 。
（ 2） G是哈密顿图,但不是欧拉图 。
（ 3） G既是欧拉图,同时也是哈密顿图 。
（ 4） G即不是欧拉图也不是哈密顿图 。
6.判别图 10.3中各图是否是哈密顿图或半哈密顿图，并说明理由。
第 10章 几种典型图图 10.3
( a ) ( b ) ( c )
第 10章 几种典型图
7.证明：若 G是半哈密顿图,则对于 V的任何子集 S
均有
P（ G-S） ≤|S|+1
8.设简单图 G=〈 V,E〉 且 |V|=n,|E|=m,若有
m≥C2n-2+2,则 G是哈密顿图 。
9.若 G是平面图,有 k个连通分支,证明,n-m+r=k+1。
10.证明图 10.1（ b） 不是平面图 。
11.证明图 10.3（ c） 不是平面图 。
第 10章 几种典型图
12.证明：小于 30条边的平面简单图中存在度数小于等于 4的顶点 。
13.若将平面分成 β个面,要求每两个面均相邻,
则 β最大为多少？
14.设 G是 n个顶点的简单连通平面图,n≥4。 已知
G中不含长度为 3的初级回路,证明 G中一定存在顶点 v，
d（ v） ≤3。
15.设 G是 11个顶点的无向简单图,证明 G或必为非平面图 。
16.设 G是简单平面图,面数 r＜ 12,δ（ G） ≥3,证明 G中存在次数小于或等于 4的面 。
第 10章 几种典型图
17.画出图 10.4中各图的对偶图。
图 10.4
( a ) ( b ) ( c )
第 10章 几种典型图
18.求出上题中对各图的面着色的最少色数 。
19.用韦尔奇 ·鲍威尔法对图 10.5中各图着色，求图的着色数。
20.假定 G是二分图,如何安排 G中顶点的次序可使
G的邻接矩阵呈 为矩阵,0为零矩阵 。
21.证明一个图能被两种颜色正常着色,当且仅当它不包含长度为奇数的回路 。
0
0
B
C
第 10章 几种典型图图 10.5
C
B
A
H G
F
E
D
1 2 3
6
4 5
7
9
11
12 13
10
8
( a ) ( b )
第 10章 几种典型图
22.今有工人甲,乙,丙,任务 a,b,c。 已知甲能胜任 a,b,c,乙能胜任 a,b,丙能胜任 b,c。 能给出几种不同的安排方案,使每个工人去完成他们能胜任的任务？
23.判断图 10.1,图 10.3,图 10.4中各图是否是二分图 。
24.某单位有 7个空缺 p1,p2,…,p7要招聘,有 10个应聘者 m1,m2,…,m10,他们适合的工作岗位集合分别为：
{p1,p5,p6},{p2,p6,p7},{p3,p4},{p1,p5},{p6，
p7},{p3},{p2,p3},{p1,p3},{p1},{p5}。 如何安排能使落聘者最少？
