第 9章 图论第 9章 图 论
9.1 图的基本概念
9.2 路和回路
9.3 连通图
9.4 图的矩阵表示
9.5 欧拉图和汉密尔顿图
9.6 树
9.7 二部图及匹配
9.8 平面图 返回总目录第 9章 图论第 9章 图论图论是一个重要的数学分支。数学家欧拉 1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。随着科学技术的发展，图论在运筹学、网络理论、信息论、控制论和计算机科学等领域都得到广泛的应用。本章首先给出图、
简单图、完全图、子图、路和图的同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、
连通矩阵和完全关联矩阵的定义。最后介绍了欧拉图与哈密尔顿图、树、二部图、平面图和图的着色。
返回章目录第 9章 图论
9.1图的基本概念
9.1.1图两个个体 x,y的无序序列称为无序对,记为 (x,y)。
在无序对 (x,y)中,x,y是无序的,它们的顺序可以颠倒,
即 (x,y)=(y,x)。
定义 9.1.1 图 G是一个三重组?V(G),E(G),?G?
其中,V(G)是非空结点集。
E(G)是边集 。
G是边集到结点的有序对或无序对集合的函数 。
第 9章 图论
【 例 9.1】 G=?V(G),E(G),?G?
其中,V(G)=?a,b,c,d?
E(G)=?e1,e2,e3,e4?
G,?G(e1)=(a,b)
G(e2)=(b,c)
G(e3)=(a,c)
G(e4)=(a,a)
试画出 G的图形 。
解,G的图形如图 9.1所示 。
第 9章 图论由于在不引起混乱的情况下,图的边可以用有序对或无序对直接表示 。 因此,图可以简单的表示为：
G=?V,E?
其中,V是非空的结点集 。
E是边的有序对或无序对组成的集合 。
按照这种表示法,例 9.1中的图可以简记为：
G=?V,E?
其中,V=?a,b,c,d?
E=?(a,b),(b,c),(a,c),(a,a)?
第 9章 图论定义 9.1.2 若图 G有 n个结点,则称该图为 n阶图 。
定义 9.1.3 设 G为图,如果 G的所有边都是有向边,则称 G为有向图 。 如果 G的所有边都是无向边,则称 G为无向图 。 如果 G中既有有向边,又有无向边,则称 G为混合图 。
图 9.3的 (a)是无向图,(b)是有向图,(c)是混合图。
第 9章 图论在一个图中,若两个结点由一条边 (有向边或无向边 )
关联,则称其中的一个结点是另一个结点的邻接点 。 并称这两个结点相互邻接 。
在一个图中不与任何结点相邻接的结点,称为孤立点 。
在一个图中,如果两条边关联于同一个结点,则称其中的一个边是另一个边的邻接边 。 并称这两个边相互邻接 。 关联于同一个结点的一条边叫做环或自回路 。 在有向图中环的方向可以是顺时针,也可以是逆时针,它们是等效的 。
定义 9.1.4 由孤立点组成的图叫做零图 。 由一个孤立点组成的图叫做平凡图 。
根据定义 9.1.4,平凡图一定是零图。
第 9章 图论
9.1.2结点的度及其性质定义 9.1.5 设 G=?V,E?是图,v?V,与 v相关联的边数叫做结点 v的度 。 记为 deg(v)。 规定,自回路为所在结点增加 2度 。
在图 G=?V,E?中,度数最大 (小 )的结点的度叫做图 G
的最大 (小 )度,记为?(G)(?(G))。 图 G的最大度和最小度表示为：
(G)=max? deg(v) | v?V?
(G)= min? deg(v) | v?V?
在图 9.1中,?(G)=4,?(G)=0。
第 9章 图论定理 9.1.1 在任何图 G=?V,E?中,所有结点度数的和等于边数的 2倍 。 即：
= 2|E|
证明,图的每一条边都和两个结点相关联,为每个相关联的结点增加一度,给图增加两度 。 所以所有结点度数的和等于边数的 2倍 。
推论 在任何图 G=?V,E?中,度数为奇数的结点必为偶数个 。
Vv
v )d e g (
第 9章 图论定义 9.1.6 设 G=?V,E?是有向图,v?V,射入 (出 )结点
v的边数称为结点 v的入 (出 )度 。 记为 deg－ (v) (deg＋ (v))。
显然,任何结点的入度与出度的和等于该结点的度数,
即 deg(v)=deg－ (v)+deg＋ (v)。
定理 9.1.2 在有向图中,所有结点入度的和等于所有结点出度的和 。
证明,在有向图中每一条边对应一个入度和一个出度,为图的入度和出度各增加 1。 所以,所有结点入度的和等于边数,所有结点出度的和也等于边数 。
第 9章 图论
9.1.3多重图,简单图,完全图和正则图定义 9.1.7 在图 G中，连接同一对结点的多条相同边称为平行边。平行边的条数称为该平行边的重数。含平行边的图叫多重图。不含平行边和环的图叫简单图。
例如，在图 9.4(a)中结点 a和 b之间有两条平行边，结点 b和 c之间有三条平行边，结点 b上有两条平行边，这两条平行边都是环。图 9.4(a)不是简单图。
又如,在图 9.4(b)中结点 v1和 v2之间有两条平行边 。 v2
和 v3之间的两条边,因为方向不同,所以不是平行边 。 图
9.4(b)不是简单图 。
简单图不含平行边和环。
第 9章 图论第 9章 图论定理 9.1.3 设 G为 n阶简单无向图,则?(G)≤n–1。
证明,因为 G有 n个结点,G的任何结点 v最多只能与其余的 n–1结点相邻接；又因为 G为简单图,既无平行边,又无环 。 所以 deg(v)≤n–1。 由 v的任意性,就有
(G) =max?deg(v) | v?V?≤n–1。
定义 9.1.8 设 G为 n阶简单无向图，若 G中的每个结点都与其余的 n–1个结点相邻接，则称 G为 n阶无向完全图。记为
Kn。在 n阶无向完全图中，给每一条边任意确定一个方向，
所得到的图称为 n阶有向完全图。也记为 Kn。
今后，将 n阶无向完全图和 n阶有向完全图统称为 n阶完全图。
第 9章 图论定理 9.1.4 n阶完全图 Kn的边数为证明,在 Kn中，每个结点都与其余的 n–1结点相邻接，
即任何一对结点之间都有一条边，故边数应为定义 9.1.9 设 G为 n阶简单无向图，若 G中每个结点都是 k
度的，则称 G为 k次正则图。
)1(212 nnC n
第 9章 图论
9.1.4图的同构在图论中只关心结点间是否有连线，而不关心结点的位置和连线的形状。因此，对于给定的图而言，如果将图的各结点安排在不同的位置上，并且用不同形状的弧线或直线表示各边，则可以得到各种不同图形。所以，同一图的图形并不惟一。由于这种图形表示的任意性，可能出现这样的情况：看起来完全不同的两种图形，却表示着同一个图。
例如，在图 9.6中,(a)和 (b)两个图的图形不同，但它们的结构完全相同，是同一个图。
为了描述看起来不同，而其结构完全相同的图，引入了同构的概念。
第 9章 图论第 9章 图论定义 9.1.10 设 G1=?V1,E1?与 G2=?V2,E2?是两个无向图
(有向图 ),若存在双射函数
f,V1?V2,?v1?V1,?v2?V1
(v1,v2)?E1(?v1,v2E1)当且仅当
(f(v1),f(v2))?E2)(?f(v1),f(v2)E2)
并且 (v1,v2)(?v1,v2?)与 (f(v1),f(v2))(?f(v1),f(v2)?)的重数相同，
则称图 G1与图 G2同构。记为 G1≌ G2。双射函数 f称为图 G1
与图 G2的同构函数。
第 9章 图论两个图同构必须满足下列条件：
① 结点数相同 。
② 边数相同 。
③ 度数相同的结点数相同 。
这三个条件是两个图同构的必要条件，不是充分条件。
一般的，用上述三个必要条件判断两个图是不同构的。
两个图同构，它们的同构函数必须实现同度结点对应同度结点。
第 9章 图论
9.1.5补图,子图和生成子图定义 9.1.11 设 G=?V,E?是 n阶简单无向图,G中的所有结点和所有能使 G成为完全图的添加边组成的图称为图 G
的相对于完全图的补图,简称为 G的补图 。 记为 。 若
G≌,则称 G为自补图 。
在图 9.9
中,(b)是 (a)
的补图,(a)与
(b)同构，所以 (a)是自补图。
G
G
第 9章 图论定义 9.1.12 设 G=?V,E?与 G1=?V1,E1?是两个图 。 如果
V1?V且 E1?E,则称 G1是 G的子图,G是 G1的母图；如果
V1?V且 E1?E,则称 G1是 G的真子图；如果 V1＝ V且 E1?E则称 G1是 G的生成子图 。
在图
9.10中，
(b)是 (a)的子图、真子图、生成子图。
返回章目录第 9章 图论
9.2 路和回路定义 9.2.1 设 G=?V,E?是图,G中的结点与边的交替序列 L：
v0e1v1e2v2? envn叫做 v0到 vn的路 。 其中 vi-1与 vi是 ei的端点,
i=1,?,n。 v0和 vn分别叫做路 L的始点和终点 。 路 L中边的条数叫做该路的长度 。
例如,在图 9.11中,
L1,v5e8v4e5v2e6v5e7v3 是从 v5到 v3的路,v5是始点,
v3是终点,长度为 4。
L2,v1e1v2e3v3 是从 v1到 v3的路,v1是始点,
v3是终点,长度为 2。
在简单图中没有平行边和环,路 L,v0e1v1e2v2? envn完全由它的结点序列 v0v1v2? vn确定 。 所以,在简单图中的路可以用结点序列表示 。
第 9章 图论定义 9.2.2 设 G=?V,E?是图,L是从 v0到 vn的路。若 v0=vn，则称 L为回路。
若 L中所有边各异，则称 L为简单路。
若此时又有 v0=vn，则称 L为简单回路。
若 L中所有结点各异，则称 L为基本路。
若此时又有 v0=vn，则称 L为基本回路。
若 L既是简单路，又是基本路，则称 L
为初级路。若此时又有 v0=vn，则称 L为初级回路。
在图 9.11中,L1是一条简单路。 L2
是一条简单路、基本路、初级路。。
第 9章 图论定理 9.2.1 在 n阶图 G中,若从结点 vi到 vj(vi≠vj)存在一条路,则必存在长度小于等于 n-1的路 。
证明,设 L,vie1v1e2v2? ejvj是 G中一条从结点 vi到 vj长度为 l的路,路上有 l+1个结点 。
若 l≤n-1,则定理已证 。
否则,l＞ n-1,此时,l+1＞ n,即路 L上的结点数 l+1
大于图 G中的结点数 n,此路上必有相同结点 。 设 vk和 vs相同 。 于是,此路两次通过同一个结点 vk(vs),所以在 L上存在 vs到自身的回路 Cks。 在 L上删除 Cks上的一切边和除 vs以外的一切结点,得路 L1,vie1v1… ekvs… ejvj。 L1仍为从结点 vi
到 vj的路,且长度至少比 L减少 1。 若路 L1的长度小于等于
n-1,则定理已证 。 否则,重复上述过程 。 由于 G有 n个结点,经过有限步后,必得到从 vi到 vj长度小于等于 n-1的路 。
第 9章 图论推论 在 n阶图 G中,若从结点 vi到 vj(vi≠vj)存在路,则必存在长度小于等于 n-1的初级路 。
由定理 9.2.1的证明过程知,本推论成立 。
类似的可证明下列定理和推论 。
定理 9.2.2 在 n阶图 G中,若存在结点 vi到自身的回路,
则必存在 vi到自身长度小于等于 n的回路 。
推论 在 n阶图 G中，若存在结点 vi到自身的简单回路，
则必存在 vi到自身长度小于等于 n的初级回路。
返回章目录第 9章 图论
9.3连通图
9.3.1无向连通图定义 9.3.1 在无向图 G中,如果结点 u和结点 v之间存在一条路,则称结点 u和结点 v连通 。 记为 u～ v。 规定,G中任意结点 v和自身连通,即 v～ v。
在无向图中,如果结点 u和结点 v连通,即 u～ v,那么,
结点 v和结点 u连通,即 v～ u。 所以,无向图结点间的连通是对称的 。
设 G=?V,E?是无向图,在图 G的结点集 V上建立一个二元关系 R：
R=u,v?| u?V∧ v?V∧ u和 v连通?
R叫做无向图 G的结点集 V上的连通关系 。
因为 R是自反的、对称的、传递的，所以 R是 V上的等价关系。无向图 G的结点集 V上的连通关系是等价关系。
第 9章 图论设 G是图 9.14。结点集 V上的连通关系为 R，以下验证
R是 V上的等价关系，并找出所有等价类。
R=a,a?,?a,b?,?a,c?,?b,a?,?b,b?,?b,c?,?c,a?,?c,b?,
c,c?,?d,d?,?e,e?,?e,f?,?e,g?,?e,h?,?f,e?,?f,f?,
f,g?,?f,h?,?g,e?,?g,f?,?g,g?,?g,h?,?h,e?,?h,f?,
h,g?,?h,h
=?a,b,c?×?a,b,c?∪?d?×?d?∪?e,f,g,h?×?e,f,g,h?
根据定义,R
是 V上的等价关系。等价类有三个，分别是：
a,b,c?,?d?，
e,f,g,h?。
第 9章 图论定义 9.3.2 若无向图 G中的任何两个结点都是连通的,
则称 G为连通图 。 规定,平凡图是连通图 。
定义 9.3.3 设 G=?V,E?是图
⑴ V1?V且 V1≠?,E1是 G中两个端点都在 V1中的边组成的集合,图 G1=?V1,E1?叫做 G的由 V1导出的子图,记为
G[V1]。
⑵ E2?E且 E2≠?,V2是由 E2中的边所关联的结点组成的集合,图 G2=?V2,E2?叫做 G的由 E2导出的子图,记为
G[E2]。
在图 9.15中,设图 G为 (a),取 V1=?a,b,c?,则 G的由
V1导出的子图 G[V1]是 (b)。 取 E2=?(a,b),(d,c)?,G的由 E2导出的子图 G[E2]是 (c)。
第 9章 图论第 9章 图论定义 9.3.4 设 G=?V,E?是无向图,R是 V上的连通关系，
V/R=?Vi?Vi是 R的等价类,i=1,?,k?是 V关于 R的商集，
G[Vi]是 Vi导出的子图，称 G[Vi]( i=1,?,k)为 G的连通分支。
G的连通分支数记为 W(G)。
设图 9.14为 G，在 G中，连通关系 R的三个等价类是
a,b,c?,?d?,?e,f,g,h?，它们导出的 G的子图分别是图
9.14中的 (a),(b),(c)。它们都是 G的连通分支。 G的连通分支数 W(G)=3。
每一个连通分支中任何两个结点是连通的，而位于不同连通分支中的任何两个结点是不连通的。即每一个连通分支都是原图的最大的连通子图。在图 9.14中,(a),(b)，
(c)都是最大的连通子图。
第 9章 图论定义 9.3.5 设 u,v是无向图 G中的任意两个结点,若 u
和 v连通,则 u和 v之间最短路的长叫做结点 u与结点 v的距离,记为 d(u,v)。 若 u和 v不连通,规定,u与 v的距离为 ∞。
即 d(u,v)=∞。
设 G=?V,E?是无向图,u,v和 w是 V中的任意结点,G
的结点间的距离有以下的性质：
① d(u,v)≥0
② d(u,u)=0
③ d(u,v)＋ d(v,w)≥d(u,w)
④ d(u,v)=d(v,u)
在 n阶无向完全图 Kn中,每两个不同结点间都有一条边,它们的距离是 1。 在零图中,每两个不同结点间都没有路,它们的距离都是 ∞。
在图 G中删除一个结点，就是将这个结点与它的所有关联边全部删除。删除一个边，则仅去掉这个边。
第 9章 图论定义 9.3.6 设 G=?V,E?是无向连通图,V1?V且 V1≠?，
满足：
⑴ 删除 V1的所有结点,得到的子图是不连通的 。
⑵ 删除 V1的任何真子集,得到的子图是连通的 。
则称 V1是 G的点割集 。 如果某一个结点组成了点割集,则称该点为割点 。
在图 9.16中，
b,d?,?c?,?e?都是点割集，结点 c和结点 e都是割点。虽然删除结点 a和 c图成为不连通的，但因?c?是?a,c?的真子集，所以?a,c?不是点割集。
第 9章 图论定义 9.3.7 设 G=?V,E?是无向连通图,如果 G不是完全图,k(G)=min?|V1|?V1是 G的点割集?称为图 G的点连通度 。
如果 G是完全图,规定 n阶无向完全图 Kn的点连通度为 n–1，
即 k(Kn)=n–1。 规定不连通图 G的点连通度为 0。 即 k(G)= 0。
图 9.16是无向连通图，但不是完全图，存在割点 c和 e，
所以点连通度是 1。
无向连通图的点连通度的物理意义是：要使 G成为不连通的最少要删除的结点数。图 9.16的点连通度是 1，最少删除一个结点，图成为不连通的，例如删除结点 c或结点 e。
第 9章 图论定义 9.3.8 设 G=?V,E?是无向连通图,E1?E且 E1≠?，
满足：
⑴删除 E1的所有边，得到的子图是不连通的。
⑵删除 E1的任何真子集，得到的子图是连通的。
则称 E1是 G的边割集。如果某一条边组成了边割集，则称该边为割边或桥。
在图 9.16中，集合?(c,e)?,?(e,f)?,?(a,b),(d,c)?和
(a,d),(b,c)?都是 G的边割集，无向边 (c,e)和 (e,f)为割边。
虽然删除边 (a,d),(a,b)和 (d,c)图成为不连通的，但因集合?(a,b),(d,c)?是集合?(a,d),(a,b),(d,c)?的真子集，所以
(a,d),(a,b),(d,c)?不是边割集。
第 9章 图论定义 9.3.9 设 G=?V,E?是无向连通图,如果 G是非平凡图,?(G)=min?|E1|?E1是 G的边割集?称为 G的边连通度 。
如果 G是平凡图,规定 G的边连通度为 0。 规定不连通图 G
的边连通度为 0,即?(G)=0。
图 9.16是无向连通图,但不是平凡图,存在割边 (c,e)
和 (e,f),所以,它的边连通度是 1。
无向连通图的边连通度的物理意义是：要使 G成为不连通的最少要删除的边数 。 图 9.16的边连通度是 1,最少删除一条边,图就会 成为不连通的,例如删除 割边 (c,e)或
(e,f)。
无向图 G的点连通度 k(G)、边连通度?(G)和最小度?
(G)有下列的关系：
第 9章 图论定理 9.3.1 设 G=?V,E?为任意无向图,则
k(G)≤?(G)≤?(G)
证明,⑴ 如果 G是不连通的,由点连通度和边连通度的定义有 k(G)=?(G)=0,所以
k(G)≤?(G)≤?(G)
⑵ 如果 G是连通图 。
① 先证明?(G)≤?(G)
如果 G是平凡图,?(G)=0≤?(G),即?(G)≤?(G)
如果 G是非平凡图,设 n=?(G)=min?deg(v)|v?V?,则存在 G的一个结点 v,它关联了 n条边,而其它结点关联的边数大于等于 n,将 v关联的这 n条边删除,G成为不连通的 。
从而这 n条边或这 n条边中的几条边组成一个边割集,即存在一个边割集的基数小于等于 n,所以第 9章 图论
min?|E 1| | E 1是 G的边割集?≤n=min?deg(v) | v?V?,即
(G)≤?(G)
② 再证 k(G)≤?(G)
设?(G)=1,G有一条割边,此边的任一端点是割点,
k(G)=1。 所以 k(G)≤?(G)成立 。
设?(G)≥2,则可删除某?(G)条边,使 G成为不连通的,
而删除其中的?(G)–1条边,它仍然是连通的且有一个桥,
设该桥为 e=(u,v)。 对这?(G)–1条边选取一个不同于 u,也不同于 v的端点,把这些端点删除,则必至少删除了这
(G)–1条边 。 若这样产生的图是不连通的,则 k(G)≤?(G)–
1≤?(G)。 若这样产生的图是连通的,则 e=(u,v)仍是桥 。 此时再删除 u或 v,就必产生了一个不连通图,故 k(G)≤?(G)
由⑴和⑵得 k(G)≤?(G)≤?(G)
第 9章 图论图 9.17是无向连通图,点连通度 k(G)=1,边连通度
(G)=2,最小度?(G)=3,此图满足 k(G)≤?(G)≤?(G)。
第 9章 图论定理 9.3.2 在无向连通图 G中,结点 v是割点的充分必要条件是存在两个结点 u和 w,使结点 u和 w之间的每一条路都通过 v。
证明,设 v是割点,证明存在两个结点 u和 w,使结点 u
和 w之间的每一条路都通过 v。
v是割点,删除 v得 G′,G′至少包含两个连通分支,设其中的两个为 G1=?V1,E1?和 G2=?V2,E2?,?u?V1,?w?V2，
因为 G连通,在 G中 u和 w之间必有路,设 L是它们之间任意一条路 。 在 G′中,由于 u和 w属于两个不同连通分支,所以,u和 w之间必没有路 。 故 L必通过 v。
设存在两个结点 u和 w,使结点 u和 w之间的每一条路都通过 v,证明 v是割点 。
删除 v得子图 G′，因为结点 u和 w之间的每一条路都通过 v，所以在 G′中结点 u和 w之间必无路，即结点 u和 w不连通。由连通图的定义知,G′是不连通的，故 v是 G的割点。
第 9章 图论
9.3.2有向连通图定义 9.3.10 在有向图 G中,结点 u到结点 v存在一条路,
则称结点 u到结点 v可达 。 记为 u→ v。 如果 u到 v可达且 v到 u
也可达,称结点 u和结点 v相互可达 。 记为 u? v。 规定,G
中任何结点 v自己到自己可达,即 v? v。
定义 9.3.11 在有向图 G=?V,E?中,u?V,v?V,若结点
u到结点 v可达,u到 v最短路的长称为结点 u到结点 v的距离 。
记为 d?u,v?。 若 u到 v不可达,规定,u到 v的距离为 ∞。 即
d?u,v?=∞。
对于有向图 G中的任意结点 u,v和 w,结点间的距离有以下的性质：
① d?u,v?≥0
② d?u,u?=0
③ d?u,v?＋ d?v,w?≥ d?u,w?
第 9章 图论定义 9.3.12 在简单有向图 G中,对于任意两个结点 u和 v，
⑴ 如果结点 u到结点 v可达或结点 v到结点 u可达,则称 G
为单向 (侧 )连通的 。
⑵ 如果结点 u和结点 v互相可达,则称 G为强连通的 。
⑶ 如果略去方向得到的无向图是连通的,则称 G为弱连通的 。
在图 9.18中,(a)是强连通的,单向 (侧 )连通的和弱连通的 。 (b)是单向 (侧 )连通的和弱连通的,但不是强连通的 。 (c)
是弱连通的,但不是单向 (侧 )连通的,也不是强连通的 。
第 9章 图论一般地说，若有向图 G是强连通的，则必是单向 (侧 )连通的和弱连通的；若有向图 G是单向 (侧 )连通的，则必是弱连通的。反之不真。
第 9章 图论定理 9.3.3 一个有向图 G是强连通的充分必要条件是 G中有一个回路至少包含 G的每个结点一次 。
证明,设 G中有一个回路至少包含 G的每个结点一次,
下证 G是强连通的 。
G中有一个回路至少包含每个结点一次,则 G中的任意两个结点通过回路互相可达 。 所以 G是强连通的 。
设 G是强连通的,下证 G中有一个回路至少包含 G的每个结点一次 。
若不然,存在结点 v不在 G的任何回路上,则 v与其它任何结点不能互相可达,这与 G是强连通的矛盾 。 故 G中有一个回路至少包含 G的每个结点一次 。
第 9章 图论定理 9.3.4 一个有向图 G是单向连通的充分必要条件是
G中有一个路至少包含每个结点一次 。
证明略 。
定义 9.3.13 在简单有向图 G中,具有强 (单向,弱 )连通性质的最大子图叫做强 (单向,弱 )分图 。
在图 9.19(a)中,由?v1,v2,v3,v4?导出的子图是强分图,
v5?导出的子图也是强分图 。 由?v1,v2,v3,v4,v5?导出的子图是单向分图,也是弱分图 。
在图 9.19 (b) 中,?v1?,?v2?,?v3?,?v4?导出的子图是强分图,?v1,v2,v3?，和?v1,v3,v4?导出的子图是单向分图，
v1,v2,v3,v4?导出了弱分图。
第 9章 图论第 9章 图论定理 9.3.5 在有向图 G=?V,E?中,每一个结点位于且只位于一个强分图中 。
证明,⑴?v?V,令 V1是 G中所有与 v互相可达的结点组成的集合,当然 v?V1,V1导出的子图是 G的强分图 。 故
G的每一个结点位于一个强分图中 。
⑵设 G1=?V1,E1?和 G2=?V2,E2?是 G的两个强分图，设
v?V1且 v?V2，则 v与 G1中的所有结点相互可达且与 G2中的所有结点相互可达。于是 G1中的结点与 G2中的结点通过 v
相互可达。这与 G1和 G2是强分图相矛盾。故 G的每一个结点只位于一个强分图中。
返回章目录第 9章 图论
9.4图的矩阵表示定义 9.4.1 设 G=?V,E?是一个简单图,V=?v1,v2,?,vn?
A(G)=(aij) n× n
其中：
i,j=1,?,n
称 A(G)为 G的邻接矩阵 。 简记为 A。
0
1
jivv
vva
ji
ji
ij
无边或到有边到第 9章 图论
0111
1010
1101
1010
)( GA
例如图 9.22的邻接矩阵为：
第 9章 图论又如图 9.23(a)的邻接矩阵为：
0001
1011
1100
0010
)( GA
第 9章 图论邻接矩阵具有以下性质：
①邻接矩阵的元素全是 0或 1。这样的矩阵叫布尔矩阵。
邻接矩阵是布尔矩阵。
②无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。
③邻接矩阵与结点在图中标定次序有关。例如图 9.23(a)
的邻接矩阵是 A(G)，若将图 9.23(a)中的接点 v1和 v2的标定次序调换，得到图 9.23(b)，图 9.23(b)的邻接矩阵是 A′(G)。
0010
1011
0001
1100
)( GA
第 9章 图论考察 A(G)和 A′(G)发现，先将 A(G)的第一行与第二行对调，再将第一列与第二列对调可得到 A′(G)。称 A′(G)与 A(G)
是置换等价的。
一般地说，把 n阶方阵 A的某些行对调，再把相应的列做同样的对调，得到一个新的 n阶方阵 A′，则称 A′与 A是置换等价的。可以证明置换等价是 n阶布尔方阵集合上的等价关系。
虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。
④对有向图来说，邻接矩阵 A(G)的第 i行 1的个数是 vi的出度,第 j列 1的个数是 vj的入度。
⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。
第 9章 图论定理 9.4.1 设 A(G)是图 G的邻接矩阵,A(G)k=A(G)A(G)k-1，
A(G)k的第 i行，第 j列元素 等于从 vi到 vj长度为 k的路的条数。
其中 为 vi到自身长度为 k的回路数。
推论 设 G=?V,E?是 n阶简单有向图,A是有向图 G的邻接矩阵,Bk=A＋ A2＋? ＋ Ak,Bk=( )n× n，则 是 G中由 vi到 vj
长度小于等于 k的路的条数。 是 G中长度小于等于 k的路的总条数。 是 G中长度小于等于 k的回路数。
【 例 9.4】 设 G=?V,E?为简单有向图，图形如图 9.24，写出 G的邻接矩阵 A，算出 A2,A3,A4且确定 v1到 v2有多少条长度为 3的路? v1到 v3有多少条长度为 2的路? v2到自身长度为 3
和长度为 4的回路各多少条?
kija
kiia
kijb
n
i
n
j
kijb
1 1
n
i
kiib
1
kijb
第 9章 图论解,邻接矩阵 A和 A2,A3,A4如下：
01000
10000
00010
00101
00010
A
10000
01000
00101
00020
00101
2
A
第 9章 图论
01000
10000
00020
00202
00020
3
A
10000
01000
00202
00040
00202
4
A
=2，所以 v1到 v2长度为 3的路有 2条，它们分别是：
v1v2v1v2和 v1v2v3v2。
=1，所以 v1到 v3长度为 2的路有 1条,v1v2v3。
=0,v2到自身无长度为 3的回路。
=4,v2到自身有 4条长度为 4的回路，它们分别是：
v2v1v2v1v2,v2v3v2v3v2,v2v3v2v1v2和 v2v1v2v3v2。
312a
213a
322a
422a
第 9章 图论定义 9.4.2 设 G=?V,E?是简单有向图,V=?v1,v2,?,vn?
P(G)=(pij)n× n
其中,pij =
i,j=1,?,n
称 P(G)为 G的可达性矩阵。简记为 P。
在定义 9.3.10中，规定了有向图的任何结点自己和自己可达。所以可达性矩阵 P(G)的主对角线元素全为 1。
不可达到可达到
ji
ji
vv
vv
0
1
第 9章 图论设 G=?V,E?是 n阶简单有向图,V=?v1,v2,?,vn?,由可达性矩阵的定义知,当 i≠j时,如果 vi到 vj有路,则 pij=1；如果
vi到 vj无路,则 pij=0；又由定理 9.2.1知,如果 vi到 vj有路,则必存在长度小于等于 n–1的路 。 依据定理 9.4.1的推论,如下计算图 G的可达性矩阵 P：
先计算 Bn–1=A＋ A2＋? ＋ An–1,设 Bn–1=( )n× n。
若 ≠0,则令 pij=1,若 =0,则令 pij =0,i,j=1,?,n。
再令 pii=1,i=1,?,n。 就得到了图 G的可达性矩阵 P。
令 A0为 n阶单位阵,则上述算法也可以改进为：
计算 Cn–1= A0＋ Bn–1=A0＋ A＋ A2＋? ＋ An-1，
设 Cn–1=( )n× n。 若 ≠0,则令 pij=1，
若 =0,则令 pij=0,i,j=1,?,n。
1?nijb
1?nijb 1?nijb
1?nijc 1?nijc
1?nijc
第 9章 图论使用上述方法,计算例 9.4中图 G的可达性矩阵,
C4= A0＋ A＋ A2＋ A3＋ A4 =
31000
13000
00433
00373
00334
11000
11000
00111
00111
00111
P=
第 9章 图论计算简单有向图 G的可达性矩阵 P,还可以用下述方法：
设 A是 G的邻接矩阵,令 A=(aij)n× n,A(k) =( )n× n,A0为
n阶单位阵 。
A(2)=A°A,其中 =(ai1∧ a1j)∨ (ai2∧ a2j)∨? ∨ (ain∧ anj)
i,j=1,?,n。
A(3)=A°A(2),其中 (ai1∧ )∨? ∨ (ain∧ )
i,j=1,?,n。
P= A0∨ A∨ A(2)∨ A(3)∨? ∨ A(n–1)。 其中,运算 ∨ 是矩阵对应元素的析取 。
可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。
)(kija
)2(ija
)3(ija )2(
1ja )2(nja
第 9章 图论定义 9.4.3 设 G=?V,E?是简单无向图,V=?v1,v2,?,vn?
P(G)=( pij) n× n
其中：
i,j=1,?,n
称 P(G)为 G的连通矩阵。简记为 P。
无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。
0
1
不连通与连通与
ji
ji
ij vv
vvp
第 9章 图论定义 9.4.4 设 G=?V,E?是无向图,V=?v1,v2,?,vp?，
E=?e1,e2,?,eq?
M(G)=( mij) p× q
其中：
i=1,?,p,j=1,?,q
称 M(G)为无向图 G的完全关联矩阵。简记为 M。
0
1
否则关联与 ji
ij
evm
第 9章 图论例如图 9.25的完全关联矩阵为：
1000
1100
0011
0111
M(G) =
第 9章 图论设 G=?V,E?是无向图,G的完全关联矩阵 M(G)有以下的性质：
① 每列元素之和均为 2。 这说明每条边关联两个结点 。
② 每行元素之和是对应结点的度数 。
③ 所有元素之和是图各结点度数的和,也是边数的 2倍 。
④ 两列相同,则对应的两个边是平行边 。
⑤ 某行元素全为零,则对应结点为孤立点 。
定义 9.4.5 设 G=?V,E?是有向图,V=?v1,v2,?,vp?，
E=?e1,e2,?,eq?
M(G)=( mij) p× q
其中,i=1,?,p,j=1,?,q
称 M(G)为有向图 G的完全关联矩阵。简记为 M。
不关联与的终点是的始点是
ji
ji
ji
ij
ev
ev
ev
m
0
1
1
第 9章 图论图 9.26的完全关联矩阵为：
M(G)=
11100
11000
00111
00011
第 9章 图论设 G=?V,E?是有向图,G的完全关联矩阵 M(G)有以下的性质：
① 每列有一个 1和一个 -1,这说明每条有向边有一个始点和一个终点 。
② 每行 1的个数是对应结点的出度,-1的个数是对应结点的入度 。
③ 所有元素之和是 0,这说明所有结点出度的和等于所有结点入度的和 。
④两列相同，则对应的两边是平行边。
返回章目录第 9章 图论
9.5欧拉图和汉密尔顿图
9.5.1欧拉图定义 9.5.1 在无孤立结点的图 G(有向图或无向图 )中,如果存在一条路经过每一条边一次且仅一次,则称该路为欧拉路 。 如果存在一条回路经过每一条边一次且仅一次,则称该回路为欧拉回路 。 具有欧拉回路的图称为欧拉图 。
定理 9.5.1 无向图 G具有一条欧拉路当且仅当 G是连通的且有零个或两个奇度结点 。
证明,设 G具有一条欧拉路,下证 G是连通的且有零个或两个奇度结点 。
设 G中有一条欧拉路 L,v0e1v1e2v2? ekvk,该路经过 G的每一条边 。 因为 G中无孤立结点,所以该路经过 G的所有结点,即 G的所有结点都在该路上 。 故 G中任意两个结点连通,
从而 G是连通图 。
第 9章 图论设 vi是图 G的任意结点,若 vi不是 L的端点,每当沿 L经过
vi一次都经过该结点关联的两条边,为该结点的度数增加 2。
由于 G的每一条边都在该路上,且不重复,所以 vi的度数必为偶数 。 若 vi是 L的端点 v0,当 v0=vk时,则 v0和 vk的度数也为偶数,即 G中无奇度结点；当 v0≠vk时,则 v0和 vk的度数均为奇数,
即 G中有两个奇度结点 。
设 G是连通的且有零个或两个奇度结点,下证 G具有一条欧拉路 。
设 G是连通图,有零个或两个奇度结点,用下述方法构造一条欧拉路：
① 若 G中有两个奇度结点,则从其中的一个 v0开始构造一条简单路 。
从 v0出发经关联边 e1进入 v1,若 v1是偶数度结点,则必可以由 v1经关联边 e2进入 v2。 如此下去,每边只取一次 。 由于 G
是连通图,必可到达另一个奇度结点 vk,从而得到一条简单路 L1,v0e1v1e2v2? ekvk。
第 9章 图论若 G中无奇度结点,则从任意结点 v0出发,用上述方法必可回到结点 v0,得到一条简单回路 L1,v0e1v1e2v2? v0。
② 若 L1经过 G的所有边,则 L1就是欧拉路 。
③ 否则,在 G中删除 L1,得子图 G′,则 G′中的每一个结点的度数为偶数 。 因为 G是连通图,故 L1和 G′至少有一个结点 vi重合,在 G′中由 vi出发重复 ①,得到简单回路 L2。
④ 若 L1与 L2组合在一起恰是 G,则得到了欧拉路,否则,
重复 ③ 可得到简单回路 L3。
以此类推直到得到一条经过 G中所有边的欧拉路 。
推论 无向图 G具有一条欧拉回路当且仅当 G是连通的且所有结点都是偶度的 。
这个推论说明,无向图 G是欧拉图当且仅当 G是连通的且所有结点都是偶度的 。
第 9章 图论图 9.30(a)的每一个结点的度数都是偶数 2，所以 (a)中有一个欧拉回路，是欧拉图；在图 9.30 (b)中有两个结点的度数是奇数 3，故 (b)中有一个欧拉路，但没有欧拉回路，
不是欧拉图；在图 9.30 (c)中四个结点的度数都是奇数 3，
(c)中没有欧拉路，更没有欧拉回路，不是欧拉图。
第 9章 图论定理 9.5.2 有向图 G具有一条欧拉回路当且仅当 G是强连通的且每个结点的入度等于出度 。
这个定理说明,有向图 G是欧拉图的充分必要条件是 G
是强连通的且每个结点的入度等于出度 。
定理 9.5.3 有向图 G具有一条欧拉路当且仅当 G是单向连通的且除了两个结点外，每个结点的入度等于出度，而在这两个结点中，一个结点入度比出度大 1，另一个结点入度比出度小 1。
这两个定理可以看作定理 9.5.1和推论的推广。因为对于有向图的任意一个结点，如果入度与出度相等，则该结点的度数为偶数。若入度与出度之差为 1时，则该结点的度数为奇数。因此定理 9.5.2和定理 9.5.3的证明与定理 9.5.1的证明类似 。
第 9章 图论图 9.31(a)是强连通的且每一个结点的入度等于出度，都等于 1，所以 (a)中有一个欧拉回路，是欧拉图；图 9.31 (b)是单向连通的且有两个结点入度与出度相等，有两个结点入度与出度不相等，其中一个结点入度比出度大 1，另一个结点入度比出度小 1。故有一个欧拉路，但没有欧拉回路，不是欧拉图；图 9.31(c)的四个结点入度与出度都不相等，没有欧拉路，更没有欧拉回路。
第 9章 图论哥尼斯堡七桥问题从前,一个称为哥尼斯堡城的城市有一条横贯全市的普雷格尔河,河中有两个小岛,用七座桥将岛和岛,河岸和岛连接起来,如图 9.32所示 。 18世纪中叶,该城市的人们提出了一个问题：能否不重复的走完七桥,最后回到原地 。
城中的很多人试图解决这个问题,然而试验者都以失败告终 。 1736年瑞士的数学家列昂哈德?欧拉 (Leonhard Euler)发表了一篇论文,哥尼斯堡七桥问题,,这篇论文的基本内容就是定理 9.5.1。 在这篇论文中第一次论证了这个问题是无解的 。 他将河岸和岛抽象成图的结点,而把桥画成相应的连接边,如图 9.33所示 。 于是,不重复的走完七桥,最后回到原地,等价于图中存在一条回路,经过每一条边一次且仅一次,即图中存在欧拉回路 。 因为图中的四个结点的度数都是奇数 。 所以图中不存在欧拉回路 。
第 9章 图论第 9章 图论
9.5.2汉密尔顿图一个与欧拉回路和欧拉图非常类似的问题是汉密尔顿回路和汉密尔顿图问题。它是由爱尔兰数学家威廉?汉密尔顿爵士 (Sir Willian Hamilton)于 1859首先提出的。
定义 9.5.2 在图 G(有向图或无向图 )中，如果存在一条路，经过每个结点一次且仅一次，则该路称为汉密尔顿路。
如果存在一条回路，经过每个结点一次且仅一次，则称该路为汉密尔顿回路。具有汉密尔顿回路的图称为汉密尔顿图。
与欧拉图不同，判断一个图是否为汉密尔顿图至今还没有一个简单的充分必要条件，只有一些必要条件和充分条件。判断一个图是汉密尔顿图的充分必要条件是图论中尚未解决的基本难题之一。下面介绍一些关于汉密尔顿图的必要条件和充分条件。
第 9章 图论先给出一个约定：设 G=?V,E?是图,S?V，用 G-S表示从图 G中删除 S中的所有结点所得的子图。
定理 9.5.4 设无向图 G=?V,E?是汉密尔顿图,S是 V的任意非空子集,则 W(G-S)≤|S|。
证明,设 C是 G的一条汉密尔顿回路,?v1?S,则 C-
v1?(从 C中删除结点 v1)是一条路或回路,路上各结点相互连通 。 再删除 S中的另一个结点 v2,则 W(C-?v1,v2?)≤2,所以
W(C-?v1,v2?)≤|?v1,v2?|。 由归纳法可得 W(C-S)≤|S|。
又因为 C-S是 G-S的生成子图，因而 W(G–S)≤ W(C–S)，
所以有 W(G–S)≤ |S|。
本定理的条件是汉密尔顿图的必要条件,而不是充分条件 。 利用该定理可以证明一个图不是汉密尔顿图,即满足此定理条件的图不一定是汉密尔顿图,而不满足此定理条件的图一定不是汉密尔顿图 。
第 9章 图论例如,图 9.34叫彼得松图 。 彼得松图满足定理 9.5.4的条件,但可以验证它不是汉密尔顿图 。
又如,在图 9.35中,令 S=?a,b?,则 W(G-S)=3,|S|=2，
故 W(G–S)≤|S|不成立 。 所以该图不是汉密尔顿图 。
第 9章 图论
【 例 9.5】 设 G是无向连通图,证明：如果 G中有割点或桥,则 G一定不是汉密尔顿图 。
证明,设 v是割点 。 删除结点 v,图成为不连通的,且至少有两个连通分支 。 令 S=?v?,则 W(G–S)≥2＞ 1=|S|,即
W(G–S)＞ |S|。 依据定理 9.5.4,G不是汉密尔顿图 。
如果 G中有桥，则该桥的一个端点是割点。可以归结为
G中有割点的情况。所以 G也不是汉密尔顿图。
定理 9.5.5 设 G=?V,E?是 n阶无向简单图，如果 G中每一对结点度数的和大于等于 n–1，则在 G中存在一条汉密尔顿路。
推论 设 G=?V,E?是 n阶无向简单图，如果 G中每一对结点度数的和大于等于 n，则在 G中存在一条汉密尔顿回路。
第 9章 图论定理 9.5.5及其推论给出了图中存在一条汉密尔顿路和汉密尔顿回路的充分条件，而不是必要条件。例如，图
9.37(a)有 6个结点，任意两个结点度数的和小于 5，但图中存在一条汉密尔顿路。又如图图 9.37 (b)也有 6个结点，任意两个结点度数的和小于 6，但图中存在一条汉密尔顿回路。
第 9章 图论
【 例 9.6】 设 G=?V,E?是一个无向简单图,|V|=n,|E|=m，
设 m＞ (n–1)(n–2)。 试证明 G中存在一条汉密尔顿路 。
证明,先证明图 G中任意两个不同的结点度数之和大于等于 n-1,然后利用定理 9.5.5即得本例要证的结果 。
用反证法,设图 G中存在两个结点 v1和 v2,使得 deg(v1)
＋ deg(v2)＜ n–1,即 deg(v1)＋ deg(v2)≤n–2。 删去结点 v1和 v2后,
得到图 G′,G′是具有 n-2个结点的无向简单图 。 设 G′的边数为 m′,则 m′≥m-(n-2)＞ (n-1)(n-2)-(n-2)=(n-2)(n-3)，
即 m′＞ (n–2)(n–3)
另一方面,G′是具有 n–2个结点的无向简单图,它最多有 (n–2)(n–3)条边 。 所以 m′≤(n–2)(n–3)。
由此得出矛盾。所以 deg(v1)＋ deg(v2)≥ n–1，由定理
9.5.5得 G中存在一条汉密尔顿路。
第 9章 图论
【 例 9.7】 某地有 5个风景点,若每个风景点均有两条道路与其它点相通,问是否可经过每个风景点恰好一次的游完这 5处?
解,因为有 5个风景点,故可看成一个有 5个结点的无向图,其中每处均有两条路与其它结点相通,所以 deg(vi)=2，
i=1,?,5。 故对任意两点 vi,vj均有
deg(vi)+deg(vj)=2+2=4=5-1
由定理 9.5.5可知此图中一定有一条汉密尔顿路,本题有解 。
定义 9.5.3 给定图 G=?V,E?有 n个结点,若将图 G中度数之和至少是 n的非邻接结点连接起来得图 G′,对图 G′重复上述步骤,直到不再有这样的结点对存在为止,所得到的图称为原图 G的闭包,记作 C(G)。
第 9章 图论例如图 9.38给出了有六个结点的图 G构造其闭包的过程。
在这个例子中 C(G)是完全图。一般情况下,C(G)也可能不是完全图。
第 9章 图论定理 9.5.6 设 G是简单图,G是汉密尔顿图当且仅当 G的闭包是汉密尔顿图 。
证明略 。
下面通过一个例子,介绍一个判别汉密尔顿路不存在的方法 。
【 例 9.8】 图 G如图 9.39所示，证明 G中没有汉密尔顿路。
证明,任取一结点 a用 A标记,所有与它相邻接的结点标记为 B。 继续不断地用 A标记所有邻接于 B的结点,再用 B
标记所有邻接于 A的结点,直到所有的结点标记完毕 。
如果图中有一条汉密尔顿路，那么它必交替通过标记 A
的结点和标记 B的结点，故或者标记 A的结点与标记 B的结点数一样，或者两者相差为 1。然而本例有 3个结点标记 A，
5个结点标记 B，它们相差为 2，所以该图不存在汉密尔顿路。
第 9章 图论返回章目录第 9章 图论
9.6 树树是比较简单而又特别重要的图，它在计算机科学和技术中有非常广泛的应用。
9.6.1无向树定义 9.6.1 连通无回路的无向图称为无向树,简称树 。
常用 T表示 。 在树中,度数为 1的结点称为树叶,度数大于 1
的结点称为分支点或内点 。 规定,平凡图也是树,叫平凡树 。
定义 9.6.2 若无向图至少有两个连通分支,每一个连通分支是树,则此无向图称为森林 。
无向树有很多性质,有些性质是树的充分必要条件,
可以看作树的等价定义 。 下面的定理是树的 6个充分必要条件,每一个都可以作为树的定义使用 。
第 9章 图论定理 9.6.1 设 G=?V,E?是无向图,|V|=n,|E|=m,则下列各命题是等价的：
① G是树 。
② G中每一对结点之间存在惟一的路 。
③ G中无回路且 m=n–1
④ G是连通的且 m=n–1
⑤ G是连通的且 G中任何边均为桥 。
⑥ G中无回路，但在任何两个不同的结点之间增加一个新边，得到一个惟一的含新边的回路。
证明,①?②
G是树,所以 G是连通的,?u?V,?v?V,u和 v之间存在一条路 。 若路不惟一,设 L1和 L2都是 u和 v之间的路,
则 L1和 L2组成了 G中的一个回路,与 G是树矛盾 。
第 9章 图论
②?③
先证 G中无回路 。 若 G中存在某个结点 v上的自回路,
u?V,由条件知 u到 v存在一条路 L1,u? v,因为 v上有自回路,所以 u到 v存在另一条路 L2,u? vv,这与 G中每一对结点之间存在惟一的路矛盾 。 若 G中存在长度大于等于 2的一条回路,则回路上两个结点之间存在不同的路 。 这与条件是矛盾的 。 所以 G中无回路 。
以下用归纳法证明 m=n–1。
当 n=1时,G为平凡图,m=0=1–1=n–1。 结论成立 。
设 n≤k时,结论成立 。 下证 n=k+1时,结论也成立 。
设 e=(u,v)是 G中的一条边,由于 G中无回路,所以
G-?e?(在 G删除边 e所得的子图 )有两个连通分支 G1和 G2，
设它们的结点数和边数分别为,m1,n1和 m2,n2。 于是有
n1≤k和 n2≤k,由归纳假设知,m1=n1–1和 m2=n2-1,m=m1＋
m2＋ 1=n1-1＋ n2-1＋ 1=n-1。
第 9章 图论
③?④ 只须证明 G是连通的 。 若不然,设 G有 t(t≥ 2)个连通分支 G1,G2,?,Gt,Gi中均无回路,都是树 。 由 ①
②?③ 可知,mi=ni–1,i=1,?,t。 于是 m=m1＋ m2＋? ＋ mt
=n1-1＋ n2-1＋? ＋ nt-1=n1＋ n2＋? ＋ nt-t=n–t,由于 t≥ 2，
这与 m=n–1矛盾 。 所以 G是连通图 。
④?⑤ 只须证明 G的每一条边均为桥 。 设 e是 G的任意边,删除 e得子图 G1,G1中的边数 m1=m-1,G1中的结点数
n1=n,m1=m–1=n-1-1=n-2=n1-2＜ n1-1,由习题 9.3的第 3题知 G1不是连通图,所以 e是桥 。
⑤?⑥ 由于 G中每一条边均为桥,因而 G中无回路 。 又因为 G连通,所以 G是树 。 由 ①?② 知,?u?V,?v?V，
u≠v,u与 v之间存在一条惟一的路 。 在 u与 v之间增加一条新边,就得到 G的一条回路,显然这条回路是惟一的 。
⑥?① 只须证明 G是连通的,?u?V,?v?V,u≠v,在
u与 v之间增加一条新边 (u,v)就产生 G的一个惟一的回路,故结点 u和结点 v连通 。 由于 u与 v是任意的,所以 G是连通图 。
第 9章 图论定理 9.6.2 在任何 n阶非平凡的无向树 T中至少有两片树叶 。
证明,设树 T有 x片树叶,由定理 9.1.1知,树 T中所有结点的度数之和 等于边数的 2倍 。 依据定理 9.6.1,在树 T中边数等于结点数减 1,即 n–1。 所以 2(n–1)= 。
另一方面,树中的分支点为 n-x个,每个分支点的度数大于等于 2,所有分支点度数之和大于等于 2(n–x),从而下式成立：
2(n-1)= ≥x+2(n-x)
解之,得 x≥2。
)deg(
1
n
i
iv
)deg(
1
n
i
iv
)deg(
1
n
i
iv
第 9章 图论
9.6.2生成树定义 9.6.3 设 G为无向图,若 G的生成子图是一棵树,
则该树称为 G的生成树 。 设 G的生成树为 T,则 T中的边称为树枝 。 G的不在生成树 T中的边称为弦 。 所有弦的集合称为生成树 T的补 。
在图 9.40中,(b)是 (a)的生成树,e2,e3,e5,e6是树枝，
e1,e4是弦,?e1,e4?是该生成树的补； (c)是 (a)的生成树，
e1,e2,e3,e6是树枝,e4,e5是弦,?e4,e5?是该生成树的补。
第 9章 图论定理 9.6.3 无向图 G具有生成树的充分必要条件是 G为连通图 。
证明,若无向图 G具有生成树,显然 G为连通图 。
以下证明若无向图 G为连通图,则 G具有生成树 。
若连通图 G无回路,则 G本身就是一棵生成树；若 G至少有一个回路,删除此回路的一边,得到子图 G1,它仍然连通,并与 G有相同结点集 。 若 G1无回路,则 G1就是一棵生成树；若 G1仍有一个回路,再删除 G1回路上的一边 。 重复上述过程,直至得到一个无回路的连通图,该图就是一棵生成树 。
由定理 9.6.3的证明过程可以看出，一个连通图可以有多个生成树。因为在取定一个回路后，就可以从中去掉任一条边，去掉的边不同，可能得到的生成树也不同。
例如，在图 9.40 (a)中相继删去边 e1和 e4，就得到了生成树 (b)。相继删去边 e4和 e5，就得到了生成树 (c)。
第 9章 图论推论 1 无向连通图 G有 n个结点和 m条边,则 m≥n–1
证明,由定理 9.6.3的证明知,G有生成树,设为 T。
|E(G)|=m,其中,E(G)是图 G的边构成的集合 。 依据定理
9.6.1,|E(T)|=n–1,其中,E(T)是树 T的边构成的集合 。 而
|E(G)|≥|E(T)|,所以 m≥n–1。
推论 2 在无向连通图中,一个回路和任何一棵生成树的补至少有一条公共边 。
证明,若有一个回路和一棵生成树的补无公共边,那么,这个回路包含在该生成树中,这与树的定义矛盾 。
推论 3 在无向连通图中,一个边割集和任何一棵生成树至少有一条公共边 。
证明,若有一个边割集和一棵生成树无公共边,那么,
删除这个边割集所得的子图必包含该生成树,从而该子图是连通的 。 这与边割集的定义矛盾 。
第 9章 图论设 G为无向连通图,有 n个结点和 m条边 。 T为 G的生成树,T有 n个结点和 n-1条边 。 所以要得到 G的一棵生成树,必须删除 G的 m-(n-1)=m–n＋ 1条边 。
定义 9.6.4 设 G为无向连通图,有 n个结点和 m条边 。
要得到一棵生成树,必须删除 G的 m–n＋ 1条边 。 m–n＋ 1
称为无向连通图 G的秩 。
无向连通图的秩，与生成树的选择无关。
定义 9.6.5 设 G=?V,E?为无向连通图,?e?E，对边 e
指定一个正数 C(e)，称正数 C(e)为边 e的权。设 T是 G的生成树,T的所有边 e的权之和称为树 T的权。记为 C(T)。若
G的每一条边都指定权，则称 G为赋权图。
在实际应用中，边的权可以是长度，运输量或其它费用。
第 9章 图论定义 9.6.6 在图 G的所有生成树中,权最小的生成树,
称为最小生成树 。
定理 9.6.4 设 G=?V,E?为无向连通赋权图,|E|=m,以下算法可以产生最小生成树 T：
先将图的 m条边按它的权由小到大的顺序排列为：
e1,e2,?,em。
① 取 e1到 T中 。
② 在尚未检查过的边中从左到右依次检查,若 ej与 T中的边不能构成回路,则取 ej到 T中,否则跳过 。
③反复做②，直到所有边都已检查。
第 9章 图论定理 9.6.4描述的算法叫克鲁斯克尔 (kruskal)算法 。
【 例 9.8】 图 9.41(a)给出了一个赋权图 G,用 kruskal算法求出 G的最小生成树 。
解,先将 m条边按权由小到大排列：
(v4,v5),(v1,v8),(v5,v7),(v6,v7),(v4,v6),(v5,v6)，
(v2,v7),(v2,v5),(v7,v8),(v2,v3),(v3,v4),(v1,v2)。
它们的权分别是：
3,4,5,6,6.5,7,7.5,8,10.5,11,12,13。
逐次取边：
(v4,v5),(v1,v8),(v5,v7),(v6,v7),(v2,v7),(v7,v8)，
(v2,v3)，
构成的生成树在图 9.41(b),这是 G的最小生成树 。 最小生成树 T的权 C(T)=3+4+5+6+7.5+10.5+11=47。
第 9章 图论第 9章 图论
9.6.3根树及其应用定义 9.6.7 一个有向图,略去方向后是树,则称这个有向图为有向树 。 如果一棵有向树恰有一个结点入度为 0,其余所有结点入度为 1,此有向树称为根树 。 在根树中,入度为 0的结点称为树根,出度为 0的结点称为树叶,出度不为 0
的结点称为分枝点或内点 。 从此定义可以看出,在根树中,
除了树叶都是分枝点或内点外,树根也是分枝点 。
9.42(a)是一棵有向树 。 (b)是一棵根树 。 v1是树根,
v3,v5,v6,v8是树叶,v1,v2,v4,v7是分枝点 。
第 9章 图论第 9章 图论定义 9.6.8设 T是一棵根树,由树根到 T的任意结点 v的路长叫做结点 v的层数 。 层数最大的结点的层数叫做该树的高 。
在图 9.42(b)中,v1的层数为 0,v2,v3,v4的层数为 1,v5,v6,
v7的层数为 2,v8的层数为 3,树的高为 3。
在根树中,各有向边的方向是一致的 。 所以画根树时,
可以省略各边的方向,并且常将树根画在最上方 。
定义 9.6.9 在根树中,若 vi到 vj有一条路,则称 vi是 vj的祖先,vj是 vi的后代 。 若?vi,vj?是根树中的一条边,则称 vi是 vj
的父亲,vj是 vi的儿子；同一个分枝点的儿子叫兄弟 。
定义 9.6.10 设 T是一棵根树,将 T中层数相同的结点标定一个次序,则称 T为有序树 。
定义 9.6.11 设 T是一棵根树,v是 T的任意结点,把 v和它的所有后代组成的结点集导出的图叫做 T的以 v为根的根子树,简称为以 v为根的子树,记为 Tv。
第 9章 图论定义 9.6.12 在根树中,若每个结点的出度小于或等于 m，
则称该树为 m叉树 。 在 m叉树中,若每个结点的出度恰等于 0
或 m,则称该树为完全 m叉树 。 在完全 m叉树中,若所有树叶层数相同,则称该树为正则 m叉树 。
当 m=2时,m叉树就是二叉树，完全 m叉树就是完全二叉树。在图 9.43中,(a),(b),(c)都是二叉树，其中 (b),(c)
是完全二叉树,(b)是正则二叉树。
二叉树的每一个结点 v至多有两棵根子树,分别称为 v的左子树和右子树 。 一般的,左子树画在 v的左下方,右子树画在 v的右下方 。 二叉树的每一个结点 v至多有两个儿子,左边的叫左儿子,右边的叫右儿子 。
第 9章 图论第 9章 图论定理 9.6.5 在完全 m叉树中,其树叶数为 t,分枝点数为 i,则 (m-1)i=t-1。
证明,由定理的条件知,该树有 i＋ t个结点,由定理
9.6.1知,该树边数为 i＋ t-1。 另一方面,由完全 m叉树定义知,该树出度的和为,mi,这也是该树的边数,于是有
mi=i＋ t-1。 整理后有 (m-1)i=t-1。
【 例 9.10】 设有一台计算机,它有一条加法指令,可计算 3个数的和 。 如果要计算 9个数的和,问至少要执行几次加法指令？
解,用 3个结点表示三个数,用它们的父结点表示它们的和 。 于是,问题就抽象为求一个完全 3叉树的分枝点有多少个 。 把 9看成树叶的个数,依据定理 9.6.5,(3-1)i=
9-1,i=4。 所以要执行 4次加法指令 。
第 9章 图论任何一棵有序根树都可用二叉树来表示,其方法如下：
① 从根结点开始,保留父亲和最左边儿子的连线,取消和其他儿子的连线,兄弟之间用从左到右的有向边连接 。
②选定二叉树的左儿子和右儿子如下：处于给定结点下方的结点作为该结点的左儿子，同一水平线上与给定结点右邻的结点作为该结点的右儿子。
图 9.44 (a)是一棵有序根树,做完 ① 得 (b),做完 ② 得 (c)，
(c)是一颗二叉树 。
第 9章 图论第 9章 图论图 9.45的 (a)也是一棵有序根树,按照上述方法,做完 ①
得 (b),做完 ② 得 (c),(c)是一颗二叉树 。
第 9章 图论用二叉树表示有序根树的方法可以推广到森林中去，其方法如下：
① 将森林中每一棵有序根树表示成二叉树 。
② 除最左边的二叉树外,
逐次将右边的二叉树作为左边的二叉树的根的右子树 。
例如图 9.44(a)中的有序根树和图 9.45(a)中的有序根树从左向右组成的一个森林,此森林转化为二叉树,只须将图
9.45(c)作为图 9.44(c)的根 v1的右子树就可以了 。 如图 9.46所示 。
第 9章 图论二叉树在计算机科学和技术中有广泛的应用,人们对它的研究也比较深入,有很多重要的结论,以下是最基本的几条 。
定义 9.6.13 在根树中,由树根到分枝点的路长叫做内部通路长 。 由树根到树叶的路长叫做外部通路长 。 若 v是根树的任意结点,树根到 v的路长叫做结点 v通路长,它是内部通路长或外部通路长,结点 v通路长记为 l(v)。
定理 9.6.6 若完全二叉树有 n个分枝点,内部通路长度的总和为 I,外部通路长度的总和为 E,则 E=I＋ 2n。
证明,对分枝点的数目 n进行归纳证明 。
① n=1,即一个分枝点,两片树叶,
如图 9.47所示 。 I=0,E=2=I＋ 2n。
第 9章 图论
② 设 n=k-1时,结论成立,即 Ek–1=Ik–1＋ 2(k-1)。 以下证明,当 n=k时,结论也成立,即 Ek=Ik＋ 2k。
设 Tk的分枝点为 k个,如果删除一个分支点 v,v的内部通路长为 l且 v的两个儿子是树叶,得到新树 Tk–1。 Tk–1与
Tk比较,减少了两片外部通路长为 l+1的树叶和一个内部通路长为 l的分枝点 。 增加了一个外部通路长为 l树叶 。 故在 Tk中,Ek= Ek–1＋ 2(l＋ 1)-l=Ek–1＋ l＋ 2,Ek–1=Ek-l-2。 Ik=
Ik–1＋ l,Ik–1= Ik-l。 代入归纳假设 Ek–1=Ik–1＋ 2(k–1)中,得
Ek-l-2=Ik-l＋ 2(k-1),整理后得 Ek= Ik＋ 2k。
这就证明 E=I＋ 2n。
第 9章 图论定义 9.6.14 设 T是一棵二叉树，有 t片树叶 v1,v2,?,
vt，分别带权 W!,W2,?,Wt，则称 T为赋权二叉树或带权二叉树。在赋权二叉树 T中,称为树 T的权。记为
W(T)。在所有有 t片树叶的二叉树中，如果 t片树叶分别带权
W!,W2,?,Wt，权 W(T)最小的二叉树，称为最优二叉树。
图 9.48中的三棵树 T1,T2和 T3都是带权 2,2,3,3,5的二叉树,它们的权分别是：
W(T1)=2× 2＋ 2× 2＋ 3× 3＋ 5× 3＋ 3× 2=38
W(T2)=3× 4＋ 5× 4＋ 3× 3＋ 2× 2＋ 2× 1=47
W(T3)=3× 3＋ 3× 3＋ 5× 2＋ 2× 2＋ 2× 2=36
以上三棵树都是带权 2,2,3,3,5的赋权二叉树，但不是最优树。
)(
1
i
t
i
i vlW?
第 9章 图论第 9章 图论下面介绍一种求最优树方法,叫 Huffman算法 。 它的基本思想是：
给定 t片树叶的权为 W1,W2,?,Wt且 W1≤W2≤? ≤Wt。
①连接权为 W1,W2的两片树叶，得一分枝点，其权为
W1＋ W2。
② 在 W1＋ W2,W3,?,Wt中选出两个最小的权,连接它们对应的结点 (不一定是树叶 ),得新分枝点及所带的权 。
③重复②，直到形成 t–1个分枝点,t片树叶为止。
第 9章 图论
【 例 9.11】 求带权 2,2,3,3,5的最优二叉树 T。
解,图 9.49给出了生成最优二叉树的过程 。 权 2,2,3，
3,5中最小的两个为 2和 2,2和 2代表两片树叶,得一分枝点,其权为 2＋ 2=4,如图 9.49 (a)所示 。 在 3,3,4,5中选出两个最小的权 3和 3,连接它们对应的结点,得新分枝点,
该结点所带权为 6,如图 9.49(b)所示 。 在 4,5,6中选出两个最小的权 4和 5,连接它们对应的结点,得新分枝点,该结点所带权为 9,如图 9.49(c)所示 。 最后,连接 6和 9对应的结点得新分枝点,该分枝点所带权为 15,如图 9.49(d)所示 。
(d)是最优树 。 最优树的权为：
W(T)=2× 3＋ 2× 3＋ 5× 2＋ 3× 2＋ 3× 2=34
第 9章 图论第 9章 图论二叉树的另一个应用是前缀码问题，下面介绍前缀码的基本概念和简单应用。
在通信中常用 0,1字符串表示英文字母,即用二进制数表示英文字母 。 最少用多少位二进制数就能表示 26个英文字母呢？ 1位二进制数可以表示 2=21个英文字母,两位二进制数可以表示 4=22个英文字母,,n位二进制数可以表示 2n个英文字母 。 如果规定,可以用 1位二进制数表示英文字母,也可以用两位二进制数表示英文字母 。 如果 1位和两位不足以表示 26个英文字母,可用 3位二进制数 。 再不够,
用 4位二进制数 。 这叫做用不定长二进制数表示英文字母 。
若用不定长二进制数表示 26个英文字母,至少需要多少位二进制数？ 设需要 i位二进制数,于是,下列的不等式成立：
26≤21＋ 22＋? ＋ 2i==2i+1–2
解之,得 i≥4
故用长度不超过 4位的二进制数足以表示 26个英文字母 。
第 9章 图论在英文中有些字母使用频率较高,另一些字母使用频率较低 。 为了减少通信中传递的信息量,人们希望用位数较少的二进制数表示频繁使用的字符,用位数较多的二进制数表示不常使用的字符 。 这样就会大大缩短信息串的总长度 。 但是也产生了一个问题：接收者如何将 0,1组成的长串,准确无误地分割成字母对应的 0,1序列呢？ 例如：
若用 00表示 e,用 01表示 t,用 0001表示 q。 当接收员接收到
0001时,就无法区分这是 et,还是 q。 为了解决这个问题,
引入前缀码的概念 。
如果 0,1序列 a是另一个 0,1序列 b左起的一个连续部分，则称 a是 b的前缀。例如 00是 0001的前缀,000也是
0001的前缀。而 01不是 0001的前缀。
第 9章 图论定义 9.6.15 给定一个 0,1序列的集合 。 若没有一个序列是另一个序列的前缀,则称该集合为前缀码 。
例如?1,00,011,0101,01001,01000?是前缀码 。 而
1,00,0101,0100,01001,01000?不是前缀码,
因为 0100是 01001的前缀,也是 01000的前缀 。
若使用前缀码中的 0,1序列表示英文字母,当接收者收到 0,1组成的长串时,就可以惟一的,准确无误地分割成字母对应的 0,1序列 。
定理 9.6.7 任意一个二叉树,可以产生惟一的前缀码 。
证明,在二叉树中,每一个分枝点引出的左侧边标记
0,右侧边标记 1。 由根结点到树叶的路经上各边的标记组成的 0,1序列作为该片树叶的标记 。 显然,没有一片树叶的标记是另一片树叶的标记的前缀 。 所有树叶的标记构成了一个前缀码 。
第 9章 图论
【 例 9.12】 求图
9.50 (a)所示的二叉树产生的前缀码 。
解,在图 9.50(a)
中，每一个分枝点引出的左侧边标记 0，
右侧边标记 1。由根结点到树叶的路经上各边的标记组成的 0、
1序列作为对应树叶的标记，如图 9.50(b)
所示。产生的前缀码为,?01,11,000,0010,
0011?
第 9章 图论定理 9.6.8 任意一个前缀码，都对应一个二叉树。
证明,给定了一个前缀码,设 h是其中最长序列的长度 。 画出一个高为 h的正则二叉树 。 按定理 9.6.7中描述的办法给各边标记 0或 1。 每一个结点对应一个 0,1序列,它是由根结点到该结点的路经上各边的标记组成的 。 如果某个 0,1序列是前缀码的元素,则标记该结点 。 将已标记结点的所有后代和该结点的射出边全部删除,得到了一个二叉树,再删除未加标记的树叶,就得到要求的二叉树 。
【 例 9.13】 设?1,01,000?是一前缀码,画出对应一个二叉树 。
解,画出一个高为 3的正则二叉树,给各边标记 0或 1，
每一个结点对应一个 0,1序列,如果某个 0,1序列是前缀码的元素,则标记该结点 。 如图 9.51(a)所示 。 将已标记结点的所有后代和该结点的射出边全部删除,再删除未加标记的树叶,得到要求的二叉树,如图 9.51 (b)所示 。
第 9章 图论返回章目录第 9章 图论
9.7二部图及匹配
9.7.1二部图定义 9.7.1 G=?V,E?是无向图,V1?V,V2?V,满足：
① V1∪ V2= V,V1∩V2=?。
② G中每一条边的两端点,一个属于 V1,另一个属于
V2。
则称 G为二部图或偶图,常记为 G=?V1,V2,E?,V1和 V2称为
G的互补的结点子集 。
二部图的每一条边的两个端点位于两个互补的结点子集,所以没有自回路 。 二部图是无自回路图 。
定义 9.7.2 设 G=?V1,V2,E?是二部图,|V1|=r,|V2|=s,若
V1的每个结点和 V2的所有结点邻接,则称 G为完全二部图或完全偶图,常记为 Kr,s。
在图 9.55中,(a),(b),(c)都是二部图,其中 (b),(c)是完全二部图 K1,3和 K3,3。
第 9章 图论第 9章 图论定理 9.7.1 设 G=?V,E?是无向图,G为二部图的充分必要条件是 G的所有回路的长均为偶数 。
证明,设 G是二部图,下证 G的所有回路的长均为偶数 。
设 G是二部图,则 V可以分成两个互补的结点子集 V1和
V2,每一个边的两个端点分别在 V1和 V2中,令
C,v0v1v2? vl-1v0
是 G中任一长度为 l的回路 。 不失一般性,设 v0?V1,则 v1?V2，
v2?V1,则 v3?V2, 。 由此可知,v2i?V1,v2i＋ 1?V2。 又因为 v0?V1,所以 vl-1?V2,l-1是奇数,l是偶数 。
设 G的所有回路的长均为偶数,下证 G是二部图 。
不妨设 G是连通图,否则可对每一个连通分支进行讨论 。
v0?V,定义 V的两个子集 V1和 V2为：
V1=?v | v?V∧ d(v0,v)为偶数?
V2=?v | v?V∧ d(v0,v)为奇数?
因为 G是连通图,任何结点与 v0之间都有路,d(v0,v)不是偶数就是奇数,所以 V1∪ V2=V,V1∩V2=?。
第 9章 图论下面证明 V1中任意两个结点不邻接,V2中任意两个结点也不邻接 。 若存在 vi?V1,vj?V1,vi 和 vj邻接,由于 d(v0,vi)
为偶数,v0到 vi有一条长为偶数的路 。 同样的道理,v0到 vj
也有一条长为偶数的路 。 这两条路和边 (vi,vj)构成一条回路,
其长度为奇数 。 与条件矛盾 。 所以 V1中任意两个结点不邻接 。 类似的可证,V2中任意两个结点也不邻接 。 于是 G为二部图 。
根据此定理，图 9.56中的 (a)和 (b)两个图是二部图。这比用定义判断要方便得多。画二部图时，习惯将互补的结点子集 V1和 V2分开画，画成图 9.55的形式。图 9.56中的 (a)，
(b)两个二部图，一定可以改画为图 9.55的形式。
第 9章 图论第 9章 图论
9.7.2匹配定义 9.7.3 设 G=?V1,V2,E?是二部图,M是 G中一些边组成的集合,如果 M中任意两条边都没有公共端点,则称 M为
G的一个匹配或对集 。 设 v是 G的结点,如果 v是 M中某条边的端点,则称 v为 M的饱和点 。 否则,称 v为 M的非饱和点 。
在图 9.57中,边集 M=?(a1,b2),(a2,b3),(a4,b1)?是一个匹配,
a1,a2,a4和 b1,b2,b3为 M的饱和点 。 结点 a3为 M的非饱和点 。
在图 9.57中，如果用 a1,a2,a3,a4表示 4位教师,b1,b2,b3表示三门待开的课程。当某位教师能开某门课程时，则把它们的对应结点用边连接起来。如果规定一个教师只能担任一门课程，那么匹配 M就表示了一种排课方案。为了使排课方案能最大限度地作到,各尽其能,,下面将引进最大匹配的概念。
第 9章 图论第 9章 图论定义 9.7.4 设 G=?V1,V2,E?是二部图,M是 G的一个匹配,如果对 G的任意匹配 M′,都有 |M′|≤|M|,则称 M为 G的最大匹配或最大对集 。
为了寻求二部图的最大匹配,以下引进交替路和可扩路两个概念 。
定义 9.7.5 设 G=?V1,V2,E?是二部图,M是 G的匹配,P
是 G中的一条路,如果 P是由 G中属于 M的边和不属于 M的边交替组成,则称 P为 G的 M交替路 。 如果交替路的始点和终点都是 M的非饱和点,则称为 G的 M可扩路 。
例如,在图 9.58中,匹配 M=?(a1,b2),(a2,b3),(a3,b5)?，
路
L1,a1b2a2b3a3,L2,a2b3a3b5a4，
L3,b1a3b5a4,L4,b1a1b2a2b3a3b5a4
都是 M交替路,其中后两条交替路 L3和 L4的始点和终点都是 M的非饱和点,所以这两条路是 M可扩路 。
第 9章 图论设 G=?V1,V2,E?是二部图,M是 G的一个匹配,P是 G中的一条 M可扩路 。 把 P中所有属于 M的边从 M中去掉,而把
P中所有不属于 M的边添加到 M中,得到一个新的边集 M′，
则 M′也是一个匹配,其所含边数比匹配 M所含的边数多 1。
第 9章 图论例如在图 9.58中,把 M可扩路 L3,b1a3b5a4中属于 M的边
(a3,b5) 从 M中去掉,而把 L3中不属于 M的边 (a3,b1)和 (a4,b5)
添加到 M中,得到一个新的边集 M′=?(a1,b2),(a2,b3),(a3,b1),
(a4,b5)?,显然 M′也是匹配且 M′的边数比 M的边数多 l,即
|M′|＝ |M|+1。 如图 9.59所示 。
第 9章 图论由此可见，利用可扩路可以增加匹配所含的边数。不断地寻求 G的可扩路，直到再也找不到新的可扩路，就可得到一个最大匹配。将这个结论写成下列的定理。
定理 9.7.2 设 G=?V1,V2,E?是二部图,M为 G的最大匹配的充分必要条件是 G中不存在 M可扩路 。
证明,设 M为 G的最大匹配,下证 G中不存在 M可扩路 。
如果 G中存在一条 M可扩路,则可以得到比 M的边数多 1
的匹配,所以 M不是最大匹配,矛盾 。 所以 G中不存在 M可扩路 。
设 G中不存在 M可扩路,下证 M为 G的最大匹配 。
设 M1是最大匹配,证明 |M|=|M1|。
考察属于 M而不属于 M1和属于 M1而不属于 M中的边,由这些边连同它们的端点一起构成 G的子图 H。
第 9章 图论在子图 H中,任一结点至多与 M中的一条边关联且与 M1
中一条边关联 。 因而任一结点的度数是 1或 2。 故 H的连通分支是一条路,或者是一个回路 。
如果 H的连通分支是一条路 P,则它是 M交替路,也是
M1交替路 。 如果 P的两个端点均与 M中的边关联,则 P是 M1
可扩路 。 由假设知,M1是最大匹配,所以,不存在 M1可扩路,得到矛盾 。 如果 P的两个端点均与 M1的边关联,那么 P
是一条 M可扩路与题设矛盾 。 故 P只能是一个端点与 M中的边关联,另一个端点与 M1中的边关联,这样 P中属于 M的边数与属于 M1的边数相等 。
如果 H的连通分支是一个回路,回路中的边交替地属于
M和 M1,因而属于 M的边数与属于 M1的边数相等 。
从上面可以看到,H中属于 M的边与属于 M1的边的数目相等 。 再加上既属于 M又属于 M1的边,可以得出,M中的边数与 M1中的边数相等 。 所以 M是最大匹配 。
第 9章 图论有了上面的准备以后,就可以进一步讨论如何在二部图中求最大匹配的问题 。
设 G=?V1,V2,E?是二部图,通常先作 G的一个匹配 M，
再看 V1中有没有 M的非饱和点 。 如果没有,那么 M肯定是最大匹配；如果有,就从这些点出发找 M可扩路 。 由 M可扩路作出一个更大的匹配 。 所以,在 G中求最大匹配的关键是寻找 M可扩路 。
寻找可扩路的一个有效方法是标记法，其基本思想如下：
设 G=?V1,V2,E?是二部图,在 G中作一个匹配 M,用 (*)
标记 V1中所有 M的非饱和点,然后交替地进行以下 ① 和 ② 两步：
① 选一个 V1的新标记过的结点,比如说 ai,用 (ai)标记不通过 M中的边与 ai邻接且尚未标记过的 V2的所有结点 。 对
V1所有新标记过的结点重复这一过程 。
第 9章 图论
② 选一个 V2的新标记过的结点，比如说 bi，用 (bi)标记通过 M中的边与 bi邻接且尚未标记过的 V1的所有结点。对 V2
所有新标记过的结点重复这一过程。
直至标记到一个 V2中的 M的非饱和点 。 从该结点倒向追踪到标记有 (*)的结点,就得到了一个 M可扩路 。 把 M可扩路中所有属于 M的边从 M中去掉,而把 M可扩路中所有不属于
M的边添加到 M中,得到一个新的匹配 M′且其所含边数比匹配 M所含的边数多 1。 对 M′重复上述过程,,直到 G中已不存在可扩路,此时的匹配就是最大匹配 。
第 9章 图论
【 例 9.15】 图 9.60是二部图,求其最大匹配 。
第 9章 图论解,取二部图图 9.60的一个匹配 M=?(a3,b1),(a5,b2)?。
用 (*)标记 V1中所有 M的非饱和点 a1,a2,a4。
① 选 V1的新标记过的结点 a1,用 (a1)标记不通过 M的边与 a1邻接且尚未标记过的 V2的结点 b1；类似地用 (a2)标记 b2。
② 选 V2的新标记过的结点 b1,用 (b1)标记通过 M的边与
b1邻接且尚未标记过的 V1的结点 a3；类似地用 (b2)标记 a5。
③ 选 V1的新标记过的结点 a3,因为不存在不通过 M的边与 a3邻接的 V2的结点,所以不用 (a3)标记 V2的结点；用 (a5)标记 b3或 b4,假定用 (a5)标记 b3。 如图 9.60所示 。
b3是 M的非饱和点,标记结束 。
从 b3倒向追踪到标记有 (*)的结点,就得到了 M可扩路：
a4b2a5b3或 a2b2a5b3,取后者 。 把 M可扩路 a2b2a5b3中的边
(a5,b2)从 M中去掉,而把 (a2,b2)和 (a5,b3)添加到 M中得到新的匹配 M′=?(a3,b1),(a2,b2),(a5,b3)?,如图 9.61所示 。
第 9章 图论第 9章 图论对匹配 M′=?(a3,b1),(a2,b2),(a5,b3)?再用标记法：
用 (*)标记 V1中所有 M′的非饱和点 a1和 a4。
① 选 V1的新标记过的结点 a1,用 (a1)标记不通过 M′的边与 a1邻接且尚未标记过的 V2的所有结点 b1；再用 (a4)标记 b2。
② 选 V2的新标记过的结点 b1,用 (b1)标记通过 M′的边与
b1邻接且尚未标记过的 V1的所有结点 a3；再用 (b2)标记 a2。
③ 选 V1的新标记过的结点 a2和 a3,V2中已无可标记的结点 。
图中已不存在可扩路,所以 M′就是最大匹配 。
第 9章 图论
【 例 9.16】 图 9.62是二部图，求其最大匹配。
第 9章 图论解,取二部图图 9.62的一个匹配 M=?(a2,b2),(a3,b3),
(a5,b5)?。 用 (*)标记 V1中所有 M的非饱和点 a1,a4。
① 选 V1的新标记过的结点 a1,用 (a1)标记 b2和 b3。
② 选 V2的新标记过的结点 b2和 b3,用 (b2)标记 a2,用 (b3)
标记 a3。
③ 选 V1的新标记过的结点 a2,用 (a2)标记 b1,b4和 b5。
由于 b1和 b4都是 M的非饱和点,说明找到了 M可扩路 。
它们是,a1b2a2b4和 a1b2a2b1。 选前者,把边 (a2,b2)从 M中去掉,而把 (a1,b2) 和 (a2,b4) 添加到 M 中,得到 新的 匹配
M′=?(a1,b2),(a2,b4),(a3,b3),(a5,b5)?,如图 9.63所示 。
对于匹配 M′=?(a1,b2),(a2,b4),(a3,b3),(a5,b5)?重复上述过程，已找不到 M′可扩路。所以 M′就是最大匹配。
第 9章 图论第 9章 图论定义 9.7.6 设 G=?V1,V2,E?是二部图,M是 G的最大匹配,若 |M|=min?|V1|,|V2|?,则称 M为 G中的一个完备匹配,
此时若 |V1|≤|V2|,则称 M为 V1到 V2的一个完备匹配 。
定理 9.7.3 设 G=?V1,V2,E?是二部图,|V1|≤|V2|,G中存在 V1到 V2的完备匹配的充分必要条件是 V1中每 k个结点
(k=1,2,?,|V1|)至少和 V2中 k个结点相邻接 (该条件称为相异性条件 )。
证明,设 |V1|=q,G中存在 V1到 V2 的完备匹配 M，
|M|=min?|V1|,|V2|?=|V1|=q,则 V1中 q结点和 V2中 q个相异结点相邻接 。 相异性条件成立 。
以下证明只要满足相异性条件,G中最大匹配一定是完备匹配 。 设 M为 G中一个最大匹配 。
第 9章 图论若 M不是完备匹配,必存在 v?V1为 M的非饱和点 。 且必存在 e?E1=E-M与 v关联 。 否则 v将是孤立点,这与相异性条件相矛盾 。 并且 V2中与 v相邻接的结点都是 M的饱和点,若存在 u?V2(与 v相邻 )为非饱和点,则 M′=M∪?(v,u)?也是匹配,
这显然与 M为最大匹配矛盾 。 考虑从 v出发的尽可能长的所有
M交替路,由于 M是最大匹配,由定理 9.7.2可知,这些 M交替路都不是 M可扩路,即每条路异于 v的端点一定是 M的饱和点,于是这些端点全在 V1中 。
S=?w| w?V1且 w 在从 v出发的交替路上?
T=?w| w?V2且 w 在从 v出发的交替路上?
由于各条交替路的两个端点全在 S中,所以 |S|=|T|＋ 1。
这正说明 V1中 |T|＋ 1个结点只与 V2中 |T|个结点相邻接,这矛盾于相异性条件 。 因而 V1中不可能存在 M的非饱和点,故 M是完备匹配 。
下一定理给出了二部图存在完备匹配的充分条件,它能很容易地判断二部图是否存在完备匹配 。
第 9章 图论定理 9.7.4 设 G=?V1,V2,E?是二部图,如果存在某一整数 t＞ 0,使得 V1中的每个结点至少关联 t条边,而 V2中的每个结点至多关联 t条边 。 则 G中存在 V1到 V2的完备匹配 。
证明,由定理的条件知,V1中任意 k个结点 (k=1,2,?,
|V1|)至少关联 kt条边 。 因为 V2中的每个结点至多关联 t条边,
所以这 kt条边至少关联于 V2中的 k个结点 。 于是二部图 G满足相异性条件 。 由定理 9.7.3可知,G有 V1到 V2的完备匹配 。
图 9.64中的二部图满足定理 9.7.4的条件。其中 t=3。因此在图 9.64中存在 V1到 V2的完备匹配。
第 9章 图论第 9章 图论下列例题给出了完备匹配的一个应用 。
【 例 9.17】 在某大学本科毕业生分配的供需洽谈会上,
有 n个毕业生可从 m(m≥n)个单位选择自己职业 。 已知每个毕业生至少愿意去 r(1≤r≤m)个单位去工作,而每个用人单位至多看中了 r–1个毕业生,愿意从中选择一名 。 问最多有多少个单位可以选择到满意的毕业生？ 写出判断过程 。
解,设 V1=?v| v为毕业生?,V2=?u| u为用人单位?，
E=?(v,u)| v愿意到 u去工作?，
则 G=?V1,V2,E?是二部图，由已知条件可知,?v?V1，
deg(v)≥r，而?u?V2,deg(u)≤r–1≤r，由此可知,G满足定理
9.7.4的条件，其中 t=r，因此有 V1到 V2的完备匹配。于是有 n
个单位，也最多有 n个单位可以选择到满意的毕业生，每个毕业生都可选到愿意去的单位。
第 9章 图论图 9.65给出了 n=3,m=5,r=3的情况 。 在这种情况下,
请读者给出几种分配方案 。
返回章目录第 9章 图论
9.8平面图
9.8.1平面图的基本概念定义 9.8.1 设 G=?V,E?是无向图,如果能把 G的所有结点和边画在一个平面上,使得任何两边除端点外没有其它交点,则称 G为平面图,否则,称 G为非平面图 。
在图 9.67中 (a)是无向完全图 K3,它是平面图 。 (b)是无向完全图 K4,它虽有相交边,但适当调整边的位置得到 (c)。
在 (c)中任何两边除端点外没有其它交点,所以 K4为平面图 。
(d)是二部图 K1,3,K1,3是平面图 。 (e)是二部图 K2,3,经改画以后得到 (f)。 由定义 9.8.1知,K2,3是平面图 。 (g),(h)分别是
K5和 K3,3,无论怎样调整边的位置都不能使任何两边除端点外没有其它交点,所以不是平面图 。
第 9章 图论第 9章 图论无向完全 K5和完全二部图 K3,3是两个重要的非平面图,
它们在平面图理论的研究中有非常重要的作用 。
以下的三个结论是显然的 。
定理 9.8.1 若 G是平面图,则 G任何子图是平面图 。
由此定理可知,无向完全图 K4的任何子图是平面图,二部图 K2,3的任何子图也是平面图 。
定理 9.8.2 若 G是非平面图,则 G任何母图是非平面图 。
推论 无向完全图 Kn(n≥5)和二部图 K3,n (n≥3)都是非平面图 。
定理 9.8.3 若 G是平面图,则 G中增加平行边或自回路后所得的图还是平面图 。
本定理说明平行边与自回路不影响图的平面性,因此研究图的平面性时,不考虑平行边和自回路 。
第 9章 图论定义 9.8.2 若 G是平面图,由图中的边所包围的区域,在区域内既不包含图的结点,也不包含图的边,这样的区域称为图 G的一个面 。 其中面积无限的面称为无限面或外部面,
面积有限的面称为有限面或内部面 。 包围该面的诸边组成的回路称为该面的边界,边界的长度称为该面的次数,面 r的次数记为 deg(r)。
常将无限面记为 r0,有限面记为 r1,r2,
图 9.68是一个平面图,它有四个面,r0,r1,r2,r3。 其中 r0是无限面,其它三个面是有限面 。 r0的边界是由回路
abcda和回路 ffghijgf组成的,其次数 deg(r0)=11； r1的边界是由回路 abcdeda组成的,其次数 deg(r1)=6； r2的边界是由回路
ghijg组成的,其次数 deg(r2)=4； r3的边界是 f上的自回路,其次数 deg(r3)=1。
第 9章 图论第 9章 图论定理 9.8.4 设 G=?V,E?是有限平面图,有 n个面,则所有面的次数之和等于边数的 2倍 。 即 =2|E|
证明,G的任何一边,或者是两个面的公共边界,为每一个面的次数增加 1；或者在一个面中作为边界重复计算两次,为该面的次数增加 2。 无论那种情况 G的任何一边为图中面的次数和增加 2,故所有面的次数之和等于边数的 2倍 。
在图 9.68中,有 11条边,所有面的次数之和为：
deg(r0)+deg(r1)+deg(r2)+deg(r3)=11+6+4+1=22=2?11
定义 9.8.3 若 G是简单平面图,若在 G的任意不相邻结点 v,u之间加入边 (v,u),所得的图为非平面图,则称 G为极大平面图 。
)deg(
1
n
i
ir
第 9章 图论关于极大平面图有以下的几个结论：
① 极大平面图是连通图 。
② 结点数大于等于 3的极大平面图不可能存在割点和桥 。
③ 设 G为结点数大于等于 3的简单连通平面图,G为极大平面图当且仅当 G的每个面的次数均为 3。
限于篇幅,这三个结论的证明从略 。
9.8.2欧拉公式
1750年瑞士的数学家列昂哈德?欧拉 (Leonhard Euler)发现任何一个凸多面体,若有 n个顶点,m条棱和 r个面,总有
n-m+r=2成立 。 我们将这个结论推广到平面图中,总结成如下的定理：
第 9章 图论定理 9.8.5 (欧拉公式 )任意连通平面图 G,若有 n个结点,m条边和 r个面,则欧拉公式 n-m+r=2成立 。
证明,对边数 m归纳证明 。
⑴ 设 m=0,由于 G是连通图,所以 G只能是平凡图 。 这时,n=1,m=0,r=1,n-m+r=2成立 。
⑵设 m=k (k≥ 1)时欧拉公式成立，下证当 m=k+1时，欧拉公式也成立。
若 G是树,则 G是非平凡树,根据定理 9.6.2,G中至少有两片树叶 。 设 v为其中一片树叶 。 令 G′=G-?v?(从 G中删除结点 v,而得到 G′),则 G′仍然是连通图 。 设 n′,m′和 r′分别是 G′的结点数,边数和面数 。 则 n′=n-1,m′=m-1=k,r′
=r。 于是 n=n′+1,m=m′+1,r=r′。 因为 G′是连通图且 m′=k
,所以 G′满足归纳假设的条件 。 由归纳假设知：
n′-m′+r′ =2，
所以 n–m+r=( n′ +1)–(m′ +1)+r′ = n′-m′ +r′ =2。
第 9章 图论若 G不是树,则 G中含有回路 。 设边 e在 G的某个回路上 。
令 G′=G-?e?(从 G中删除边 e,而得到 G′),则 G′仍然是连通图 。 设 n′,m′和 r′分别是的结点数,边数和面数 。 则 n′=n，
m′=m-1=k,r′=r–1。 于是 n=n′,m=m′+1,r=r′+1。 因为 G′是连通图且 m′=k,所以 G′满足归纳假设的条件 。 由归纳假设知：
n′–m′＋ r′=2,所以
n–m+r= n′–(m′+1)+(r′+1)= n′-m′+r′=2。
欧拉公式成立是平面图的重要性质，条件是平面图的连通性。欧拉公式还可以推广到非连通的平面图中。将这个结果写成下面的定理：
第 9章 图论定理 9.8.6 设 G是平面图，有 k个连通分支,n个结点,m
条边,r个面，则公式 n-m+r=k+1成立。
证明,设 G的连通分支为 Gi,ni,mi和 ri分别是 Gi的结点数、边数和面数，根据定理 9.8.5,ni-mi+ri=2,i=1,?,k。
而 =m,=n，由于每一个 Gi有一个外部面，而 G只有一个外部面，所以 G的面数 r= -k+1，即 =r+k-1。
所以 2k= = = – ＋ =n-m+r+k-1
整理后有 n-m+r=k+1
由欧拉公式可以推出平面图的一些性质。
k
i
im
1
k
i
in
1
k
i
ir
1
k
i
ir
1
k
i 1
2 )(
1
ii
k
i
i rmn
k
i
in
1
k
i
im
1
k
i i
r
1
第 9章 图论定理 9.8.7 设 G是连通的平面图,有 n个结点,m条边,
每个面的次数至少为 k(k≥3),则关系式 m≤ 成立 。
证明,设 G中有 r个面,由定理 9.8.4知,2m= 。
因为每个面的次数大于等于 k,所以所有面的次数之和大于等于 kr,于是,2m= ≥kr。 即 2m≥kr。 代入欧拉公式
r=2 +m-n,得 2m≥kr=k(2+m–n),整理得,m≤ 。
)2(2 nk k
)d eg (
1
r
i
ir
)deg(
1
r
i
ir
)2(2 nk k
第 9章 图论
【 例 9.18】 利用上述定理证明 K5和 K3,3都不是平面图 。
解,K5如图 9.67(g)所示,结点数 n=5,边数 m=10。
假设 K5是平面图 。 显然 K5是连通的,因为 K5中无自回路和平行边,所以每个面的次数至少为 3,即定理 9.8.7中的 k=3，
K5满足定理 9.8.7的条件 。 所以应有
m≤
但是,代入 n=5,m=10和 k=3得 10?9=,
矛盾 。 所以 K5不是平面图 。
K3,3如图 9.67 (h) 所示,结点数 n=6,边数 m=9。
假设 K3,3是平面图 。 显然 K3,3连通的,因为在 K3,3中任何三个结点,其中必有两个是不相邻接的,所以每个面的次数大于等于 4,即定理 9.8.7中的 k=4,K3,3满足定理 9.8.7的条件 。 所以应有
)2(2 nk k
)25(23 3
第 9章 图论
m≤
但是,代入 n=6,m=9和 k=4得 9?8=,矛盾 。
所以 K3,3不是平面图 。
定理 9.8.8 设 G是平面图,有 s个连通分支,n个结点,m
条边,每个面的次数至少为 k (k≥3),则 m≤
成立 。
利用欧拉公式推广形式容易证明此定理，留作练习。
)2(2 nk k
)26(24 4
)1(2 snk k
第 9章 图论定理 9.8.9 设 G是简单平面图,有 n(n≥3)个结点,m条边,
则 m≤3n-6
证明,设 G有 s (s≥1)个连通分支 。
若 G为树或森林,根据定理 9.6.1，
m=n-s≤n=n+6-6=n+3+3-6≤n+n+n-6=3n–6。
即 m≤3n–6
若 G不是树,也不是森林,则 G中必含有回路 。 又因为
G是简单平面图,所以其中的回路的长度均大于等于 3,因而各面次数 k≥3,又 =1+,当 k=3 时,达到最大值 3,由定理 9.8.8有：
m≤ ≤3(n-s-1)≤3(n-1-1)≤3n-6
2?k
k
2
2
k
)1(2 snk k
第 9章 图论定理 9.8.10 设 G是极大平面图,有 n(n≥3)个结点,m条边,
则 m=3n–6
证明,设 G有 r个面 。 由于极大平面图是连通图,所以 G
是连通图 。 由欧拉公式得 r=2+m-n,又因为 G是极大平面图,
G的每个面的次数均为 3,所以 2m= =3r=3(2+m-n)。
整理后,m=3n–6。
定理 9.8.11 设 G是简单平面图,则 G的最小度?(G)≤5。
证明,设 G有 n个结点,m条边 。
当 n≤6,因为 G是简单图,由定理 9.1.3知,
(G)≤?(G)≤5。
以下证 n≥7的情况,若?(G)≥6,即每个结点的度数大于等于 6,G中所有结点度数之和大于等于 6n。 于是
2m= ≥6n,m≥3n＞ 3n–6,即 m＞ 3n–6，
与定理 9.8.9矛盾 。
)deg(
1
r
i
ir
)d eg (
1
n
i
iv
第 9章 图论在给定图 G的边上插入一个新的度数为 2的结点,使一条边分成两条边,如图 9.69(a)所示,叫做插入一个 2度结点；对于度数为 2的结点,去掉这个结点,使它关联的两条边变成一条边,如图 9.69(b)所示,叫做去掉一个 2度结点 。
定义 9.8.4 给定两个图 G1和 G2,如果它们是同构的,或者通过反复插入一个 2度结点或去掉一个 2度结点后使 G1和 G2
同构,则称 G1和 G2在 2度结点内同构或 G1和 G2同胚 。
定理 9.8.12(Kuratowski定理 1)一个图是平面图当且仅当它不包含与 K3,3或 K5在 2度结点内同构的子图 。
本定理的证明从略 。
第 9章 图论定义 9.8.5 设 G=?V,E?是无向图,e?E,在 G中删除 e,将 e
的两个端点 u和 v合并成一个新端点,记为 w。 w关联除 e以外 u
和 v关联的所有边,称为边 e的收缩 。 如果对图 G的某些边进行收缩,得到图 G′,则称将 G收缩到 G′。
定理 9.8.13 (Kuratowski定理 2)一个图是平面图当且仅当它既没有收缩到 K5的子图,也没有收缩到 K3,3的子图 。 (证明略 )
9.8.3平面图的对偶图定义 9.8.6 设 G=?V,E?是平面图,它具有面 r1,r2,?,rn，
若有图 G*=?V*,E*?满足下述条件：
⑴ 对于图 G的任何一个面 ri,内部有且仅有一个结点?V*。
⑵ 对于图 G的面 ri,rj的公共边界 ek?E,存在且仅存在一个边?E*,使 =(,)且 与 ek相交 。
⑶ 当且仅当 ek只是一个面 ri的边界时,存在一个自回路与 ek相交 。
则称图 G*是平面图 G的对偶图 。
*iv *
jv
*iv
*ke*
ke
*ke
*iv
*ke
第 9章 图论在图 9.71中,设实线边的图是 G,则虚线边的图是 G的对偶图 G*。
从定义可以看出平面图 G
的对偶图 G*有以下的性质：
① G*是连通平面图 。
② G*是图 G的对偶图,G也是图 G*的对偶图 。
③ 若边 e为 G中的自回路,
则在 G*中,与 e对应的边 e*为桥；
若边 e为桥,则在 G*中,与 e对应的边 e*为自回路 。
④ 在多数情况下,G*是多重图 。
第 9章 图论定理 9.8.14 设 G是连通平面图,G*是图 G的对偶图 。 m、
n和 r分别是 G的结点数,边数和面数 。 m*,n*和 r*分别是 G*的结点数,边数和面数 。 则
⑴ n*=r
⑵ m*=m
⑶ r*=n
⑷ 设 G*的结点 位于 G的面 ri中,则 deg( )＝ deg(ri)。 其中,deg( )是结点 的度数,deg(ri)是面 ri的次数 。
证明,根据定义 9.8.6,⑴,⑵ 显然 。
⑶ 由于 G与 G*都是连通平面图,因而满足欧拉公式,n–
m+r=2。 n*–m*+r*=2。 故 r*=2-n*+m*=2-r +m=2+m–r= n
⑷ 设 G的面 ri的边界为 Ci,设 Ci中有 k1个桥,k2个非桥边,
于是 Ci的长度为,2k1+k2,即 deg(ri)=2k1+k2；而 k1个桥对应面
ri中的结点 处有 k1个自回路,k2个非桥边对应从 处引出 k2
条边,即 deg( )=2k1+k2；从而 deg( )=deg(ri)。
*iv*iv
*iv *iv
*iv *iv
*iv*iv
第 9章 图论定理 9.8.15 设 G是平面图,具有 k(k≥2)个连通分支,G*是图 G的对偶图 。 m,n和 r分别是 G的结点数,边数和面数 。 m*、
n*和 r*分别是 G*的结点数,边数和面数 。 则
⑴ n*=r
⑵ m*=m
⑶ r*=n-k+1
⑷ 设 G*的结点 位于 G的面 ri中,则 deg( )=deg(ri)。 其中,deg( )是结点 的度数,deg(ri)是面 ri的次数 。
本定理的证明从略 。
定义 9.8.7如果 G的对偶图 G*与 G同构,则称 G为自对偶图 。
在图 9.72的 (a),(b)中，设实线边图是 G，则虚线边图是
G的对偶图 G*。可以看出图 G和它的对偶图 G*是同构的。所以，图 9.71(a),(b)中的实线边图都是自对偶图。
*iv
*iv
*iv
*iv
第 9章 图论定义 9.8.8 设 G是一个无自回路图,对 G的每一个结点指定一种颜色,使相邻接结点具有不同颜色,称为对图 G的正常着色,简称着色 。 如果图 G着色时用了 n种颜色,则称图 G
为 n色的 。 对图 G着色时,需要的最少颜色数,称为 G的着色数,记为 X(G)。
第 9章 图论对图 G的正常着色有一个简单而有效的方法,叫韦尔奇?
鲍威尔 (Welch Powell)方法,它的基本思想如下：
① 将图 G中的结点按照度数的递减次序进行排列 。 (这种排列可能不惟一,因为有些结点有相同度数 。 )
② 用第一种颜色对第一个结点着色,并且按排列次序,
对与前面着色结点不邻接的每一个结点着上同样的颜色 。
③ 用第二种颜色对尚未着色的结点重复 ②,用第三种颜色继续这种做法,直到所有结点全部着上色为止 。
第 9章 图论
【 例 9.19】 用韦尔奇?鲍威尔法对图 9.73着色 。
解：
① 按照度数递减次序排列各结点,b,f,a,c,e,g,d,h。 他们的度数分别是,4,4,3,3,3,3,2,2。
② 用第一种颜色对 b着色,并对与 b不相邻的结点 g也着这种颜色 。
③ 对结点 f和 c着第二种颜色 。
④ 对结点 a,d和 h着第三种颜色 。
⑤ 对结点 e着第四种颜色 。
因此 G是四色的 。 注意 G不可能是三色的,因为 a,b,e,f
相互邻接的,故必须着四种颜色 。 所以 X(G)=4。
从定义 9.8.8可以看出下列定理成立：
第 9章 图论定理 9.8.16 X(G)=1当且仅当 G是零图 。
定理 9.8.17 设 G中至少含有一条边，则 X(G)=2当且仅当 G是二部图。
第 9章 图论定理 9.8.18 X(Kn)=n。
证明,因为 n个结点的完全图的每一个结点与其它 n-1
个结点都邻接,故 n 个结点的着色数不能少于 n,又 n个结点的着色数至多为 n,X(Kn)=n。
定义 9.8.9 对地图 G的每个国家涂上一种颜色,使相邻的国家涂不同的颜色,称为对地图 G的一种面正常着色,简称着色 。 如果对图 G着色时,用了 n种颜色,则称地图 G为 n
色的 。 对图 G着色时,需要的最少颜色数,称为 G的着色数,
记为 X *(G)。
研究地图的着色可以转化成对它的对偶图的结点着色,
见下面定理 。
定理 9.8.19 地图 G是 n色的当且仅当它的对偶图 G*是 n色的 。
第 9章 图论证明,设地图 G是 n色的,下证它的对偶图 G*是 n色的 。
因为地图 G连通,由定理 9.8.14可知,n*=r,即 G的每个面中含 G*的一个结点 。 设 位于 G的面 ri内 。 将 G*的结点 涂
ri的颜色,易知,若 与 相邻,则由于 ri与 rj的颜色不同 。 所以,与 的颜色也不同,因而 G*是 n色的 。
当 G的对偶图 G*是 n色的,类似的可以证明 G也是 n色 。
由定理 9.8.19可知,研究地图的着色 (面着色 )等价于研究平面图的结点着色 。 对于平面图的点着色问题,到目前为止,人们证明了下面定理 。
定理 9.8.20 任何平面图 G最多是 5色的 。
本定理的证明略 。
定理 9.8.20 称为五色定理，也称为希伍德 (Hewood)定理。
*iv
*iv
*iv
*jv
*jv*iv
返回章目录 返回总目录
9.1 图的基本概念
9.2 路和回路
9.3 连通图
9.4 图的矩阵表示
9.5 欧拉图和汉密尔顿图
9.6 树
9.7 二部图及匹配
9.8 平面图 返回总目录第 9章 图论第 9章 图论图论是一个重要的数学分支。数学家欧拉 1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。随着科学技术的发展，图论在运筹学、网络理论、信息论、控制论和计算机科学等领域都得到广泛的应用。本章首先给出图、
简单图、完全图、子图、路和图的同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、
连通矩阵和完全关联矩阵的定义。最后介绍了欧拉图与哈密尔顿图、树、二部图、平面图和图的着色。
返回章目录第 9章 图论
9.1图的基本概念
9.1.1图两个个体 x,y的无序序列称为无序对,记为 (x,y)。
在无序对 (x,y)中,x,y是无序的,它们的顺序可以颠倒,
即 (x,y)=(y,x)。
定义 9.1.1 图 G是一个三重组?V(G),E(G),?G?
其中,V(G)是非空结点集。
E(G)是边集 。
G是边集到结点的有序对或无序对集合的函数 。
第 9章 图论
【 例 9.1】 G=?V(G),E(G),?G?
其中,V(G)=?a,b,c,d?
E(G)=?e1,e2,e3,e4?
G,?G(e1)=(a,b)
G(e2)=(b,c)
G(e3)=(a,c)
G(e4)=(a,a)
试画出 G的图形 。
解,G的图形如图 9.1所示 。
第 9章 图论由于在不引起混乱的情况下,图的边可以用有序对或无序对直接表示 。 因此,图可以简单的表示为：
G=?V,E?
其中,V是非空的结点集 。
E是边的有序对或无序对组成的集合 。
按照这种表示法,例 9.1中的图可以简记为：
G=?V,E?
其中,V=?a,b,c,d?
E=?(a,b),(b,c),(a,c),(a,a)?
第 9章 图论定义 9.1.2 若图 G有 n个结点,则称该图为 n阶图 。
定义 9.1.3 设 G为图,如果 G的所有边都是有向边,则称 G为有向图 。 如果 G的所有边都是无向边,则称 G为无向图 。 如果 G中既有有向边,又有无向边,则称 G为混合图 。
图 9.3的 (a)是无向图,(b)是有向图,(c)是混合图。
第 9章 图论在一个图中,若两个结点由一条边 (有向边或无向边 )
关联,则称其中的一个结点是另一个结点的邻接点 。 并称这两个结点相互邻接 。
在一个图中不与任何结点相邻接的结点,称为孤立点 。
在一个图中,如果两条边关联于同一个结点,则称其中的一个边是另一个边的邻接边 。 并称这两个边相互邻接 。 关联于同一个结点的一条边叫做环或自回路 。 在有向图中环的方向可以是顺时针,也可以是逆时针,它们是等效的 。
定义 9.1.4 由孤立点组成的图叫做零图 。 由一个孤立点组成的图叫做平凡图 。
根据定义 9.1.4,平凡图一定是零图。
第 9章 图论
9.1.2结点的度及其性质定义 9.1.5 设 G=?V,E?是图,v?V,与 v相关联的边数叫做结点 v的度 。 记为 deg(v)。 规定,自回路为所在结点增加 2度 。
在图 G=?V,E?中,度数最大 (小 )的结点的度叫做图 G
的最大 (小 )度,记为?(G)(?(G))。 图 G的最大度和最小度表示为：
(G)=max? deg(v) | v?V?
(G)= min? deg(v) | v?V?
在图 9.1中,?(G)=4,?(G)=0。
第 9章 图论定理 9.1.1 在任何图 G=?V,E?中,所有结点度数的和等于边数的 2倍 。 即：
= 2|E|
证明,图的每一条边都和两个结点相关联,为每个相关联的结点增加一度,给图增加两度 。 所以所有结点度数的和等于边数的 2倍 。
推论 在任何图 G=?V,E?中,度数为奇数的结点必为偶数个 。
Vv
v )d e g (
第 9章 图论定义 9.1.6 设 G=?V,E?是有向图,v?V,射入 (出 )结点
v的边数称为结点 v的入 (出 )度 。 记为 deg－ (v) (deg＋ (v))。
显然,任何结点的入度与出度的和等于该结点的度数,
即 deg(v)=deg－ (v)+deg＋ (v)。
定理 9.1.2 在有向图中,所有结点入度的和等于所有结点出度的和 。
证明,在有向图中每一条边对应一个入度和一个出度,为图的入度和出度各增加 1。 所以,所有结点入度的和等于边数,所有结点出度的和也等于边数 。
第 9章 图论
9.1.3多重图,简单图,完全图和正则图定义 9.1.7 在图 G中，连接同一对结点的多条相同边称为平行边。平行边的条数称为该平行边的重数。含平行边的图叫多重图。不含平行边和环的图叫简单图。
例如，在图 9.4(a)中结点 a和 b之间有两条平行边，结点 b和 c之间有三条平行边，结点 b上有两条平行边，这两条平行边都是环。图 9.4(a)不是简单图。
又如,在图 9.4(b)中结点 v1和 v2之间有两条平行边 。 v2
和 v3之间的两条边,因为方向不同,所以不是平行边 。 图
9.4(b)不是简单图 。
简单图不含平行边和环。
第 9章 图论第 9章 图论定理 9.1.3 设 G为 n阶简单无向图,则?(G)≤n–1。
证明,因为 G有 n个结点,G的任何结点 v最多只能与其余的 n–1结点相邻接；又因为 G为简单图,既无平行边,又无环 。 所以 deg(v)≤n–1。 由 v的任意性,就有
(G) =max?deg(v) | v?V?≤n–1。
定义 9.1.8 设 G为 n阶简单无向图，若 G中的每个结点都与其余的 n–1个结点相邻接，则称 G为 n阶无向完全图。记为
Kn。在 n阶无向完全图中，给每一条边任意确定一个方向，
所得到的图称为 n阶有向完全图。也记为 Kn。
今后，将 n阶无向完全图和 n阶有向完全图统称为 n阶完全图。
第 9章 图论定理 9.1.4 n阶完全图 Kn的边数为证明,在 Kn中，每个结点都与其余的 n–1结点相邻接，
即任何一对结点之间都有一条边，故边数应为定义 9.1.9 设 G为 n阶简单无向图，若 G中每个结点都是 k
度的，则称 G为 k次正则图。
)1(212 nnC n
第 9章 图论
9.1.4图的同构在图论中只关心结点间是否有连线，而不关心结点的位置和连线的形状。因此，对于给定的图而言，如果将图的各结点安排在不同的位置上，并且用不同形状的弧线或直线表示各边，则可以得到各种不同图形。所以，同一图的图形并不惟一。由于这种图形表示的任意性，可能出现这样的情况：看起来完全不同的两种图形，却表示着同一个图。
例如，在图 9.6中,(a)和 (b)两个图的图形不同，但它们的结构完全相同，是同一个图。
为了描述看起来不同，而其结构完全相同的图，引入了同构的概念。
第 9章 图论第 9章 图论定义 9.1.10 设 G1=?V1,E1?与 G2=?V2,E2?是两个无向图
(有向图 ),若存在双射函数
f,V1?V2,?v1?V1,?v2?V1
(v1,v2)?E1(?v1,v2E1)当且仅当
(f(v1),f(v2))?E2)(?f(v1),f(v2)E2)
并且 (v1,v2)(?v1,v2?)与 (f(v1),f(v2))(?f(v1),f(v2)?)的重数相同，
则称图 G1与图 G2同构。记为 G1≌ G2。双射函数 f称为图 G1
与图 G2的同构函数。
第 9章 图论两个图同构必须满足下列条件：
① 结点数相同 。
② 边数相同 。
③ 度数相同的结点数相同 。
这三个条件是两个图同构的必要条件，不是充分条件。
一般的，用上述三个必要条件判断两个图是不同构的。
两个图同构，它们的同构函数必须实现同度结点对应同度结点。
第 9章 图论
9.1.5补图,子图和生成子图定义 9.1.11 设 G=?V,E?是 n阶简单无向图,G中的所有结点和所有能使 G成为完全图的添加边组成的图称为图 G
的相对于完全图的补图,简称为 G的补图 。 记为 。 若
G≌,则称 G为自补图 。
在图 9.9
中,(b)是 (a)
的补图,(a)与
(b)同构，所以 (a)是自补图。
G
G
第 9章 图论定义 9.1.12 设 G=?V,E?与 G1=?V1,E1?是两个图 。 如果
V1?V且 E1?E,则称 G1是 G的子图,G是 G1的母图；如果
V1?V且 E1?E,则称 G1是 G的真子图；如果 V1＝ V且 E1?E则称 G1是 G的生成子图 。
在图
9.10中，
(b)是 (a)的子图、真子图、生成子图。
返回章目录第 9章 图论
9.2 路和回路定义 9.2.1 设 G=?V,E?是图,G中的结点与边的交替序列 L：
v0e1v1e2v2? envn叫做 v0到 vn的路 。 其中 vi-1与 vi是 ei的端点,
i=1,?,n。 v0和 vn分别叫做路 L的始点和终点 。 路 L中边的条数叫做该路的长度 。
例如,在图 9.11中,
L1,v5e8v4e5v2e6v5e7v3 是从 v5到 v3的路,v5是始点,
v3是终点,长度为 4。
L2,v1e1v2e3v3 是从 v1到 v3的路,v1是始点,
v3是终点,长度为 2。
在简单图中没有平行边和环,路 L,v0e1v1e2v2? envn完全由它的结点序列 v0v1v2? vn确定 。 所以,在简单图中的路可以用结点序列表示 。
第 9章 图论定义 9.2.2 设 G=?V,E?是图,L是从 v0到 vn的路。若 v0=vn，则称 L为回路。
若 L中所有边各异，则称 L为简单路。
若此时又有 v0=vn，则称 L为简单回路。
若 L中所有结点各异，则称 L为基本路。
若此时又有 v0=vn，则称 L为基本回路。
若 L既是简单路，又是基本路，则称 L
为初级路。若此时又有 v0=vn，则称 L为初级回路。
在图 9.11中,L1是一条简单路。 L2
是一条简单路、基本路、初级路。。
第 9章 图论定理 9.2.1 在 n阶图 G中,若从结点 vi到 vj(vi≠vj)存在一条路,则必存在长度小于等于 n-1的路 。
证明,设 L,vie1v1e2v2? ejvj是 G中一条从结点 vi到 vj长度为 l的路,路上有 l+1个结点 。
若 l≤n-1,则定理已证 。
否则,l＞ n-1,此时,l+1＞ n,即路 L上的结点数 l+1
大于图 G中的结点数 n,此路上必有相同结点 。 设 vk和 vs相同 。 于是,此路两次通过同一个结点 vk(vs),所以在 L上存在 vs到自身的回路 Cks。 在 L上删除 Cks上的一切边和除 vs以外的一切结点,得路 L1,vie1v1… ekvs… ejvj。 L1仍为从结点 vi
到 vj的路,且长度至少比 L减少 1。 若路 L1的长度小于等于
n-1,则定理已证 。 否则,重复上述过程 。 由于 G有 n个结点,经过有限步后,必得到从 vi到 vj长度小于等于 n-1的路 。
第 9章 图论推论 在 n阶图 G中,若从结点 vi到 vj(vi≠vj)存在路,则必存在长度小于等于 n-1的初级路 。
由定理 9.2.1的证明过程知,本推论成立 。
类似的可证明下列定理和推论 。
定理 9.2.2 在 n阶图 G中,若存在结点 vi到自身的回路,
则必存在 vi到自身长度小于等于 n的回路 。
推论 在 n阶图 G中，若存在结点 vi到自身的简单回路，
则必存在 vi到自身长度小于等于 n的初级回路。
返回章目录第 9章 图论
9.3连通图
9.3.1无向连通图定义 9.3.1 在无向图 G中,如果结点 u和结点 v之间存在一条路,则称结点 u和结点 v连通 。 记为 u～ v。 规定,G中任意结点 v和自身连通,即 v～ v。
在无向图中,如果结点 u和结点 v连通,即 u～ v,那么,
结点 v和结点 u连通,即 v～ u。 所以,无向图结点间的连通是对称的 。
设 G=?V,E?是无向图,在图 G的结点集 V上建立一个二元关系 R：
R=u,v?| u?V∧ v?V∧ u和 v连通?
R叫做无向图 G的结点集 V上的连通关系 。
因为 R是自反的、对称的、传递的，所以 R是 V上的等价关系。无向图 G的结点集 V上的连通关系是等价关系。
第 9章 图论设 G是图 9.14。结点集 V上的连通关系为 R，以下验证
R是 V上的等价关系，并找出所有等价类。
R=a,a?,?a,b?,?a,c?,?b,a?,?b,b?,?b,c?,?c,a?,?c,b?,
c,c?,?d,d?,?e,e?,?e,f?,?e,g?,?e,h?,?f,e?,?f,f?,
f,g?,?f,h?,?g,e?,?g,f?,?g,g?,?g,h?,?h,e?,?h,f?,
h,g?,?h,h
=?a,b,c?×?a,b,c?∪?d?×?d?∪?e,f,g,h?×?e,f,g,h?
根据定义,R
是 V上的等价关系。等价类有三个，分别是：
a,b,c?,?d?，
e,f,g,h?。
第 9章 图论定义 9.3.2 若无向图 G中的任何两个结点都是连通的,
则称 G为连通图 。 规定,平凡图是连通图 。
定义 9.3.3 设 G=?V,E?是图
⑴ V1?V且 V1≠?,E1是 G中两个端点都在 V1中的边组成的集合,图 G1=?V1,E1?叫做 G的由 V1导出的子图,记为
G[V1]。
⑵ E2?E且 E2≠?,V2是由 E2中的边所关联的结点组成的集合,图 G2=?V2,E2?叫做 G的由 E2导出的子图,记为
G[E2]。
在图 9.15中,设图 G为 (a),取 V1=?a,b,c?,则 G的由
V1导出的子图 G[V1]是 (b)。 取 E2=?(a,b),(d,c)?,G的由 E2导出的子图 G[E2]是 (c)。
第 9章 图论第 9章 图论定义 9.3.4 设 G=?V,E?是无向图,R是 V上的连通关系，
V/R=?Vi?Vi是 R的等价类,i=1,?,k?是 V关于 R的商集，
G[Vi]是 Vi导出的子图，称 G[Vi]( i=1,?,k)为 G的连通分支。
G的连通分支数记为 W(G)。
设图 9.14为 G，在 G中，连通关系 R的三个等价类是
a,b,c?,?d?,?e,f,g,h?，它们导出的 G的子图分别是图
9.14中的 (a),(b),(c)。它们都是 G的连通分支。 G的连通分支数 W(G)=3。
每一个连通分支中任何两个结点是连通的，而位于不同连通分支中的任何两个结点是不连通的。即每一个连通分支都是原图的最大的连通子图。在图 9.14中,(a),(b)，
(c)都是最大的连通子图。
第 9章 图论定义 9.3.5 设 u,v是无向图 G中的任意两个结点,若 u
和 v连通,则 u和 v之间最短路的长叫做结点 u与结点 v的距离,记为 d(u,v)。 若 u和 v不连通,规定,u与 v的距离为 ∞。
即 d(u,v)=∞。
设 G=?V,E?是无向图,u,v和 w是 V中的任意结点,G
的结点间的距离有以下的性质：
① d(u,v)≥0
② d(u,u)=0
③ d(u,v)＋ d(v,w)≥d(u,w)
④ d(u,v)=d(v,u)
在 n阶无向完全图 Kn中,每两个不同结点间都有一条边,它们的距离是 1。 在零图中,每两个不同结点间都没有路,它们的距离都是 ∞。
在图 G中删除一个结点，就是将这个结点与它的所有关联边全部删除。删除一个边，则仅去掉这个边。
第 9章 图论定义 9.3.6 设 G=?V,E?是无向连通图,V1?V且 V1≠?，
满足：
⑴ 删除 V1的所有结点,得到的子图是不连通的 。
⑵ 删除 V1的任何真子集,得到的子图是连通的 。
则称 V1是 G的点割集 。 如果某一个结点组成了点割集,则称该点为割点 。
在图 9.16中，
b,d?,?c?,?e?都是点割集，结点 c和结点 e都是割点。虽然删除结点 a和 c图成为不连通的，但因?c?是?a,c?的真子集，所以?a,c?不是点割集。
第 9章 图论定义 9.3.7 设 G=?V,E?是无向连通图,如果 G不是完全图,k(G)=min?|V1|?V1是 G的点割集?称为图 G的点连通度 。
如果 G是完全图,规定 n阶无向完全图 Kn的点连通度为 n–1，
即 k(Kn)=n–1。 规定不连通图 G的点连通度为 0。 即 k(G)= 0。
图 9.16是无向连通图，但不是完全图，存在割点 c和 e，
所以点连通度是 1。
无向连通图的点连通度的物理意义是：要使 G成为不连通的最少要删除的结点数。图 9.16的点连通度是 1，最少删除一个结点，图成为不连通的，例如删除结点 c或结点 e。
第 9章 图论定义 9.3.8 设 G=?V,E?是无向连通图,E1?E且 E1≠?，
满足：
⑴删除 E1的所有边，得到的子图是不连通的。
⑵删除 E1的任何真子集，得到的子图是连通的。
则称 E1是 G的边割集。如果某一条边组成了边割集，则称该边为割边或桥。
在图 9.16中，集合?(c,e)?,?(e,f)?,?(a,b),(d,c)?和
(a,d),(b,c)?都是 G的边割集，无向边 (c,e)和 (e,f)为割边。
虽然删除边 (a,d),(a,b)和 (d,c)图成为不连通的，但因集合?(a,b),(d,c)?是集合?(a,d),(a,b),(d,c)?的真子集，所以
(a,d),(a,b),(d,c)?不是边割集。
第 9章 图论定义 9.3.9 设 G=?V,E?是无向连通图,如果 G是非平凡图,?(G)=min?|E1|?E1是 G的边割集?称为 G的边连通度 。
如果 G是平凡图,规定 G的边连通度为 0。 规定不连通图 G
的边连通度为 0,即?(G)=0。
图 9.16是无向连通图,但不是平凡图,存在割边 (c,e)
和 (e,f),所以,它的边连通度是 1。
无向连通图的边连通度的物理意义是：要使 G成为不连通的最少要删除的边数 。 图 9.16的边连通度是 1,最少删除一条边,图就会 成为不连通的,例如删除 割边 (c,e)或
(e,f)。
无向图 G的点连通度 k(G)、边连通度?(G)和最小度?
(G)有下列的关系：
第 9章 图论定理 9.3.1 设 G=?V,E?为任意无向图,则
k(G)≤?(G)≤?(G)
证明,⑴ 如果 G是不连通的,由点连通度和边连通度的定义有 k(G)=?(G)=0,所以
k(G)≤?(G)≤?(G)
⑵ 如果 G是连通图 。
① 先证明?(G)≤?(G)
如果 G是平凡图,?(G)=0≤?(G),即?(G)≤?(G)
如果 G是非平凡图,设 n=?(G)=min?deg(v)|v?V?,则存在 G的一个结点 v,它关联了 n条边,而其它结点关联的边数大于等于 n,将 v关联的这 n条边删除,G成为不连通的 。
从而这 n条边或这 n条边中的几条边组成一个边割集,即存在一个边割集的基数小于等于 n,所以第 9章 图论
min?|E 1| | E 1是 G的边割集?≤n=min?deg(v) | v?V?,即
(G)≤?(G)
② 再证 k(G)≤?(G)
设?(G)=1,G有一条割边,此边的任一端点是割点,
k(G)=1。 所以 k(G)≤?(G)成立 。
设?(G)≥2,则可删除某?(G)条边,使 G成为不连通的,
而删除其中的?(G)–1条边,它仍然是连通的且有一个桥,
设该桥为 e=(u,v)。 对这?(G)–1条边选取一个不同于 u,也不同于 v的端点,把这些端点删除,则必至少删除了这
(G)–1条边 。 若这样产生的图是不连通的,则 k(G)≤?(G)–
1≤?(G)。 若这样产生的图是连通的,则 e=(u,v)仍是桥 。 此时再删除 u或 v,就必产生了一个不连通图,故 k(G)≤?(G)
由⑴和⑵得 k(G)≤?(G)≤?(G)
第 9章 图论图 9.17是无向连通图,点连通度 k(G)=1,边连通度
(G)=2,最小度?(G)=3,此图满足 k(G)≤?(G)≤?(G)。
第 9章 图论定理 9.3.2 在无向连通图 G中,结点 v是割点的充分必要条件是存在两个结点 u和 w,使结点 u和 w之间的每一条路都通过 v。
证明,设 v是割点,证明存在两个结点 u和 w,使结点 u
和 w之间的每一条路都通过 v。
v是割点,删除 v得 G′,G′至少包含两个连通分支,设其中的两个为 G1=?V1,E1?和 G2=?V2,E2?,?u?V1,?w?V2，
因为 G连通,在 G中 u和 w之间必有路,设 L是它们之间任意一条路 。 在 G′中,由于 u和 w属于两个不同连通分支,所以,u和 w之间必没有路 。 故 L必通过 v。
设存在两个结点 u和 w,使结点 u和 w之间的每一条路都通过 v,证明 v是割点 。
删除 v得子图 G′，因为结点 u和 w之间的每一条路都通过 v，所以在 G′中结点 u和 w之间必无路，即结点 u和 w不连通。由连通图的定义知,G′是不连通的，故 v是 G的割点。
第 9章 图论
9.3.2有向连通图定义 9.3.10 在有向图 G中,结点 u到结点 v存在一条路,
则称结点 u到结点 v可达 。 记为 u→ v。 如果 u到 v可达且 v到 u
也可达,称结点 u和结点 v相互可达 。 记为 u? v。 规定,G
中任何结点 v自己到自己可达,即 v? v。
定义 9.3.11 在有向图 G=?V,E?中,u?V,v?V,若结点
u到结点 v可达,u到 v最短路的长称为结点 u到结点 v的距离 。
记为 d?u,v?。 若 u到 v不可达,规定,u到 v的距离为 ∞。 即
d?u,v?=∞。
对于有向图 G中的任意结点 u,v和 w,结点间的距离有以下的性质：
① d?u,v?≥0
② d?u,u?=0
③ d?u,v?＋ d?v,w?≥ d?u,w?
第 9章 图论定义 9.3.12 在简单有向图 G中,对于任意两个结点 u和 v，
⑴ 如果结点 u到结点 v可达或结点 v到结点 u可达,则称 G
为单向 (侧 )连通的 。
⑵ 如果结点 u和结点 v互相可达,则称 G为强连通的 。
⑶ 如果略去方向得到的无向图是连通的,则称 G为弱连通的 。
在图 9.18中,(a)是强连通的,单向 (侧 )连通的和弱连通的 。 (b)是单向 (侧 )连通的和弱连通的,但不是强连通的 。 (c)
是弱连通的,但不是单向 (侧 )连通的,也不是强连通的 。
第 9章 图论一般地说，若有向图 G是强连通的，则必是单向 (侧 )连通的和弱连通的；若有向图 G是单向 (侧 )连通的，则必是弱连通的。反之不真。
第 9章 图论定理 9.3.3 一个有向图 G是强连通的充分必要条件是 G中有一个回路至少包含 G的每个结点一次 。
证明,设 G中有一个回路至少包含 G的每个结点一次,
下证 G是强连通的 。
G中有一个回路至少包含每个结点一次,则 G中的任意两个结点通过回路互相可达 。 所以 G是强连通的 。
设 G是强连通的,下证 G中有一个回路至少包含 G的每个结点一次 。
若不然,存在结点 v不在 G的任何回路上,则 v与其它任何结点不能互相可达,这与 G是强连通的矛盾 。 故 G中有一个回路至少包含 G的每个结点一次 。
第 9章 图论定理 9.3.4 一个有向图 G是单向连通的充分必要条件是
G中有一个路至少包含每个结点一次 。
证明略 。
定义 9.3.13 在简单有向图 G中,具有强 (单向,弱 )连通性质的最大子图叫做强 (单向,弱 )分图 。
在图 9.19(a)中,由?v1,v2,v3,v4?导出的子图是强分图,
v5?导出的子图也是强分图 。 由?v1,v2,v3,v4,v5?导出的子图是单向分图,也是弱分图 。
在图 9.19 (b) 中,?v1?,?v2?,?v3?,?v4?导出的子图是强分图,?v1,v2,v3?，和?v1,v3,v4?导出的子图是单向分图，
v1,v2,v3,v4?导出了弱分图。
第 9章 图论第 9章 图论定理 9.3.5 在有向图 G=?V,E?中,每一个结点位于且只位于一个强分图中 。
证明,⑴?v?V,令 V1是 G中所有与 v互相可达的结点组成的集合,当然 v?V1,V1导出的子图是 G的强分图 。 故
G的每一个结点位于一个强分图中 。
⑵设 G1=?V1,E1?和 G2=?V2,E2?是 G的两个强分图，设
v?V1且 v?V2，则 v与 G1中的所有结点相互可达且与 G2中的所有结点相互可达。于是 G1中的结点与 G2中的结点通过 v
相互可达。这与 G1和 G2是强分图相矛盾。故 G的每一个结点只位于一个强分图中。
返回章目录第 9章 图论
9.4图的矩阵表示定义 9.4.1 设 G=?V,E?是一个简单图,V=?v1,v2,?,vn?
A(G)=(aij) n× n
其中：
i,j=1,?,n
称 A(G)为 G的邻接矩阵 。 简记为 A。
0
1
jivv
vva
ji
ji
ij
无边或到有边到第 9章 图论
0111
1010
1101
1010
)( GA
例如图 9.22的邻接矩阵为：
第 9章 图论又如图 9.23(a)的邻接矩阵为：
0001
1011
1100
0010
)( GA
第 9章 图论邻接矩阵具有以下性质：
①邻接矩阵的元素全是 0或 1。这样的矩阵叫布尔矩阵。
邻接矩阵是布尔矩阵。
②无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。
③邻接矩阵与结点在图中标定次序有关。例如图 9.23(a)
的邻接矩阵是 A(G)，若将图 9.23(a)中的接点 v1和 v2的标定次序调换，得到图 9.23(b)，图 9.23(b)的邻接矩阵是 A′(G)。
0010
1011
0001
1100
)( GA
第 9章 图论考察 A(G)和 A′(G)发现，先将 A(G)的第一行与第二行对调，再将第一列与第二列对调可得到 A′(G)。称 A′(G)与 A(G)
是置换等价的。
一般地说，把 n阶方阵 A的某些行对调，再把相应的列做同样的对调，得到一个新的 n阶方阵 A′，则称 A′与 A是置换等价的。可以证明置换等价是 n阶布尔方阵集合上的等价关系。
虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。
④对有向图来说，邻接矩阵 A(G)的第 i行 1的个数是 vi的出度,第 j列 1的个数是 vj的入度。
⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。
第 9章 图论定理 9.4.1 设 A(G)是图 G的邻接矩阵,A(G)k=A(G)A(G)k-1，
A(G)k的第 i行，第 j列元素 等于从 vi到 vj长度为 k的路的条数。
其中 为 vi到自身长度为 k的回路数。
推论 设 G=?V,E?是 n阶简单有向图,A是有向图 G的邻接矩阵,Bk=A＋ A2＋? ＋ Ak,Bk=( )n× n，则 是 G中由 vi到 vj
长度小于等于 k的路的条数。 是 G中长度小于等于 k的路的总条数。 是 G中长度小于等于 k的回路数。
【 例 9.4】 设 G=?V,E?为简单有向图，图形如图 9.24，写出 G的邻接矩阵 A，算出 A2,A3,A4且确定 v1到 v2有多少条长度为 3的路? v1到 v3有多少条长度为 2的路? v2到自身长度为 3
和长度为 4的回路各多少条?
kija
kiia
kijb
n
i
n
j
kijb
1 1
n
i
kiib
1
kijb
第 9章 图论解,邻接矩阵 A和 A2,A3,A4如下：
01000
10000
00010
00101
00010
A
10000
01000
00101
00020
00101
2
A
第 9章 图论
01000
10000
00020
00202
00020
3
A
10000
01000
00202
00040
00202
4
A
=2，所以 v1到 v2长度为 3的路有 2条，它们分别是：
v1v2v1v2和 v1v2v3v2。
=1，所以 v1到 v3长度为 2的路有 1条,v1v2v3。
=0,v2到自身无长度为 3的回路。
=4,v2到自身有 4条长度为 4的回路，它们分别是：
v2v1v2v1v2,v2v3v2v3v2,v2v3v2v1v2和 v2v1v2v3v2。
312a
213a
322a
422a
第 9章 图论定义 9.4.2 设 G=?V,E?是简单有向图,V=?v1,v2,?,vn?
P(G)=(pij)n× n
其中,pij =
i,j=1,?,n
称 P(G)为 G的可达性矩阵。简记为 P。
在定义 9.3.10中，规定了有向图的任何结点自己和自己可达。所以可达性矩阵 P(G)的主对角线元素全为 1。
不可达到可达到
ji
ji
vv
vv
0
1
第 9章 图论设 G=?V,E?是 n阶简单有向图,V=?v1,v2,?,vn?,由可达性矩阵的定义知,当 i≠j时,如果 vi到 vj有路,则 pij=1；如果
vi到 vj无路,则 pij=0；又由定理 9.2.1知,如果 vi到 vj有路,则必存在长度小于等于 n–1的路 。 依据定理 9.4.1的推论,如下计算图 G的可达性矩阵 P：
先计算 Bn–1=A＋ A2＋? ＋ An–1,设 Bn–1=( )n× n。
若 ≠0,则令 pij=1,若 =0,则令 pij =0,i,j=1,?,n。
再令 pii=1,i=1,?,n。 就得到了图 G的可达性矩阵 P。
令 A0为 n阶单位阵,则上述算法也可以改进为：
计算 Cn–1= A0＋ Bn–1=A0＋ A＋ A2＋? ＋ An-1，
设 Cn–1=( )n× n。 若 ≠0,则令 pij=1，
若 =0,则令 pij=0,i,j=1,?,n。
1?nijb
1?nijb 1?nijb
1?nijc 1?nijc
1?nijc
第 9章 图论使用上述方法,计算例 9.4中图 G的可达性矩阵,
C4= A0＋ A＋ A2＋ A3＋ A4 =
31000
13000
00433
00373
00334
11000
11000
00111
00111
00111
P=
第 9章 图论计算简单有向图 G的可达性矩阵 P,还可以用下述方法：
设 A是 G的邻接矩阵,令 A=(aij)n× n,A(k) =( )n× n,A0为
n阶单位阵 。
A(2)=A°A,其中 =(ai1∧ a1j)∨ (ai2∧ a2j)∨? ∨ (ain∧ anj)
i,j=1,?,n。
A(3)=A°A(2),其中 (ai1∧ )∨? ∨ (ain∧ )
i,j=1,?,n。
P= A0∨ A∨ A(2)∨ A(3)∨? ∨ A(n–1)。 其中,运算 ∨ 是矩阵对应元素的析取 。
可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。
)(kija
)2(ija
)3(ija )2(
1ja )2(nja
第 9章 图论定义 9.4.3 设 G=?V,E?是简单无向图,V=?v1,v2,?,vn?
P(G)=( pij) n× n
其中：
i,j=1,?,n
称 P(G)为 G的连通矩阵。简记为 P。
无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。
0
1
不连通与连通与
ji
ji
ij vv
vvp
第 9章 图论定义 9.4.4 设 G=?V,E?是无向图,V=?v1,v2,?,vp?，
E=?e1,e2,?,eq?
M(G)=( mij) p× q
其中：
i=1,?,p,j=1,?,q
称 M(G)为无向图 G的完全关联矩阵。简记为 M。
0
1
否则关联与 ji
ij
evm
第 9章 图论例如图 9.25的完全关联矩阵为：
1000
1100
0011
0111
M(G) =
第 9章 图论设 G=?V,E?是无向图,G的完全关联矩阵 M(G)有以下的性质：
① 每列元素之和均为 2。 这说明每条边关联两个结点 。
② 每行元素之和是对应结点的度数 。
③ 所有元素之和是图各结点度数的和,也是边数的 2倍 。
④ 两列相同,则对应的两个边是平行边 。
⑤ 某行元素全为零,则对应结点为孤立点 。
定义 9.4.5 设 G=?V,E?是有向图,V=?v1,v2,?,vp?，
E=?e1,e2,?,eq?
M(G)=( mij) p× q
其中,i=1,?,p,j=1,?,q
称 M(G)为有向图 G的完全关联矩阵。简记为 M。
不关联与的终点是的始点是
ji
ji
ji
ij
ev
ev
ev
m
0
1
1
第 9章 图论图 9.26的完全关联矩阵为：
M(G)=
11100
11000
00111
00011
第 9章 图论设 G=?V,E?是有向图,G的完全关联矩阵 M(G)有以下的性质：
① 每列有一个 1和一个 -1,这说明每条有向边有一个始点和一个终点 。
② 每行 1的个数是对应结点的出度,-1的个数是对应结点的入度 。
③ 所有元素之和是 0,这说明所有结点出度的和等于所有结点入度的和 。
④两列相同，则对应的两边是平行边。
返回章目录第 9章 图论
9.5欧拉图和汉密尔顿图
9.5.1欧拉图定义 9.5.1 在无孤立结点的图 G(有向图或无向图 )中,如果存在一条路经过每一条边一次且仅一次,则称该路为欧拉路 。 如果存在一条回路经过每一条边一次且仅一次,则称该回路为欧拉回路 。 具有欧拉回路的图称为欧拉图 。
定理 9.5.1 无向图 G具有一条欧拉路当且仅当 G是连通的且有零个或两个奇度结点 。
证明,设 G具有一条欧拉路,下证 G是连通的且有零个或两个奇度结点 。
设 G中有一条欧拉路 L,v0e1v1e2v2? ekvk,该路经过 G的每一条边 。 因为 G中无孤立结点,所以该路经过 G的所有结点,即 G的所有结点都在该路上 。 故 G中任意两个结点连通,
从而 G是连通图 。
第 9章 图论设 vi是图 G的任意结点,若 vi不是 L的端点,每当沿 L经过
vi一次都经过该结点关联的两条边,为该结点的度数增加 2。
由于 G的每一条边都在该路上,且不重复,所以 vi的度数必为偶数 。 若 vi是 L的端点 v0,当 v0=vk时,则 v0和 vk的度数也为偶数,即 G中无奇度结点；当 v0≠vk时,则 v0和 vk的度数均为奇数,
即 G中有两个奇度结点 。
设 G是连通的且有零个或两个奇度结点,下证 G具有一条欧拉路 。
设 G是连通图,有零个或两个奇度结点,用下述方法构造一条欧拉路：
① 若 G中有两个奇度结点,则从其中的一个 v0开始构造一条简单路 。
从 v0出发经关联边 e1进入 v1,若 v1是偶数度结点,则必可以由 v1经关联边 e2进入 v2。 如此下去,每边只取一次 。 由于 G
是连通图,必可到达另一个奇度结点 vk,从而得到一条简单路 L1,v0e1v1e2v2? ekvk。
第 9章 图论若 G中无奇度结点,则从任意结点 v0出发,用上述方法必可回到结点 v0,得到一条简单回路 L1,v0e1v1e2v2? v0。
② 若 L1经过 G的所有边,则 L1就是欧拉路 。
③ 否则,在 G中删除 L1,得子图 G′,则 G′中的每一个结点的度数为偶数 。 因为 G是连通图,故 L1和 G′至少有一个结点 vi重合,在 G′中由 vi出发重复 ①,得到简单回路 L2。
④ 若 L1与 L2组合在一起恰是 G,则得到了欧拉路,否则,
重复 ③ 可得到简单回路 L3。
以此类推直到得到一条经过 G中所有边的欧拉路 。
推论 无向图 G具有一条欧拉回路当且仅当 G是连通的且所有结点都是偶度的 。
这个推论说明,无向图 G是欧拉图当且仅当 G是连通的且所有结点都是偶度的 。
第 9章 图论图 9.30(a)的每一个结点的度数都是偶数 2，所以 (a)中有一个欧拉回路，是欧拉图；在图 9.30 (b)中有两个结点的度数是奇数 3，故 (b)中有一个欧拉路，但没有欧拉回路，
不是欧拉图；在图 9.30 (c)中四个结点的度数都是奇数 3，
(c)中没有欧拉路，更没有欧拉回路，不是欧拉图。
第 9章 图论定理 9.5.2 有向图 G具有一条欧拉回路当且仅当 G是强连通的且每个结点的入度等于出度 。
这个定理说明,有向图 G是欧拉图的充分必要条件是 G
是强连通的且每个结点的入度等于出度 。
定理 9.5.3 有向图 G具有一条欧拉路当且仅当 G是单向连通的且除了两个结点外，每个结点的入度等于出度，而在这两个结点中，一个结点入度比出度大 1，另一个结点入度比出度小 1。
这两个定理可以看作定理 9.5.1和推论的推广。因为对于有向图的任意一个结点，如果入度与出度相等，则该结点的度数为偶数。若入度与出度之差为 1时，则该结点的度数为奇数。因此定理 9.5.2和定理 9.5.3的证明与定理 9.5.1的证明类似 。
第 9章 图论图 9.31(a)是强连通的且每一个结点的入度等于出度，都等于 1，所以 (a)中有一个欧拉回路，是欧拉图；图 9.31 (b)是单向连通的且有两个结点入度与出度相等，有两个结点入度与出度不相等，其中一个结点入度比出度大 1，另一个结点入度比出度小 1。故有一个欧拉路，但没有欧拉回路，不是欧拉图；图 9.31(c)的四个结点入度与出度都不相等，没有欧拉路，更没有欧拉回路。
第 9章 图论哥尼斯堡七桥问题从前,一个称为哥尼斯堡城的城市有一条横贯全市的普雷格尔河,河中有两个小岛,用七座桥将岛和岛,河岸和岛连接起来,如图 9.32所示 。 18世纪中叶,该城市的人们提出了一个问题：能否不重复的走完七桥,最后回到原地 。
城中的很多人试图解决这个问题,然而试验者都以失败告终 。 1736年瑞士的数学家列昂哈德?欧拉 (Leonhard Euler)发表了一篇论文,哥尼斯堡七桥问题,,这篇论文的基本内容就是定理 9.5.1。 在这篇论文中第一次论证了这个问题是无解的 。 他将河岸和岛抽象成图的结点,而把桥画成相应的连接边,如图 9.33所示 。 于是,不重复的走完七桥,最后回到原地,等价于图中存在一条回路,经过每一条边一次且仅一次,即图中存在欧拉回路 。 因为图中的四个结点的度数都是奇数 。 所以图中不存在欧拉回路 。
第 9章 图论第 9章 图论
9.5.2汉密尔顿图一个与欧拉回路和欧拉图非常类似的问题是汉密尔顿回路和汉密尔顿图问题。它是由爱尔兰数学家威廉?汉密尔顿爵士 (Sir Willian Hamilton)于 1859首先提出的。
定义 9.5.2 在图 G(有向图或无向图 )中，如果存在一条路，经过每个结点一次且仅一次，则该路称为汉密尔顿路。
如果存在一条回路，经过每个结点一次且仅一次，则称该路为汉密尔顿回路。具有汉密尔顿回路的图称为汉密尔顿图。
与欧拉图不同，判断一个图是否为汉密尔顿图至今还没有一个简单的充分必要条件，只有一些必要条件和充分条件。判断一个图是汉密尔顿图的充分必要条件是图论中尚未解决的基本难题之一。下面介绍一些关于汉密尔顿图的必要条件和充分条件。
第 9章 图论先给出一个约定：设 G=?V,E?是图,S?V，用 G-S表示从图 G中删除 S中的所有结点所得的子图。
定理 9.5.4 设无向图 G=?V,E?是汉密尔顿图,S是 V的任意非空子集,则 W(G-S)≤|S|。
证明,设 C是 G的一条汉密尔顿回路,?v1?S,则 C-
v1?(从 C中删除结点 v1)是一条路或回路,路上各结点相互连通 。 再删除 S中的另一个结点 v2,则 W(C-?v1,v2?)≤2,所以
W(C-?v1,v2?)≤|?v1,v2?|。 由归纳法可得 W(C-S)≤|S|。
又因为 C-S是 G-S的生成子图，因而 W(G–S)≤ W(C–S)，
所以有 W(G–S)≤ |S|。
本定理的条件是汉密尔顿图的必要条件,而不是充分条件 。 利用该定理可以证明一个图不是汉密尔顿图,即满足此定理条件的图不一定是汉密尔顿图,而不满足此定理条件的图一定不是汉密尔顿图 。
第 9章 图论例如,图 9.34叫彼得松图 。 彼得松图满足定理 9.5.4的条件,但可以验证它不是汉密尔顿图 。
又如,在图 9.35中,令 S=?a,b?,则 W(G-S)=3,|S|=2，
故 W(G–S)≤|S|不成立 。 所以该图不是汉密尔顿图 。
第 9章 图论
【 例 9.5】 设 G是无向连通图,证明：如果 G中有割点或桥,则 G一定不是汉密尔顿图 。
证明,设 v是割点 。 删除结点 v,图成为不连通的,且至少有两个连通分支 。 令 S=?v?,则 W(G–S)≥2＞ 1=|S|,即
W(G–S)＞ |S|。 依据定理 9.5.4,G不是汉密尔顿图 。
如果 G中有桥，则该桥的一个端点是割点。可以归结为
G中有割点的情况。所以 G也不是汉密尔顿图。
定理 9.5.5 设 G=?V,E?是 n阶无向简单图，如果 G中每一对结点度数的和大于等于 n–1，则在 G中存在一条汉密尔顿路。
推论 设 G=?V,E?是 n阶无向简单图，如果 G中每一对结点度数的和大于等于 n，则在 G中存在一条汉密尔顿回路。
第 9章 图论定理 9.5.5及其推论给出了图中存在一条汉密尔顿路和汉密尔顿回路的充分条件，而不是必要条件。例如，图
9.37(a)有 6个结点，任意两个结点度数的和小于 5，但图中存在一条汉密尔顿路。又如图图 9.37 (b)也有 6个结点，任意两个结点度数的和小于 6，但图中存在一条汉密尔顿回路。
第 9章 图论
【 例 9.6】 设 G=?V,E?是一个无向简单图,|V|=n,|E|=m，
设 m＞ (n–1)(n–2)。 试证明 G中存在一条汉密尔顿路 。
证明,先证明图 G中任意两个不同的结点度数之和大于等于 n-1,然后利用定理 9.5.5即得本例要证的结果 。
用反证法,设图 G中存在两个结点 v1和 v2,使得 deg(v1)
＋ deg(v2)＜ n–1,即 deg(v1)＋ deg(v2)≤n–2。 删去结点 v1和 v2后,
得到图 G′,G′是具有 n-2个结点的无向简单图 。 设 G′的边数为 m′,则 m′≥m-(n-2)＞ (n-1)(n-2)-(n-2)=(n-2)(n-3)，
即 m′＞ (n–2)(n–3)
另一方面,G′是具有 n–2个结点的无向简单图,它最多有 (n–2)(n–3)条边 。 所以 m′≤(n–2)(n–3)。
由此得出矛盾。所以 deg(v1)＋ deg(v2)≥ n–1，由定理
9.5.5得 G中存在一条汉密尔顿路。
第 9章 图论
【 例 9.7】 某地有 5个风景点,若每个风景点均有两条道路与其它点相通,问是否可经过每个风景点恰好一次的游完这 5处?
解,因为有 5个风景点,故可看成一个有 5个结点的无向图,其中每处均有两条路与其它结点相通,所以 deg(vi)=2，
i=1,?,5。 故对任意两点 vi,vj均有
deg(vi)+deg(vj)=2+2=4=5-1
由定理 9.5.5可知此图中一定有一条汉密尔顿路,本题有解 。
定义 9.5.3 给定图 G=?V,E?有 n个结点,若将图 G中度数之和至少是 n的非邻接结点连接起来得图 G′,对图 G′重复上述步骤,直到不再有这样的结点对存在为止,所得到的图称为原图 G的闭包,记作 C(G)。
第 9章 图论例如图 9.38给出了有六个结点的图 G构造其闭包的过程。
在这个例子中 C(G)是完全图。一般情况下,C(G)也可能不是完全图。
第 9章 图论定理 9.5.6 设 G是简单图,G是汉密尔顿图当且仅当 G的闭包是汉密尔顿图 。
证明略 。
下面通过一个例子,介绍一个判别汉密尔顿路不存在的方法 。
【 例 9.8】 图 G如图 9.39所示，证明 G中没有汉密尔顿路。
证明,任取一结点 a用 A标记,所有与它相邻接的结点标记为 B。 继续不断地用 A标记所有邻接于 B的结点,再用 B
标记所有邻接于 A的结点,直到所有的结点标记完毕 。
如果图中有一条汉密尔顿路，那么它必交替通过标记 A
的结点和标记 B的结点，故或者标记 A的结点与标记 B的结点数一样，或者两者相差为 1。然而本例有 3个结点标记 A，
5个结点标记 B，它们相差为 2，所以该图不存在汉密尔顿路。
第 9章 图论返回章目录第 9章 图论
9.6 树树是比较简单而又特别重要的图，它在计算机科学和技术中有非常广泛的应用。
9.6.1无向树定义 9.6.1 连通无回路的无向图称为无向树,简称树 。
常用 T表示 。 在树中,度数为 1的结点称为树叶,度数大于 1
的结点称为分支点或内点 。 规定,平凡图也是树,叫平凡树 。
定义 9.6.2 若无向图至少有两个连通分支,每一个连通分支是树,则此无向图称为森林 。
无向树有很多性质,有些性质是树的充分必要条件,
可以看作树的等价定义 。 下面的定理是树的 6个充分必要条件,每一个都可以作为树的定义使用 。
第 9章 图论定理 9.6.1 设 G=?V,E?是无向图,|V|=n,|E|=m,则下列各命题是等价的：
① G是树 。
② G中每一对结点之间存在惟一的路 。
③ G中无回路且 m=n–1
④ G是连通的且 m=n–1
⑤ G是连通的且 G中任何边均为桥 。
⑥ G中无回路，但在任何两个不同的结点之间增加一个新边，得到一个惟一的含新边的回路。
证明,①?②
G是树,所以 G是连通的,?u?V,?v?V,u和 v之间存在一条路 。 若路不惟一,设 L1和 L2都是 u和 v之间的路,
则 L1和 L2组成了 G中的一个回路,与 G是树矛盾 。
第 9章 图论
②?③
先证 G中无回路 。 若 G中存在某个结点 v上的自回路,
u?V,由条件知 u到 v存在一条路 L1,u? v,因为 v上有自回路,所以 u到 v存在另一条路 L2,u? vv,这与 G中每一对结点之间存在惟一的路矛盾 。 若 G中存在长度大于等于 2的一条回路,则回路上两个结点之间存在不同的路 。 这与条件是矛盾的 。 所以 G中无回路 。
以下用归纳法证明 m=n–1。
当 n=1时,G为平凡图,m=0=1–1=n–1。 结论成立 。
设 n≤k时,结论成立 。 下证 n=k+1时,结论也成立 。
设 e=(u,v)是 G中的一条边,由于 G中无回路,所以
G-?e?(在 G删除边 e所得的子图 )有两个连通分支 G1和 G2，
设它们的结点数和边数分别为,m1,n1和 m2,n2。 于是有
n1≤k和 n2≤k,由归纳假设知,m1=n1–1和 m2=n2-1,m=m1＋
m2＋ 1=n1-1＋ n2-1＋ 1=n-1。
第 9章 图论
③?④ 只须证明 G是连通的 。 若不然,设 G有 t(t≥ 2)个连通分支 G1,G2,?,Gt,Gi中均无回路,都是树 。 由 ①
②?③ 可知,mi=ni–1,i=1,?,t。 于是 m=m1＋ m2＋? ＋ mt
=n1-1＋ n2-1＋? ＋ nt-1=n1＋ n2＋? ＋ nt-t=n–t,由于 t≥ 2，
这与 m=n–1矛盾 。 所以 G是连通图 。
④?⑤ 只须证明 G的每一条边均为桥 。 设 e是 G的任意边,删除 e得子图 G1,G1中的边数 m1=m-1,G1中的结点数
n1=n,m1=m–1=n-1-1=n-2=n1-2＜ n1-1,由习题 9.3的第 3题知 G1不是连通图,所以 e是桥 。
⑤?⑥ 由于 G中每一条边均为桥,因而 G中无回路 。 又因为 G连通,所以 G是树 。 由 ①?② 知,?u?V,?v?V，
u≠v,u与 v之间存在一条惟一的路 。 在 u与 v之间增加一条新边,就得到 G的一条回路,显然这条回路是惟一的 。
⑥?① 只须证明 G是连通的,?u?V,?v?V,u≠v,在
u与 v之间增加一条新边 (u,v)就产生 G的一个惟一的回路,故结点 u和结点 v连通 。 由于 u与 v是任意的,所以 G是连通图 。
第 9章 图论定理 9.6.2 在任何 n阶非平凡的无向树 T中至少有两片树叶 。
证明,设树 T有 x片树叶,由定理 9.1.1知,树 T中所有结点的度数之和 等于边数的 2倍 。 依据定理 9.6.1,在树 T中边数等于结点数减 1,即 n–1。 所以 2(n–1)= 。
另一方面,树中的分支点为 n-x个,每个分支点的度数大于等于 2,所有分支点度数之和大于等于 2(n–x),从而下式成立：
2(n-1)= ≥x+2(n-x)
解之,得 x≥2。
)deg(
1
n
i
iv
)deg(
1
n
i
iv
)deg(
1
n
i
iv
第 9章 图论
9.6.2生成树定义 9.6.3 设 G为无向图,若 G的生成子图是一棵树,
则该树称为 G的生成树 。 设 G的生成树为 T,则 T中的边称为树枝 。 G的不在生成树 T中的边称为弦 。 所有弦的集合称为生成树 T的补 。
在图 9.40中,(b)是 (a)的生成树,e2,e3,e5,e6是树枝，
e1,e4是弦,?e1,e4?是该生成树的补； (c)是 (a)的生成树，
e1,e2,e3,e6是树枝,e4,e5是弦,?e4,e5?是该生成树的补。
第 9章 图论定理 9.6.3 无向图 G具有生成树的充分必要条件是 G为连通图 。
证明,若无向图 G具有生成树,显然 G为连通图 。
以下证明若无向图 G为连通图,则 G具有生成树 。
若连通图 G无回路,则 G本身就是一棵生成树；若 G至少有一个回路,删除此回路的一边,得到子图 G1,它仍然连通,并与 G有相同结点集 。 若 G1无回路,则 G1就是一棵生成树；若 G1仍有一个回路,再删除 G1回路上的一边 。 重复上述过程,直至得到一个无回路的连通图,该图就是一棵生成树 。
由定理 9.6.3的证明过程可以看出，一个连通图可以有多个生成树。因为在取定一个回路后，就可以从中去掉任一条边，去掉的边不同，可能得到的生成树也不同。
例如，在图 9.40 (a)中相继删去边 e1和 e4，就得到了生成树 (b)。相继删去边 e4和 e5，就得到了生成树 (c)。
第 9章 图论推论 1 无向连通图 G有 n个结点和 m条边,则 m≥n–1
证明,由定理 9.6.3的证明知,G有生成树,设为 T。
|E(G)|=m,其中,E(G)是图 G的边构成的集合 。 依据定理
9.6.1,|E(T)|=n–1,其中,E(T)是树 T的边构成的集合 。 而
|E(G)|≥|E(T)|,所以 m≥n–1。
推论 2 在无向连通图中,一个回路和任何一棵生成树的补至少有一条公共边 。
证明,若有一个回路和一棵生成树的补无公共边,那么,这个回路包含在该生成树中,这与树的定义矛盾 。
推论 3 在无向连通图中,一个边割集和任何一棵生成树至少有一条公共边 。
证明,若有一个边割集和一棵生成树无公共边,那么,
删除这个边割集所得的子图必包含该生成树,从而该子图是连通的 。 这与边割集的定义矛盾 。
第 9章 图论设 G为无向连通图,有 n个结点和 m条边 。 T为 G的生成树,T有 n个结点和 n-1条边 。 所以要得到 G的一棵生成树,必须删除 G的 m-(n-1)=m–n＋ 1条边 。
定义 9.6.4 设 G为无向连通图,有 n个结点和 m条边 。
要得到一棵生成树,必须删除 G的 m–n＋ 1条边 。 m–n＋ 1
称为无向连通图 G的秩 。
无向连通图的秩，与生成树的选择无关。
定义 9.6.5 设 G=?V,E?为无向连通图,?e?E，对边 e
指定一个正数 C(e)，称正数 C(e)为边 e的权。设 T是 G的生成树,T的所有边 e的权之和称为树 T的权。记为 C(T)。若
G的每一条边都指定权，则称 G为赋权图。
在实际应用中，边的权可以是长度，运输量或其它费用。
第 9章 图论定义 9.6.6 在图 G的所有生成树中,权最小的生成树,
称为最小生成树 。
定理 9.6.4 设 G=?V,E?为无向连通赋权图,|E|=m,以下算法可以产生最小生成树 T：
先将图的 m条边按它的权由小到大的顺序排列为：
e1,e2,?,em。
① 取 e1到 T中 。
② 在尚未检查过的边中从左到右依次检查,若 ej与 T中的边不能构成回路,则取 ej到 T中,否则跳过 。
③反复做②，直到所有边都已检查。
第 9章 图论定理 9.6.4描述的算法叫克鲁斯克尔 (kruskal)算法 。
【 例 9.8】 图 9.41(a)给出了一个赋权图 G,用 kruskal算法求出 G的最小生成树 。
解,先将 m条边按权由小到大排列：
(v4,v5),(v1,v8),(v5,v7),(v6,v7),(v4,v6),(v5,v6)，
(v2,v7),(v2,v5),(v7,v8),(v2,v3),(v3,v4),(v1,v2)。
它们的权分别是：
3,4,5,6,6.5,7,7.5,8,10.5,11,12,13。
逐次取边：
(v4,v5),(v1,v8),(v5,v7),(v6,v7),(v2,v7),(v7,v8)，
(v2,v3)，
构成的生成树在图 9.41(b),这是 G的最小生成树 。 最小生成树 T的权 C(T)=3+4+5+6+7.5+10.5+11=47。
第 9章 图论第 9章 图论
9.6.3根树及其应用定义 9.6.7 一个有向图,略去方向后是树,则称这个有向图为有向树 。 如果一棵有向树恰有一个结点入度为 0,其余所有结点入度为 1,此有向树称为根树 。 在根树中,入度为 0的结点称为树根,出度为 0的结点称为树叶,出度不为 0
的结点称为分枝点或内点 。 从此定义可以看出,在根树中,
除了树叶都是分枝点或内点外,树根也是分枝点 。
9.42(a)是一棵有向树 。 (b)是一棵根树 。 v1是树根,
v3,v5,v6,v8是树叶,v1,v2,v4,v7是分枝点 。
第 9章 图论第 9章 图论定义 9.6.8设 T是一棵根树,由树根到 T的任意结点 v的路长叫做结点 v的层数 。 层数最大的结点的层数叫做该树的高 。
在图 9.42(b)中,v1的层数为 0,v2,v3,v4的层数为 1,v5,v6,
v7的层数为 2,v8的层数为 3,树的高为 3。
在根树中,各有向边的方向是一致的 。 所以画根树时,
可以省略各边的方向,并且常将树根画在最上方 。
定义 9.6.9 在根树中,若 vi到 vj有一条路,则称 vi是 vj的祖先,vj是 vi的后代 。 若?vi,vj?是根树中的一条边,则称 vi是 vj
的父亲,vj是 vi的儿子；同一个分枝点的儿子叫兄弟 。
定义 9.6.10 设 T是一棵根树,将 T中层数相同的结点标定一个次序,则称 T为有序树 。
定义 9.6.11 设 T是一棵根树,v是 T的任意结点,把 v和它的所有后代组成的结点集导出的图叫做 T的以 v为根的根子树,简称为以 v为根的子树,记为 Tv。
第 9章 图论定义 9.6.12 在根树中,若每个结点的出度小于或等于 m，
则称该树为 m叉树 。 在 m叉树中,若每个结点的出度恰等于 0
或 m,则称该树为完全 m叉树 。 在完全 m叉树中,若所有树叶层数相同,则称该树为正则 m叉树 。
当 m=2时,m叉树就是二叉树，完全 m叉树就是完全二叉树。在图 9.43中,(a),(b),(c)都是二叉树，其中 (b),(c)
是完全二叉树,(b)是正则二叉树。
二叉树的每一个结点 v至多有两棵根子树,分别称为 v的左子树和右子树 。 一般的,左子树画在 v的左下方,右子树画在 v的右下方 。 二叉树的每一个结点 v至多有两个儿子,左边的叫左儿子,右边的叫右儿子 。
第 9章 图论第 9章 图论定理 9.6.5 在完全 m叉树中,其树叶数为 t,分枝点数为 i,则 (m-1)i=t-1。
证明,由定理的条件知,该树有 i＋ t个结点,由定理
9.6.1知,该树边数为 i＋ t-1。 另一方面,由完全 m叉树定义知,该树出度的和为,mi,这也是该树的边数,于是有
mi=i＋ t-1。 整理后有 (m-1)i=t-1。
【 例 9.10】 设有一台计算机,它有一条加法指令,可计算 3个数的和 。 如果要计算 9个数的和,问至少要执行几次加法指令？
解,用 3个结点表示三个数,用它们的父结点表示它们的和 。 于是,问题就抽象为求一个完全 3叉树的分枝点有多少个 。 把 9看成树叶的个数,依据定理 9.6.5,(3-1)i=
9-1,i=4。 所以要执行 4次加法指令 。
第 9章 图论任何一棵有序根树都可用二叉树来表示,其方法如下：
① 从根结点开始,保留父亲和最左边儿子的连线,取消和其他儿子的连线,兄弟之间用从左到右的有向边连接 。
②选定二叉树的左儿子和右儿子如下：处于给定结点下方的结点作为该结点的左儿子，同一水平线上与给定结点右邻的结点作为该结点的右儿子。
图 9.44 (a)是一棵有序根树,做完 ① 得 (b),做完 ② 得 (c)，
(c)是一颗二叉树 。
第 9章 图论第 9章 图论图 9.45的 (a)也是一棵有序根树,按照上述方法,做完 ①
得 (b),做完 ② 得 (c),(c)是一颗二叉树 。
第 9章 图论用二叉树表示有序根树的方法可以推广到森林中去，其方法如下：
① 将森林中每一棵有序根树表示成二叉树 。
② 除最左边的二叉树外,
逐次将右边的二叉树作为左边的二叉树的根的右子树 。
例如图 9.44(a)中的有序根树和图 9.45(a)中的有序根树从左向右组成的一个森林,此森林转化为二叉树,只须将图
9.45(c)作为图 9.44(c)的根 v1的右子树就可以了 。 如图 9.46所示 。
第 9章 图论二叉树在计算机科学和技术中有广泛的应用,人们对它的研究也比较深入,有很多重要的结论,以下是最基本的几条 。
定义 9.6.13 在根树中,由树根到分枝点的路长叫做内部通路长 。 由树根到树叶的路长叫做外部通路长 。 若 v是根树的任意结点,树根到 v的路长叫做结点 v通路长,它是内部通路长或外部通路长,结点 v通路长记为 l(v)。
定理 9.6.6 若完全二叉树有 n个分枝点,内部通路长度的总和为 I,外部通路长度的总和为 E,则 E=I＋ 2n。
证明,对分枝点的数目 n进行归纳证明 。
① n=1,即一个分枝点,两片树叶,
如图 9.47所示 。 I=0,E=2=I＋ 2n。
第 9章 图论
② 设 n=k-1时,结论成立,即 Ek–1=Ik–1＋ 2(k-1)。 以下证明,当 n=k时,结论也成立,即 Ek=Ik＋ 2k。
设 Tk的分枝点为 k个,如果删除一个分支点 v,v的内部通路长为 l且 v的两个儿子是树叶,得到新树 Tk–1。 Tk–1与
Tk比较,减少了两片外部通路长为 l+1的树叶和一个内部通路长为 l的分枝点 。 增加了一个外部通路长为 l树叶 。 故在 Tk中,Ek= Ek–1＋ 2(l＋ 1)-l=Ek–1＋ l＋ 2,Ek–1=Ek-l-2。 Ik=
Ik–1＋ l,Ik–1= Ik-l。 代入归纳假设 Ek–1=Ik–1＋ 2(k–1)中,得
Ek-l-2=Ik-l＋ 2(k-1),整理后得 Ek= Ik＋ 2k。
这就证明 E=I＋ 2n。
第 9章 图论定义 9.6.14 设 T是一棵二叉树，有 t片树叶 v1,v2,?,
vt，分别带权 W!,W2,?,Wt，则称 T为赋权二叉树或带权二叉树。在赋权二叉树 T中,称为树 T的权。记为
W(T)。在所有有 t片树叶的二叉树中，如果 t片树叶分别带权
W!,W2,?,Wt，权 W(T)最小的二叉树，称为最优二叉树。
图 9.48中的三棵树 T1,T2和 T3都是带权 2,2,3,3,5的二叉树,它们的权分别是：
W(T1)=2× 2＋ 2× 2＋ 3× 3＋ 5× 3＋ 3× 2=38
W(T2)=3× 4＋ 5× 4＋ 3× 3＋ 2× 2＋ 2× 1=47
W(T3)=3× 3＋ 3× 3＋ 5× 2＋ 2× 2＋ 2× 2=36
以上三棵树都是带权 2,2,3,3,5的赋权二叉树，但不是最优树。
)(
1
i
t
i
i vlW?
第 9章 图论第 9章 图论下面介绍一种求最优树方法,叫 Huffman算法 。 它的基本思想是：
给定 t片树叶的权为 W1,W2,?,Wt且 W1≤W2≤? ≤Wt。
①连接权为 W1,W2的两片树叶，得一分枝点，其权为
W1＋ W2。
② 在 W1＋ W2,W3,?,Wt中选出两个最小的权,连接它们对应的结点 (不一定是树叶 ),得新分枝点及所带的权 。
③重复②，直到形成 t–1个分枝点,t片树叶为止。
第 9章 图论
【 例 9.11】 求带权 2,2,3,3,5的最优二叉树 T。
解,图 9.49给出了生成最优二叉树的过程 。 权 2,2,3，
3,5中最小的两个为 2和 2,2和 2代表两片树叶,得一分枝点,其权为 2＋ 2=4,如图 9.49 (a)所示 。 在 3,3,4,5中选出两个最小的权 3和 3,连接它们对应的结点,得新分枝点,
该结点所带权为 6,如图 9.49(b)所示 。 在 4,5,6中选出两个最小的权 4和 5,连接它们对应的结点,得新分枝点,该结点所带权为 9,如图 9.49(c)所示 。 最后,连接 6和 9对应的结点得新分枝点,该分枝点所带权为 15,如图 9.49(d)所示 。
(d)是最优树 。 最优树的权为：
W(T)=2× 3＋ 2× 3＋ 5× 2＋ 3× 2＋ 3× 2=34
第 9章 图论第 9章 图论二叉树的另一个应用是前缀码问题，下面介绍前缀码的基本概念和简单应用。
在通信中常用 0,1字符串表示英文字母,即用二进制数表示英文字母 。 最少用多少位二进制数就能表示 26个英文字母呢？ 1位二进制数可以表示 2=21个英文字母,两位二进制数可以表示 4=22个英文字母,,n位二进制数可以表示 2n个英文字母 。 如果规定,可以用 1位二进制数表示英文字母,也可以用两位二进制数表示英文字母 。 如果 1位和两位不足以表示 26个英文字母,可用 3位二进制数 。 再不够,
用 4位二进制数 。 这叫做用不定长二进制数表示英文字母 。
若用不定长二进制数表示 26个英文字母,至少需要多少位二进制数？ 设需要 i位二进制数,于是,下列的不等式成立：
26≤21＋ 22＋? ＋ 2i==2i+1–2
解之,得 i≥4
故用长度不超过 4位的二进制数足以表示 26个英文字母 。
第 9章 图论在英文中有些字母使用频率较高,另一些字母使用频率较低 。 为了减少通信中传递的信息量,人们希望用位数较少的二进制数表示频繁使用的字符,用位数较多的二进制数表示不常使用的字符 。 这样就会大大缩短信息串的总长度 。 但是也产生了一个问题：接收者如何将 0,1组成的长串,准确无误地分割成字母对应的 0,1序列呢？ 例如：
若用 00表示 e,用 01表示 t,用 0001表示 q。 当接收员接收到
0001时,就无法区分这是 et,还是 q。 为了解决这个问题,
引入前缀码的概念 。
如果 0,1序列 a是另一个 0,1序列 b左起的一个连续部分，则称 a是 b的前缀。例如 00是 0001的前缀,000也是
0001的前缀。而 01不是 0001的前缀。
第 9章 图论定义 9.6.15 给定一个 0,1序列的集合 。 若没有一个序列是另一个序列的前缀,则称该集合为前缀码 。
例如?1,00,011,0101,01001,01000?是前缀码 。 而
1,00,0101,0100,01001,01000?不是前缀码,
因为 0100是 01001的前缀,也是 01000的前缀 。
若使用前缀码中的 0,1序列表示英文字母,当接收者收到 0,1组成的长串时,就可以惟一的,准确无误地分割成字母对应的 0,1序列 。
定理 9.6.7 任意一个二叉树,可以产生惟一的前缀码 。
证明,在二叉树中,每一个分枝点引出的左侧边标记
0,右侧边标记 1。 由根结点到树叶的路经上各边的标记组成的 0,1序列作为该片树叶的标记 。 显然,没有一片树叶的标记是另一片树叶的标记的前缀 。 所有树叶的标记构成了一个前缀码 。
第 9章 图论
【 例 9.12】 求图
9.50 (a)所示的二叉树产生的前缀码 。
解,在图 9.50(a)
中，每一个分枝点引出的左侧边标记 0，
右侧边标记 1。由根结点到树叶的路经上各边的标记组成的 0、
1序列作为对应树叶的标记，如图 9.50(b)
所示。产生的前缀码为,?01,11,000,0010,
0011?
第 9章 图论定理 9.6.8 任意一个前缀码，都对应一个二叉树。
证明,给定了一个前缀码,设 h是其中最长序列的长度 。 画出一个高为 h的正则二叉树 。 按定理 9.6.7中描述的办法给各边标记 0或 1。 每一个结点对应一个 0,1序列,它是由根结点到该结点的路经上各边的标记组成的 。 如果某个 0,1序列是前缀码的元素,则标记该结点 。 将已标记结点的所有后代和该结点的射出边全部删除,得到了一个二叉树,再删除未加标记的树叶,就得到要求的二叉树 。
【 例 9.13】 设?1,01,000?是一前缀码,画出对应一个二叉树 。
解,画出一个高为 3的正则二叉树,给各边标记 0或 1，
每一个结点对应一个 0,1序列,如果某个 0,1序列是前缀码的元素,则标记该结点 。 如图 9.51(a)所示 。 将已标记结点的所有后代和该结点的射出边全部删除,再删除未加标记的树叶,得到要求的二叉树,如图 9.51 (b)所示 。
第 9章 图论返回章目录第 9章 图论
9.7二部图及匹配
9.7.1二部图定义 9.7.1 G=?V,E?是无向图,V1?V,V2?V,满足：
① V1∪ V2= V,V1∩V2=?。
② G中每一条边的两端点,一个属于 V1,另一个属于
V2。
则称 G为二部图或偶图,常记为 G=?V1,V2,E?,V1和 V2称为
G的互补的结点子集 。
二部图的每一条边的两个端点位于两个互补的结点子集,所以没有自回路 。 二部图是无自回路图 。
定义 9.7.2 设 G=?V1,V2,E?是二部图,|V1|=r,|V2|=s,若
V1的每个结点和 V2的所有结点邻接,则称 G为完全二部图或完全偶图,常记为 Kr,s。
在图 9.55中,(a),(b),(c)都是二部图,其中 (b),(c)是完全二部图 K1,3和 K3,3。
第 9章 图论第 9章 图论定理 9.7.1 设 G=?V,E?是无向图,G为二部图的充分必要条件是 G的所有回路的长均为偶数 。
证明,设 G是二部图,下证 G的所有回路的长均为偶数 。
设 G是二部图,则 V可以分成两个互补的结点子集 V1和
V2,每一个边的两个端点分别在 V1和 V2中,令
C,v0v1v2? vl-1v0
是 G中任一长度为 l的回路 。 不失一般性,设 v0?V1,则 v1?V2，
v2?V1,则 v3?V2, 。 由此可知,v2i?V1,v2i＋ 1?V2。 又因为 v0?V1,所以 vl-1?V2,l-1是奇数,l是偶数 。
设 G的所有回路的长均为偶数,下证 G是二部图 。
不妨设 G是连通图,否则可对每一个连通分支进行讨论 。
v0?V,定义 V的两个子集 V1和 V2为：
V1=?v | v?V∧ d(v0,v)为偶数?
V2=?v | v?V∧ d(v0,v)为奇数?
因为 G是连通图,任何结点与 v0之间都有路,d(v0,v)不是偶数就是奇数,所以 V1∪ V2=V,V1∩V2=?。
第 9章 图论下面证明 V1中任意两个结点不邻接,V2中任意两个结点也不邻接 。 若存在 vi?V1,vj?V1,vi 和 vj邻接,由于 d(v0,vi)
为偶数,v0到 vi有一条长为偶数的路 。 同样的道理,v0到 vj
也有一条长为偶数的路 。 这两条路和边 (vi,vj)构成一条回路,
其长度为奇数 。 与条件矛盾 。 所以 V1中任意两个结点不邻接 。 类似的可证,V2中任意两个结点也不邻接 。 于是 G为二部图 。
根据此定理，图 9.56中的 (a)和 (b)两个图是二部图。这比用定义判断要方便得多。画二部图时，习惯将互补的结点子集 V1和 V2分开画，画成图 9.55的形式。图 9.56中的 (a)，
(b)两个二部图，一定可以改画为图 9.55的形式。
第 9章 图论第 9章 图论
9.7.2匹配定义 9.7.3 设 G=?V1,V2,E?是二部图,M是 G中一些边组成的集合,如果 M中任意两条边都没有公共端点,则称 M为
G的一个匹配或对集 。 设 v是 G的结点,如果 v是 M中某条边的端点,则称 v为 M的饱和点 。 否则,称 v为 M的非饱和点 。
在图 9.57中,边集 M=?(a1,b2),(a2,b3),(a4,b1)?是一个匹配,
a1,a2,a4和 b1,b2,b3为 M的饱和点 。 结点 a3为 M的非饱和点 。
在图 9.57中，如果用 a1,a2,a3,a4表示 4位教师,b1,b2,b3表示三门待开的课程。当某位教师能开某门课程时，则把它们的对应结点用边连接起来。如果规定一个教师只能担任一门课程，那么匹配 M就表示了一种排课方案。为了使排课方案能最大限度地作到,各尽其能,,下面将引进最大匹配的概念。
第 9章 图论第 9章 图论定义 9.7.4 设 G=?V1,V2,E?是二部图,M是 G的一个匹配,如果对 G的任意匹配 M′,都有 |M′|≤|M|,则称 M为 G的最大匹配或最大对集 。
为了寻求二部图的最大匹配,以下引进交替路和可扩路两个概念 。
定义 9.7.5 设 G=?V1,V2,E?是二部图,M是 G的匹配,P
是 G中的一条路,如果 P是由 G中属于 M的边和不属于 M的边交替组成,则称 P为 G的 M交替路 。 如果交替路的始点和终点都是 M的非饱和点,则称为 G的 M可扩路 。
例如,在图 9.58中,匹配 M=?(a1,b2),(a2,b3),(a3,b5)?，
路
L1,a1b2a2b3a3,L2,a2b3a3b5a4，
L3,b1a3b5a4,L4,b1a1b2a2b3a3b5a4
都是 M交替路,其中后两条交替路 L3和 L4的始点和终点都是 M的非饱和点,所以这两条路是 M可扩路 。
第 9章 图论设 G=?V1,V2,E?是二部图,M是 G的一个匹配,P是 G中的一条 M可扩路 。 把 P中所有属于 M的边从 M中去掉,而把
P中所有不属于 M的边添加到 M中,得到一个新的边集 M′，
则 M′也是一个匹配,其所含边数比匹配 M所含的边数多 1。
第 9章 图论例如在图 9.58中,把 M可扩路 L3,b1a3b5a4中属于 M的边
(a3,b5) 从 M中去掉,而把 L3中不属于 M的边 (a3,b1)和 (a4,b5)
添加到 M中,得到一个新的边集 M′=?(a1,b2),(a2,b3),(a3,b1),
(a4,b5)?,显然 M′也是匹配且 M′的边数比 M的边数多 l,即
|M′|＝ |M|+1。 如图 9.59所示 。
第 9章 图论由此可见，利用可扩路可以增加匹配所含的边数。不断地寻求 G的可扩路，直到再也找不到新的可扩路，就可得到一个最大匹配。将这个结论写成下列的定理。
定理 9.7.2 设 G=?V1,V2,E?是二部图,M为 G的最大匹配的充分必要条件是 G中不存在 M可扩路 。
证明,设 M为 G的最大匹配,下证 G中不存在 M可扩路 。
如果 G中存在一条 M可扩路,则可以得到比 M的边数多 1
的匹配,所以 M不是最大匹配,矛盾 。 所以 G中不存在 M可扩路 。
设 G中不存在 M可扩路,下证 M为 G的最大匹配 。
设 M1是最大匹配,证明 |M|=|M1|。
考察属于 M而不属于 M1和属于 M1而不属于 M中的边,由这些边连同它们的端点一起构成 G的子图 H。
第 9章 图论在子图 H中,任一结点至多与 M中的一条边关联且与 M1
中一条边关联 。 因而任一结点的度数是 1或 2。 故 H的连通分支是一条路,或者是一个回路 。
如果 H的连通分支是一条路 P,则它是 M交替路,也是
M1交替路 。 如果 P的两个端点均与 M中的边关联,则 P是 M1
可扩路 。 由假设知,M1是最大匹配,所以,不存在 M1可扩路,得到矛盾 。 如果 P的两个端点均与 M1的边关联,那么 P
是一条 M可扩路与题设矛盾 。 故 P只能是一个端点与 M中的边关联,另一个端点与 M1中的边关联,这样 P中属于 M的边数与属于 M1的边数相等 。
如果 H的连通分支是一个回路,回路中的边交替地属于
M和 M1,因而属于 M的边数与属于 M1的边数相等 。
从上面可以看到,H中属于 M的边与属于 M1的边的数目相等 。 再加上既属于 M又属于 M1的边,可以得出,M中的边数与 M1中的边数相等 。 所以 M是最大匹配 。
第 9章 图论有了上面的准备以后,就可以进一步讨论如何在二部图中求最大匹配的问题 。
设 G=?V1,V2,E?是二部图,通常先作 G的一个匹配 M，
再看 V1中有没有 M的非饱和点 。 如果没有,那么 M肯定是最大匹配；如果有,就从这些点出发找 M可扩路 。 由 M可扩路作出一个更大的匹配 。 所以,在 G中求最大匹配的关键是寻找 M可扩路 。
寻找可扩路的一个有效方法是标记法，其基本思想如下：
设 G=?V1,V2,E?是二部图,在 G中作一个匹配 M,用 (*)
标记 V1中所有 M的非饱和点,然后交替地进行以下 ① 和 ② 两步：
① 选一个 V1的新标记过的结点,比如说 ai,用 (ai)标记不通过 M中的边与 ai邻接且尚未标记过的 V2的所有结点 。 对
V1所有新标记过的结点重复这一过程 。
第 9章 图论
② 选一个 V2的新标记过的结点，比如说 bi，用 (bi)标记通过 M中的边与 bi邻接且尚未标记过的 V1的所有结点。对 V2
所有新标记过的结点重复这一过程。
直至标记到一个 V2中的 M的非饱和点 。 从该结点倒向追踪到标记有 (*)的结点,就得到了一个 M可扩路 。 把 M可扩路中所有属于 M的边从 M中去掉,而把 M可扩路中所有不属于
M的边添加到 M中,得到一个新的匹配 M′且其所含边数比匹配 M所含的边数多 1。 对 M′重复上述过程,,直到 G中已不存在可扩路,此时的匹配就是最大匹配 。
第 9章 图论
【 例 9.15】 图 9.60是二部图,求其最大匹配 。
第 9章 图论解,取二部图图 9.60的一个匹配 M=?(a3,b1),(a5,b2)?。
用 (*)标记 V1中所有 M的非饱和点 a1,a2,a4。
① 选 V1的新标记过的结点 a1,用 (a1)标记不通过 M的边与 a1邻接且尚未标记过的 V2的结点 b1；类似地用 (a2)标记 b2。
② 选 V2的新标记过的结点 b1,用 (b1)标记通过 M的边与
b1邻接且尚未标记过的 V1的结点 a3；类似地用 (b2)标记 a5。
③ 选 V1的新标记过的结点 a3,因为不存在不通过 M的边与 a3邻接的 V2的结点,所以不用 (a3)标记 V2的结点；用 (a5)标记 b3或 b4,假定用 (a5)标记 b3。 如图 9.60所示 。
b3是 M的非饱和点,标记结束 。
从 b3倒向追踪到标记有 (*)的结点,就得到了 M可扩路：
a4b2a5b3或 a2b2a5b3,取后者 。 把 M可扩路 a2b2a5b3中的边
(a5,b2)从 M中去掉,而把 (a2,b2)和 (a5,b3)添加到 M中得到新的匹配 M′=?(a3,b1),(a2,b2),(a5,b3)?,如图 9.61所示 。
第 9章 图论第 9章 图论对匹配 M′=?(a3,b1),(a2,b2),(a5,b3)?再用标记法：
用 (*)标记 V1中所有 M′的非饱和点 a1和 a4。
① 选 V1的新标记过的结点 a1,用 (a1)标记不通过 M′的边与 a1邻接且尚未标记过的 V2的所有结点 b1；再用 (a4)标记 b2。
② 选 V2的新标记过的结点 b1,用 (b1)标记通过 M′的边与
b1邻接且尚未标记过的 V1的所有结点 a3；再用 (b2)标记 a2。
③ 选 V1的新标记过的结点 a2和 a3,V2中已无可标记的结点 。
图中已不存在可扩路,所以 M′就是最大匹配 。
第 9章 图论
【 例 9.16】 图 9.62是二部图，求其最大匹配。
第 9章 图论解,取二部图图 9.62的一个匹配 M=?(a2,b2),(a3,b3),
(a5,b5)?。 用 (*)标记 V1中所有 M的非饱和点 a1,a4。
① 选 V1的新标记过的结点 a1,用 (a1)标记 b2和 b3。
② 选 V2的新标记过的结点 b2和 b3,用 (b2)标记 a2,用 (b3)
标记 a3。
③ 选 V1的新标记过的结点 a2,用 (a2)标记 b1,b4和 b5。
由于 b1和 b4都是 M的非饱和点,说明找到了 M可扩路 。
它们是,a1b2a2b4和 a1b2a2b1。 选前者,把边 (a2,b2)从 M中去掉,而把 (a1,b2) 和 (a2,b4) 添加到 M 中,得到 新的 匹配
M′=?(a1,b2),(a2,b4),(a3,b3),(a5,b5)?,如图 9.63所示 。
对于匹配 M′=?(a1,b2),(a2,b4),(a3,b3),(a5,b5)?重复上述过程，已找不到 M′可扩路。所以 M′就是最大匹配。
第 9章 图论第 9章 图论定义 9.7.6 设 G=?V1,V2,E?是二部图,M是 G的最大匹配,若 |M|=min?|V1|,|V2|?,则称 M为 G中的一个完备匹配,
此时若 |V1|≤|V2|,则称 M为 V1到 V2的一个完备匹配 。
定理 9.7.3 设 G=?V1,V2,E?是二部图,|V1|≤|V2|,G中存在 V1到 V2的完备匹配的充分必要条件是 V1中每 k个结点
(k=1,2,?,|V1|)至少和 V2中 k个结点相邻接 (该条件称为相异性条件 )。
证明,设 |V1|=q,G中存在 V1到 V2 的完备匹配 M，
|M|=min?|V1|,|V2|?=|V1|=q,则 V1中 q结点和 V2中 q个相异结点相邻接 。 相异性条件成立 。
以下证明只要满足相异性条件,G中最大匹配一定是完备匹配 。 设 M为 G中一个最大匹配 。
第 9章 图论若 M不是完备匹配,必存在 v?V1为 M的非饱和点 。 且必存在 e?E1=E-M与 v关联 。 否则 v将是孤立点,这与相异性条件相矛盾 。 并且 V2中与 v相邻接的结点都是 M的饱和点,若存在 u?V2(与 v相邻 )为非饱和点,则 M′=M∪?(v,u)?也是匹配,
这显然与 M为最大匹配矛盾 。 考虑从 v出发的尽可能长的所有
M交替路,由于 M是最大匹配,由定理 9.7.2可知,这些 M交替路都不是 M可扩路,即每条路异于 v的端点一定是 M的饱和点,于是这些端点全在 V1中 。
S=?w| w?V1且 w 在从 v出发的交替路上?
T=?w| w?V2且 w 在从 v出发的交替路上?
由于各条交替路的两个端点全在 S中,所以 |S|=|T|＋ 1。
这正说明 V1中 |T|＋ 1个结点只与 V2中 |T|个结点相邻接,这矛盾于相异性条件 。 因而 V1中不可能存在 M的非饱和点,故 M是完备匹配 。
下一定理给出了二部图存在完备匹配的充分条件,它能很容易地判断二部图是否存在完备匹配 。
第 9章 图论定理 9.7.4 设 G=?V1,V2,E?是二部图,如果存在某一整数 t＞ 0,使得 V1中的每个结点至少关联 t条边,而 V2中的每个结点至多关联 t条边 。 则 G中存在 V1到 V2的完备匹配 。
证明,由定理的条件知,V1中任意 k个结点 (k=1,2,?,
|V1|)至少关联 kt条边 。 因为 V2中的每个结点至多关联 t条边,
所以这 kt条边至少关联于 V2中的 k个结点 。 于是二部图 G满足相异性条件 。 由定理 9.7.3可知,G有 V1到 V2的完备匹配 。
图 9.64中的二部图满足定理 9.7.4的条件。其中 t=3。因此在图 9.64中存在 V1到 V2的完备匹配。
第 9章 图论第 9章 图论下列例题给出了完备匹配的一个应用 。
【 例 9.17】 在某大学本科毕业生分配的供需洽谈会上,
有 n个毕业生可从 m(m≥n)个单位选择自己职业 。 已知每个毕业生至少愿意去 r(1≤r≤m)个单位去工作,而每个用人单位至多看中了 r–1个毕业生,愿意从中选择一名 。 问最多有多少个单位可以选择到满意的毕业生？ 写出判断过程 。
解,设 V1=?v| v为毕业生?,V2=?u| u为用人单位?，
E=?(v,u)| v愿意到 u去工作?，
则 G=?V1,V2,E?是二部图，由已知条件可知,?v?V1，
deg(v)≥r，而?u?V2,deg(u)≤r–1≤r，由此可知,G满足定理
9.7.4的条件，其中 t=r，因此有 V1到 V2的完备匹配。于是有 n
个单位，也最多有 n个单位可以选择到满意的毕业生，每个毕业生都可选到愿意去的单位。
第 9章 图论图 9.65给出了 n=3,m=5,r=3的情况 。 在这种情况下,
请读者给出几种分配方案 。
返回章目录第 9章 图论
9.8平面图
9.8.1平面图的基本概念定义 9.8.1 设 G=?V,E?是无向图,如果能把 G的所有结点和边画在一个平面上,使得任何两边除端点外没有其它交点,则称 G为平面图,否则,称 G为非平面图 。
在图 9.67中 (a)是无向完全图 K3,它是平面图 。 (b)是无向完全图 K4,它虽有相交边,但适当调整边的位置得到 (c)。
在 (c)中任何两边除端点外没有其它交点,所以 K4为平面图 。
(d)是二部图 K1,3,K1,3是平面图 。 (e)是二部图 K2,3,经改画以后得到 (f)。 由定义 9.8.1知,K2,3是平面图 。 (g),(h)分别是
K5和 K3,3,无论怎样调整边的位置都不能使任何两边除端点外没有其它交点,所以不是平面图 。
第 9章 图论第 9章 图论无向完全 K5和完全二部图 K3,3是两个重要的非平面图,
它们在平面图理论的研究中有非常重要的作用 。
以下的三个结论是显然的 。
定理 9.8.1 若 G是平面图,则 G任何子图是平面图 。
由此定理可知,无向完全图 K4的任何子图是平面图,二部图 K2,3的任何子图也是平面图 。
定理 9.8.2 若 G是非平面图,则 G任何母图是非平面图 。
推论 无向完全图 Kn(n≥5)和二部图 K3,n (n≥3)都是非平面图 。
定理 9.8.3 若 G是平面图,则 G中增加平行边或自回路后所得的图还是平面图 。
本定理说明平行边与自回路不影响图的平面性,因此研究图的平面性时,不考虑平行边和自回路 。
第 9章 图论定义 9.8.2 若 G是平面图,由图中的边所包围的区域,在区域内既不包含图的结点,也不包含图的边,这样的区域称为图 G的一个面 。 其中面积无限的面称为无限面或外部面,
面积有限的面称为有限面或内部面 。 包围该面的诸边组成的回路称为该面的边界,边界的长度称为该面的次数,面 r的次数记为 deg(r)。
常将无限面记为 r0,有限面记为 r1,r2,
图 9.68是一个平面图,它有四个面,r0,r1,r2,r3。 其中 r0是无限面,其它三个面是有限面 。 r0的边界是由回路
abcda和回路 ffghijgf组成的,其次数 deg(r0)=11； r1的边界是由回路 abcdeda组成的,其次数 deg(r1)=6； r2的边界是由回路
ghijg组成的,其次数 deg(r2)=4； r3的边界是 f上的自回路,其次数 deg(r3)=1。
第 9章 图论第 9章 图论定理 9.8.4 设 G=?V,E?是有限平面图,有 n个面,则所有面的次数之和等于边数的 2倍 。 即 =2|E|
证明,G的任何一边,或者是两个面的公共边界,为每一个面的次数增加 1；或者在一个面中作为边界重复计算两次,为该面的次数增加 2。 无论那种情况 G的任何一边为图中面的次数和增加 2,故所有面的次数之和等于边数的 2倍 。
在图 9.68中,有 11条边,所有面的次数之和为：
deg(r0)+deg(r1)+deg(r2)+deg(r3)=11+6+4+1=22=2?11
定义 9.8.3 若 G是简单平面图,若在 G的任意不相邻结点 v,u之间加入边 (v,u),所得的图为非平面图,则称 G为极大平面图 。
)deg(
1
n
i
ir
第 9章 图论关于极大平面图有以下的几个结论：
① 极大平面图是连通图 。
② 结点数大于等于 3的极大平面图不可能存在割点和桥 。
③ 设 G为结点数大于等于 3的简单连通平面图,G为极大平面图当且仅当 G的每个面的次数均为 3。
限于篇幅,这三个结论的证明从略 。
9.8.2欧拉公式
1750年瑞士的数学家列昂哈德?欧拉 (Leonhard Euler)发现任何一个凸多面体,若有 n个顶点,m条棱和 r个面,总有
n-m+r=2成立 。 我们将这个结论推广到平面图中,总结成如下的定理：
第 9章 图论定理 9.8.5 (欧拉公式 )任意连通平面图 G,若有 n个结点,m条边和 r个面,则欧拉公式 n-m+r=2成立 。
证明,对边数 m归纳证明 。
⑴ 设 m=0,由于 G是连通图,所以 G只能是平凡图 。 这时,n=1,m=0,r=1,n-m+r=2成立 。
⑵设 m=k (k≥ 1)时欧拉公式成立，下证当 m=k+1时，欧拉公式也成立。
若 G是树,则 G是非平凡树,根据定理 9.6.2,G中至少有两片树叶 。 设 v为其中一片树叶 。 令 G′=G-?v?(从 G中删除结点 v,而得到 G′),则 G′仍然是连通图 。 设 n′,m′和 r′分别是 G′的结点数,边数和面数 。 则 n′=n-1,m′=m-1=k,r′
=r。 于是 n=n′+1,m=m′+1,r=r′。 因为 G′是连通图且 m′=k
,所以 G′满足归纳假设的条件 。 由归纳假设知：
n′-m′+r′ =2，
所以 n–m+r=( n′ +1)–(m′ +1)+r′ = n′-m′ +r′ =2。
第 9章 图论若 G不是树,则 G中含有回路 。 设边 e在 G的某个回路上 。
令 G′=G-?e?(从 G中删除边 e,而得到 G′),则 G′仍然是连通图 。 设 n′,m′和 r′分别是的结点数,边数和面数 。 则 n′=n，
m′=m-1=k,r′=r–1。 于是 n=n′,m=m′+1,r=r′+1。 因为 G′是连通图且 m′=k,所以 G′满足归纳假设的条件 。 由归纳假设知：
n′–m′＋ r′=2,所以
n–m+r= n′–(m′+1)+(r′+1)= n′-m′+r′=2。
欧拉公式成立是平面图的重要性质，条件是平面图的连通性。欧拉公式还可以推广到非连通的平面图中。将这个结果写成下面的定理：
第 9章 图论定理 9.8.6 设 G是平面图，有 k个连通分支,n个结点,m
条边,r个面，则公式 n-m+r=k+1成立。
证明,设 G的连通分支为 Gi,ni,mi和 ri分别是 Gi的结点数、边数和面数，根据定理 9.8.5,ni-mi+ri=2,i=1,?,k。
而 =m,=n，由于每一个 Gi有一个外部面，而 G只有一个外部面，所以 G的面数 r= -k+1，即 =r+k-1。
所以 2k= = = – ＋ =n-m+r+k-1
整理后有 n-m+r=k+1
由欧拉公式可以推出平面图的一些性质。
k
i
im
1
k
i
in
1
k
i
ir
1
k
i
ir
1
k
i 1
2 )(
1
ii
k
i
i rmn
k
i
in
1
k
i
im
1
k
i i
r
1
第 9章 图论定理 9.8.7 设 G是连通的平面图,有 n个结点,m条边,
每个面的次数至少为 k(k≥3),则关系式 m≤ 成立 。
证明,设 G中有 r个面,由定理 9.8.4知,2m= 。
因为每个面的次数大于等于 k,所以所有面的次数之和大于等于 kr,于是,2m= ≥kr。 即 2m≥kr。 代入欧拉公式
r=2 +m-n,得 2m≥kr=k(2+m–n),整理得,m≤ 。
)2(2 nk k
)d eg (
1
r
i
ir
)deg(
1
r
i
ir
)2(2 nk k
第 9章 图论
【 例 9.18】 利用上述定理证明 K5和 K3,3都不是平面图 。
解,K5如图 9.67(g)所示,结点数 n=5,边数 m=10。
假设 K5是平面图 。 显然 K5是连通的,因为 K5中无自回路和平行边,所以每个面的次数至少为 3,即定理 9.8.7中的 k=3，
K5满足定理 9.8.7的条件 。 所以应有
m≤
但是,代入 n=5,m=10和 k=3得 10?9=,
矛盾 。 所以 K5不是平面图 。
K3,3如图 9.67 (h) 所示,结点数 n=6,边数 m=9。
假设 K3,3是平面图 。 显然 K3,3连通的,因为在 K3,3中任何三个结点,其中必有两个是不相邻接的,所以每个面的次数大于等于 4,即定理 9.8.7中的 k=4,K3,3满足定理 9.8.7的条件 。 所以应有
)2(2 nk k
)25(23 3
第 9章 图论
m≤
但是,代入 n=6,m=9和 k=4得 9?8=,矛盾 。
所以 K3,3不是平面图 。
定理 9.8.8 设 G是平面图,有 s个连通分支,n个结点,m
条边,每个面的次数至少为 k (k≥3),则 m≤
成立 。
利用欧拉公式推广形式容易证明此定理，留作练习。
)2(2 nk k
)26(24 4
)1(2 snk k
第 9章 图论定理 9.8.9 设 G是简单平面图,有 n(n≥3)个结点,m条边,
则 m≤3n-6
证明,设 G有 s (s≥1)个连通分支 。
若 G为树或森林,根据定理 9.6.1，
m=n-s≤n=n+6-6=n+3+3-6≤n+n+n-6=3n–6。
即 m≤3n–6
若 G不是树,也不是森林,则 G中必含有回路 。 又因为
G是简单平面图,所以其中的回路的长度均大于等于 3,因而各面次数 k≥3,又 =1+,当 k=3 时,达到最大值 3,由定理 9.8.8有：
m≤ ≤3(n-s-1)≤3(n-1-1)≤3n-6
2?k
k
2
2
k
)1(2 snk k
第 9章 图论定理 9.8.10 设 G是极大平面图,有 n(n≥3)个结点,m条边,
则 m=3n–6
证明,设 G有 r个面 。 由于极大平面图是连通图,所以 G
是连通图 。 由欧拉公式得 r=2+m-n,又因为 G是极大平面图,
G的每个面的次数均为 3,所以 2m= =3r=3(2+m-n)。
整理后,m=3n–6。
定理 9.8.11 设 G是简单平面图,则 G的最小度?(G)≤5。
证明,设 G有 n个结点,m条边 。
当 n≤6,因为 G是简单图,由定理 9.1.3知,
(G)≤?(G)≤5。
以下证 n≥7的情况,若?(G)≥6,即每个结点的度数大于等于 6,G中所有结点度数之和大于等于 6n。 于是
2m= ≥6n,m≥3n＞ 3n–6,即 m＞ 3n–6，
与定理 9.8.9矛盾 。
)deg(
1
r
i
ir
)d eg (
1
n
i
iv
第 9章 图论在给定图 G的边上插入一个新的度数为 2的结点,使一条边分成两条边,如图 9.69(a)所示,叫做插入一个 2度结点；对于度数为 2的结点,去掉这个结点,使它关联的两条边变成一条边,如图 9.69(b)所示,叫做去掉一个 2度结点 。
定义 9.8.4 给定两个图 G1和 G2,如果它们是同构的,或者通过反复插入一个 2度结点或去掉一个 2度结点后使 G1和 G2
同构,则称 G1和 G2在 2度结点内同构或 G1和 G2同胚 。
定理 9.8.12(Kuratowski定理 1)一个图是平面图当且仅当它不包含与 K3,3或 K5在 2度结点内同构的子图 。
本定理的证明从略 。
第 9章 图论定义 9.8.5 设 G=?V,E?是无向图,e?E,在 G中删除 e,将 e
的两个端点 u和 v合并成一个新端点,记为 w。 w关联除 e以外 u
和 v关联的所有边,称为边 e的收缩 。 如果对图 G的某些边进行收缩,得到图 G′,则称将 G收缩到 G′。
定理 9.8.13 (Kuratowski定理 2)一个图是平面图当且仅当它既没有收缩到 K5的子图,也没有收缩到 K3,3的子图 。 (证明略 )
9.8.3平面图的对偶图定义 9.8.6 设 G=?V,E?是平面图,它具有面 r1,r2,?,rn，
若有图 G*=?V*,E*?满足下述条件：
⑴ 对于图 G的任何一个面 ri,内部有且仅有一个结点?V*。
⑵ 对于图 G的面 ri,rj的公共边界 ek?E,存在且仅存在一个边?E*,使 =(,)且 与 ek相交 。
⑶ 当且仅当 ek只是一个面 ri的边界时,存在一个自回路与 ek相交 。
则称图 G*是平面图 G的对偶图 。
*iv *
jv
*iv
*ke*
ke
*ke
*iv
*ke
第 9章 图论在图 9.71中,设实线边的图是 G,则虚线边的图是 G的对偶图 G*。
从定义可以看出平面图 G
的对偶图 G*有以下的性质：
① G*是连通平面图 。
② G*是图 G的对偶图,G也是图 G*的对偶图 。
③ 若边 e为 G中的自回路,
则在 G*中,与 e对应的边 e*为桥；
若边 e为桥,则在 G*中,与 e对应的边 e*为自回路 。
④ 在多数情况下,G*是多重图 。
第 9章 图论定理 9.8.14 设 G是连通平面图,G*是图 G的对偶图 。 m、
n和 r分别是 G的结点数,边数和面数 。 m*,n*和 r*分别是 G*的结点数,边数和面数 。 则
⑴ n*=r
⑵ m*=m
⑶ r*=n
⑷ 设 G*的结点 位于 G的面 ri中,则 deg( )＝ deg(ri)。 其中,deg( )是结点 的度数,deg(ri)是面 ri的次数 。
证明,根据定义 9.8.6,⑴,⑵ 显然 。
⑶ 由于 G与 G*都是连通平面图,因而满足欧拉公式,n–
m+r=2。 n*–m*+r*=2。 故 r*=2-n*+m*=2-r +m=2+m–r= n
⑷ 设 G的面 ri的边界为 Ci,设 Ci中有 k1个桥,k2个非桥边,
于是 Ci的长度为,2k1+k2,即 deg(ri)=2k1+k2；而 k1个桥对应面
ri中的结点 处有 k1个自回路,k2个非桥边对应从 处引出 k2
条边,即 deg( )=2k1+k2；从而 deg( )=deg(ri)。
*iv*iv
*iv *iv
*iv *iv
*iv*iv
第 9章 图论定理 9.8.15 设 G是平面图,具有 k(k≥2)个连通分支,G*是图 G的对偶图 。 m,n和 r分别是 G的结点数,边数和面数 。 m*、
n*和 r*分别是 G*的结点数,边数和面数 。 则
⑴ n*=r
⑵ m*=m
⑶ r*=n-k+1
⑷ 设 G*的结点 位于 G的面 ri中,则 deg( )=deg(ri)。 其中,deg( )是结点 的度数,deg(ri)是面 ri的次数 。
本定理的证明从略 。
定义 9.8.7如果 G的对偶图 G*与 G同构,则称 G为自对偶图 。
在图 9.72的 (a),(b)中，设实线边图是 G，则虚线边图是
G的对偶图 G*。可以看出图 G和它的对偶图 G*是同构的。所以，图 9.71(a),(b)中的实线边图都是自对偶图。
*iv
*iv
*iv
*iv
第 9章 图论定义 9.8.8 设 G是一个无自回路图,对 G的每一个结点指定一种颜色,使相邻接结点具有不同颜色,称为对图 G的正常着色,简称着色 。 如果图 G着色时用了 n种颜色,则称图 G
为 n色的 。 对图 G着色时,需要的最少颜色数,称为 G的着色数,记为 X(G)。
第 9章 图论对图 G的正常着色有一个简单而有效的方法,叫韦尔奇?
鲍威尔 (Welch Powell)方法,它的基本思想如下：
① 将图 G中的结点按照度数的递减次序进行排列 。 (这种排列可能不惟一,因为有些结点有相同度数 。 )
② 用第一种颜色对第一个结点着色,并且按排列次序,
对与前面着色结点不邻接的每一个结点着上同样的颜色 。
③ 用第二种颜色对尚未着色的结点重复 ②,用第三种颜色继续这种做法,直到所有结点全部着上色为止 。
第 9章 图论
【 例 9.19】 用韦尔奇?鲍威尔法对图 9.73着色 。
解：
① 按照度数递减次序排列各结点,b,f,a,c,e,g,d,h。 他们的度数分别是,4,4,3,3,3,3,2,2。
② 用第一种颜色对 b着色,并对与 b不相邻的结点 g也着这种颜色 。
③ 对结点 f和 c着第二种颜色 。
④ 对结点 a,d和 h着第三种颜色 。
⑤ 对结点 e着第四种颜色 。
因此 G是四色的 。 注意 G不可能是三色的,因为 a,b,e,f
相互邻接的,故必须着四种颜色 。 所以 X(G)=4。
从定义 9.8.8可以看出下列定理成立：
第 9章 图论定理 9.8.16 X(G)=1当且仅当 G是零图 。
定理 9.8.17 设 G中至少含有一条边，则 X(G)=2当且仅当 G是二部图。
第 9章 图论定理 9.8.18 X(Kn)=n。
证明,因为 n个结点的完全图的每一个结点与其它 n-1
个结点都邻接,故 n 个结点的着色数不能少于 n,又 n个结点的着色数至多为 n,X(Kn)=n。
定义 9.8.9 对地图 G的每个国家涂上一种颜色,使相邻的国家涂不同的颜色,称为对地图 G的一种面正常着色,简称着色 。 如果对图 G着色时,用了 n种颜色,则称地图 G为 n
色的 。 对图 G着色时,需要的最少颜色数,称为 G的着色数,
记为 X *(G)。
研究地图的着色可以转化成对它的对偶图的结点着色,
见下面定理 。
定理 9.8.19 地图 G是 n色的当且仅当它的对偶图 G*是 n色的 。
第 9章 图论证明,设地图 G是 n色的,下证它的对偶图 G*是 n色的 。
因为地图 G连通,由定理 9.8.14可知,n*=r,即 G的每个面中含 G*的一个结点 。 设 位于 G的面 ri内 。 将 G*的结点 涂
ri的颜色,易知,若 与 相邻,则由于 ri与 rj的颜色不同 。 所以,与 的颜色也不同,因而 G*是 n色的 。
当 G的对偶图 G*是 n色的,类似的可以证明 G也是 n色 。
由定理 9.8.19可知,研究地图的着色 (面着色 )等价于研究平面图的结点着色 。 对于平面图的点着色问题,到目前为止,人们证明了下面定理 。
定理 9.8.20 任何平面图 G最多是 5色的 。
本定理的证明略 。
定理 9.8.20 称为五色定理，也称为希伍德 (Hewood)定理。
*iv
*iv
*iv
*jv
*jv*iv
返回章目录 返回总目录
