1
第 8章 一些特殊的图
8.1 二部图
8.2 欧拉图
8.3 哈密顿图
8.4 平面图
2
8.1 二部图
?二部图
?完全二部图
?匹配
?极大匹配
?最大匹配
?匹配数
?完备匹配
3
二部图
定义 设无向图 G=<V,E>,若能将 V 分成 V1 和 V2
(V1?V2=V,V1?V2=?),使得 G中的每条边的两个端
点都一个属于 V1,另一个属于 V2,则称 G为 二部图,
记为 <V1,V2,E>,称 V1和 V2为 互补顶点子集, 又若 G
是简单图,且 V1中每个顶点均与 V2中每个顶点都相
邻,则称 G为 完全二部图,记为 Kr,s,其中 r=|V1|,s=|V2|,
注意, n 阶零图为二部图,
4
二部图的判别法
定理 无向图 G=<V,E>是二部图当且仅当 G中无奇圈
例 下述各图都是二部图
5
匹配
设 G=<V,E>,
匹配 (边独立集 ),任 2条边均不相邻的边子集
极大匹配, 添加任一条边后都不再是匹配的匹配
最大匹配, 边数最多的匹配
匹配数, 最大匹配中的边数,记为 ?1
例 3个图的匹配数 依次为 3,3,4,
6
匹配 (续 )
设 M为 G中一个匹配
vi与 vj被 M匹配, (vi,vj)?M
v为 M饱和点, M中有边与 v关联
v为 M非饱和点, M中没有边与 v关联
M为完美匹配, G的每个顶点都是 M饱和点
例 关于 M1,a,b,e,d是饱和点
f,c是非饱和点
M1不是完美匹配
M2是完美匹配 M1 M2
7
二部图中的匹配
定义 设 G=<V1,V2,E>为二部图,|V1|?|V2|,M是 G中最
大匹配,若 V1中顶点全是 M饱和点,则称 M为 G中 V1
到 V2的 完备匹配, 当 |V1|=|V2|时,完备匹配变成完美
匹配,
(1) (2) (3)
例 图中红边组成各图的一个匹配,(1)为完备的,但不是完
美的 ; (2)不是完备的,其实 (2)中无完备匹配 ; (3) 是完美的,
8
Hall定理
定理 (Hall定理 ) 设二部图 G=<V1,V2,E>中, |V1|?|V2|,G中存
在从 V1到 V2的完备匹配当且仅当 V1中任意 k 个顶点至少与 V2
中的 k个顶点相邻 (k=1,2,…,|V1|),
由 Hall定理不难证明,上一页图 (2)没有完备匹配,
定理 设二部图 G=<V1,V2,E>中,如果存在 t?1,使得 V1中每个
顶点至少关联 t 条边,而 V2中每个顶点至多关联 t条边, 则 G
中存在 V1到 V2的完备匹配,
Hall定理中的条件称为, 相异性条件,,第二个定理中的条
件
称为 t 条件, 满足 t 条件的二部图一定满足相异性条件,
9
一个应用实例
例 某课题组要从 a,b,c,d,e 5人中派 3人分别到上海、广州、
香港去开会, 已知 a只想去上海,b只想去广州,c,d,e都表
示想去广州或香港, 问该课题组在满足个人要求的条件下，
共有几种派遣方案？
解 令 G=<V1,V2,E>,其中 V1={s,g,x},V2={a,b,c,d,e},
E={(u,v) | u?V1,v?V2,v想去 u},
其中 s,g,x分别表示上海, 广州和香港,
G如图所示,
G 满足相异性条件, 因而可给
出派遣方案, 共有 9种派遣方案
(请给出这 9种方案 ),
10
8.2 欧拉图
?欧拉通路
?欧拉回路
?欧拉图
?半欧拉图
11
哥尼斯堡七桥问题
欧拉图是能一笔画出的边不重复的回路,
12
欧拉图
欧拉通路, 图中行遍所有顶点且恰好经过每条边一次的通路,
欧拉回路, 图中行遍所有顶点且恰好经过每条边一次的回路,
欧拉图, 有欧拉回路的图,
半欧拉图, 有欧拉通路而无欧拉回路的图,
几点说明,
上述定义对无向图和有向图都适用,
规定平凡图为欧拉图,
欧拉通路是简单通路,欧拉回路是简单回路,
环不影响图的欧拉性,
13
欧拉图 (续 )
例 图中,(1),(4)为欧拉图 ; (2),(5)为半欧拉图 ; (3),(6)既不
是欧拉图,也不是半欧拉图,
在 (3),(6)中各至少加几条边才能成为欧拉图?
14
欧拉图的判别法
定理 无向图 G为欧拉图当且仅当 G连通且无奇度顶点,
无向图 G是半欧拉图当且仅当 G连通且恰有两个奇度顶点,
定理 有向图 D是欧拉图当且仅当 D连通且每个顶点的入度都
等于出度,
有向图 D具有欧拉通路当且仅当 D连通且恰有两个奇度顶
点,其中一个入度比出度大 1,另一个出度比入度大 1,其余
顶点的入度等于出度,
15
实例
例 1 哥尼斯堡七桥问题
例 2 下面两个图都是欧拉图,
从 A点出发,如何一次成功地走出一条欧拉回路来？
16
8.3 哈密顿图
?哈密顿通路
?哈密顿回路
?哈密顿图
?半哈密顿图
17
哈密顿周游世界问题
18
哈密顿图的定义
哈密顿通路, 经过图中所有顶点一次且仅一次的通路,
哈密顿回路, 经过图中所有顶点一次且仅一次的回路,
哈密顿图, 具有哈密顿回路的图,
半哈密顿图, 具有哈密顿通路而无哈密顿回路的图,
几点说明,
平凡图是哈密顿图,
哈密顿通路是初级通路, 哈密顿回路是初级回路,
环与平行边不影响图的哈密顿性,
19
实例
例 图中,(1),(2)是哈密顿图 ; (3) 是半哈密顿图,
(4)既不是哈密顿图,也不是半哈密顿图，为什么？
20
无向哈密顿图的一个必要条件
定理 设无向图 G=<V,E>是哈密顿图,则对于任意 V1?V且
V1??,均有 p(G?V1)?|V1|,
证 设 C为 G中一条哈密顿回路,有 p(C?V1) ? |V1|,又因为
C?G,故 p(G?V1) ? p(C?V1) ? |V1|,
几点说明
定理中的条件是哈密顿图的必要条件,但不是充分条件,
可利用该定理判断某些图不是哈密顿图,
由定理可知,Kr,s当 s?r+1时不是哈密顿图,
当 r?2时,Kr,r是哈密顿图,而 Kr,r+1是半哈密顿图,
21
实例
例 设 G为 n阶无向连通简单图,若 G中有割点或桥,
则 G不是哈密顿图,
证 (1) 设 v为割点,则 p(G?v) ? 2>|{v}|=1,根据定理,
G不是哈密顿图,
(2) 若 G是 K2(K2有桥 ),它显然不是哈密顿图, 除 K2
外,其他的有桥连通图均有割点, 由 (1),得证 G不是
哈密顿图,
22
无向哈密顿图的一个充分条件
定理
设 G是 n阶无向简单图,若任意两个不相邻的顶点
的度数之和大于等于 n?1,则 G中存在哈密顿通路,
当 n?3时,若任意两个不相邻的顶点的度数之和大
于等于 n,则 G中存在哈密顿回路,从而 G为哈密顿
图,
23
哈密顿通路 (回路 )的存在性 (续 )
定理中的条件是存在哈密顿通路 (回路 )的充分条
件,但不是必要条件,
例如,设 G为长度为 n?1(n?4)的路径,它不满足定理
中哈密顿通路的条件,但它显然存在哈密顿通路,
设 G是长为 n的圈,它不满足定理中哈密顿回路的条
件,但它显然是哈密顿图,
由定理,当 n?3时,Kn均为哈密顿图,
判断某图是否为哈密顿图至今还是一个难题
24
判断是否是哈密顿图 的可行方法
? 观察出一条哈密顿回路
例如 右图 (周游世界问题 )中红
边给出一条哈密顿回路,故它
是哈密顿图,
注意,此图不满足定理的条件,
? 满足充分条件
例如 当 n?3时,Kn中任何两个不同的顶点 u,v,均
有 d(u)+d(v) = 2(n?1) ? n,所以 Kn为哈密顿图,
25
判断是否是哈 密顿图 的可行方法 (续 )
例 1/4国际象棋盘 (4?4方格 )上的
跳马问题, 马是否能恰好经过
每一个方格一次后回到原处?
解 每个方格看作一个顶点,2个
顶点之间有边当且仅当马可以从一个方格跳到另一个方格,
得到 16阶图 G,如左图红边所示, 取 V1={a,b,c,d},则 p(G?V1)
= 6 >|V1|,见右图, 由定理,图中无哈密顿回路,故问题无解,
在国际象棋盘 (8?8)上,跳马问题是否有解?
?不满足必要条件
26
应用实例
例 某次国际会议 8人参加, 已知每人至少与其余 7人中
的 4人有共同语言, 问服务员能否将他们安排在同一张
圆桌就座, 使得每个人都能与两边的人交谈？
解 图是描述事物之间关系的最好的手段之一, 作无向图
G=<V,E>,其中 V={v|v为与会者 },E={(u,v) | u,v?V,u与 v
有共同语言,且 u?v},G为简单图, 根据条件,?v?V,d(v)?
4,于是, ?u,v?V,有 d(u)+d(v)?8,由定理可知 G为哈密顿
图, 服务员在 G中找一条哈密顿回路 C,按 C中相邻关系
安排座位即可,
由本题想到的：哈密顿图的实质是能将图中所有的顶点
排在同一个圈中,
第 8章 一些特殊的图
8.1 二部图
8.2 欧拉图
8.3 哈密顿图
8.4 平面图
2
8.1 二部图
?二部图
?完全二部图
?匹配
?极大匹配
?最大匹配
?匹配数
?完备匹配
3
二部图
定义 设无向图 G=<V,E>,若能将 V 分成 V1 和 V2
(V1?V2=V,V1?V2=?),使得 G中的每条边的两个端
点都一个属于 V1,另一个属于 V2,则称 G为 二部图,
记为 <V1,V2,E>,称 V1和 V2为 互补顶点子集, 又若 G
是简单图,且 V1中每个顶点均与 V2中每个顶点都相
邻,则称 G为 完全二部图,记为 Kr,s,其中 r=|V1|,s=|V2|,
注意, n 阶零图为二部图,
4
二部图的判别法
定理 无向图 G=<V,E>是二部图当且仅当 G中无奇圈
例 下述各图都是二部图
5
匹配
设 G=<V,E>,
匹配 (边独立集 ),任 2条边均不相邻的边子集
极大匹配, 添加任一条边后都不再是匹配的匹配
最大匹配, 边数最多的匹配
匹配数, 最大匹配中的边数,记为 ?1
例 3个图的匹配数 依次为 3,3,4,
6
匹配 (续 )
设 M为 G中一个匹配
vi与 vj被 M匹配, (vi,vj)?M
v为 M饱和点, M中有边与 v关联
v为 M非饱和点, M中没有边与 v关联
M为完美匹配, G的每个顶点都是 M饱和点
例 关于 M1,a,b,e,d是饱和点
f,c是非饱和点
M1不是完美匹配
M2是完美匹配 M1 M2
7
二部图中的匹配
定义 设 G=<V1,V2,E>为二部图,|V1|?|V2|,M是 G中最
大匹配,若 V1中顶点全是 M饱和点,则称 M为 G中 V1
到 V2的 完备匹配, 当 |V1|=|V2|时,完备匹配变成完美
匹配,
(1) (2) (3)
例 图中红边组成各图的一个匹配,(1)为完备的,但不是完
美的 ; (2)不是完备的,其实 (2)中无完备匹配 ; (3) 是完美的,
8
Hall定理
定理 (Hall定理 ) 设二部图 G=<V1,V2,E>中, |V1|?|V2|,G中存
在从 V1到 V2的完备匹配当且仅当 V1中任意 k 个顶点至少与 V2
中的 k个顶点相邻 (k=1,2,…,|V1|),
由 Hall定理不难证明,上一页图 (2)没有完备匹配,
定理 设二部图 G=<V1,V2,E>中,如果存在 t?1,使得 V1中每个
顶点至少关联 t 条边,而 V2中每个顶点至多关联 t条边, 则 G
中存在 V1到 V2的完备匹配,
Hall定理中的条件称为, 相异性条件,,第二个定理中的条
件
称为 t 条件, 满足 t 条件的二部图一定满足相异性条件,
9
一个应用实例
例 某课题组要从 a,b,c,d,e 5人中派 3人分别到上海、广州、
香港去开会, 已知 a只想去上海,b只想去广州,c,d,e都表
示想去广州或香港, 问该课题组在满足个人要求的条件下，
共有几种派遣方案？
解 令 G=<V1,V2,E>,其中 V1={s,g,x},V2={a,b,c,d,e},
E={(u,v) | u?V1,v?V2,v想去 u},
其中 s,g,x分别表示上海, 广州和香港,
G如图所示,
G 满足相异性条件, 因而可给
出派遣方案, 共有 9种派遣方案
(请给出这 9种方案 ),
10
8.2 欧拉图
?欧拉通路
?欧拉回路
?欧拉图
?半欧拉图
11
哥尼斯堡七桥问题
欧拉图是能一笔画出的边不重复的回路,
12
欧拉图
欧拉通路, 图中行遍所有顶点且恰好经过每条边一次的通路,
欧拉回路, 图中行遍所有顶点且恰好经过每条边一次的回路,
欧拉图, 有欧拉回路的图,
半欧拉图, 有欧拉通路而无欧拉回路的图,
几点说明,
上述定义对无向图和有向图都适用,
规定平凡图为欧拉图,
欧拉通路是简单通路,欧拉回路是简单回路,
环不影响图的欧拉性,
13
欧拉图 (续 )
例 图中,(1),(4)为欧拉图 ; (2),(5)为半欧拉图 ; (3),(6)既不
是欧拉图,也不是半欧拉图,
在 (3),(6)中各至少加几条边才能成为欧拉图?
14
欧拉图的判别法
定理 无向图 G为欧拉图当且仅当 G连通且无奇度顶点,
无向图 G是半欧拉图当且仅当 G连通且恰有两个奇度顶点,
定理 有向图 D是欧拉图当且仅当 D连通且每个顶点的入度都
等于出度,
有向图 D具有欧拉通路当且仅当 D连通且恰有两个奇度顶
点,其中一个入度比出度大 1,另一个出度比入度大 1,其余
顶点的入度等于出度,
15
实例
例 1 哥尼斯堡七桥问题
例 2 下面两个图都是欧拉图,
从 A点出发,如何一次成功地走出一条欧拉回路来？
16
8.3 哈密顿图
?哈密顿通路
?哈密顿回路
?哈密顿图
?半哈密顿图
17
哈密顿周游世界问题
18
哈密顿图的定义
哈密顿通路, 经过图中所有顶点一次且仅一次的通路,
哈密顿回路, 经过图中所有顶点一次且仅一次的回路,
哈密顿图, 具有哈密顿回路的图,
半哈密顿图, 具有哈密顿通路而无哈密顿回路的图,
几点说明,
平凡图是哈密顿图,
哈密顿通路是初级通路, 哈密顿回路是初级回路,
环与平行边不影响图的哈密顿性,
19
实例
例 图中,(1),(2)是哈密顿图 ; (3) 是半哈密顿图,
(4)既不是哈密顿图,也不是半哈密顿图，为什么？
20
无向哈密顿图的一个必要条件
定理 设无向图 G=<V,E>是哈密顿图,则对于任意 V1?V且
V1??,均有 p(G?V1)?|V1|,
证 设 C为 G中一条哈密顿回路,有 p(C?V1) ? |V1|,又因为
C?G,故 p(G?V1) ? p(C?V1) ? |V1|,
几点说明
定理中的条件是哈密顿图的必要条件,但不是充分条件,
可利用该定理判断某些图不是哈密顿图,
由定理可知,Kr,s当 s?r+1时不是哈密顿图,
当 r?2时,Kr,r是哈密顿图,而 Kr,r+1是半哈密顿图,
21
实例
例 设 G为 n阶无向连通简单图,若 G中有割点或桥,
则 G不是哈密顿图,
证 (1) 设 v为割点,则 p(G?v) ? 2>|{v}|=1,根据定理,
G不是哈密顿图,
(2) 若 G是 K2(K2有桥 ),它显然不是哈密顿图, 除 K2
外,其他的有桥连通图均有割点, 由 (1),得证 G不是
哈密顿图,
22
无向哈密顿图的一个充分条件
定理
设 G是 n阶无向简单图,若任意两个不相邻的顶点
的度数之和大于等于 n?1,则 G中存在哈密顿通路,
当 n?3时,若任意两个不相邻的顶点的度数之和大
于等于 n,则 G中存在哈密顿回路,从而 G为哈密顿
图,
23
哈密顿通路 (回路 )的存在性 (续 )
定理中的条件是存在哈密顿通路 (回路 )的充分条
件,但不是必要条件,
例如,设 G为长度为 n?1(n?4)的路径,它不满足定理
中哈密顿通路的条件,但它显然存在哈密顿通路,
设 G是长为 n的圈,它不满足定理中哈密顿回路的条
件,但它显然是哈密顿图,
由定理,当 n?3时,Kn均为哈密顿图,
判断某图是否为哈密顿图至今还是一个难题
24
判断是否是哈密顿图 的可行方法
? 观察出一条哈密顿回路
例如 右图 (周游世界问题 )中红
边给出一条哈密顿回路,故它
是哈密顿图,
注意,此图不满足定理的条件,
? 满足充分条件
例如 当 n?3时,Kn中任何两个不同的顶点 u,v,均
有 d(u)+d(v) = 2(n?1) ? n,所以 Kn为哈密顿图,
25
判断是否是哈 密顿图 的可行方法 (续 )
例 1/4国际象棋盘 (4?4方格 )上的
跳马问题, 马是否能恰好经过
每一个方格一次后回到原处?
解 每个方格看作一个顶点,2个
顶点之间有边当且仅当马可以从一个方格跳到另一个方格,
得到 16阶图 G,如左图红边所示, 取 V1={a,b,c,d},则 p(G?V1)
= 6 >|V1|,见右图, 由定理,图中无哈密顿回路,故问题无解,
在国际象棋盘 (8?8)上,跳马问题是否有解?
?不满足必要条件
26
应用实例
例 某次国际会议 8人参加, 已知每人至少与其余 7人中
的 4人有共同语言, 问服务员能否将他们安排在同一张
圆桌就座, 使得每个人都能与两边的人交谈？
解 图是描述事物之间关系的最好的手段之一, 作无向图
G=<V,E>,其中 V={v|v为与会者 },E={(u,v) | u,v?V,u与 v
有共同语言,且 u?v},G为简单图, 根据条件,?v?V,d(v)?
4,于是, ?u,v?V,有 d(u)+d(v)?8,由定理可知 G为哈密顿
图, 服务员在 G中找一条哈密顿回路 C,按 C中相邻关系
安排座位即可,
由本题想到的：哈密顿图的实质是能将图中所有的顶点
排在同一个圈中,
