离散数学及其应用-第2版 课件 第9章特殊图

第9章

特殊图第9章特殊图9.1欧拉图与哈密顿图9.2带权图9.3匹配和二分图9.4平面图9.1欧拉图与哈密顿图哥尼斯堡七桥问题、周游世界问题欧拉图定义9.1.1

设G=（V，E）是无向图或有向图，若G中有一条包含所有边（有向边）的简单回路，称该回路为欧拉回路，称图G为欧拉图。若G中有一条包含G中所有边（有向边）的简单通路，称它为欧拉通路，称图G为半欧拉图。欧拉图半欧拉图例题b-c-d-b-e-c-a-b

b-d-c-e-b-a-c

例9.1.1

在下面的图中，哪些有欧拉回路？没有欧拉回路的图中，哪些有欧拉通路？欧拉图的判断定理9.1.1

无向连通图G是欧拉图，当且仅当G的所有结点的度数都是偶数。定理9.1.2

连通无向图G为半欧拉图，当且仅当G中只有两个奇度数的结点。定理9.1.1证明定理9.1.1

无向连通图G是欧拉图，当且仅当G的所有结点的度数都是偶数。证明：（必要性）设G是欧拉图，则G有欧拉回路C。设a是图G的任一结点，欧拉回路经过和a关联的边到结点a后又经过另一条和a关联的边离开到下一个结点b，因此每经过一个结点a就给它的度数贡献2度。若欧拉回路k次经过结点a，则d（a）=2k。所以，欧拉图的所有结点的度数都是偶数。（充分性）假设G中所有结点的度数都是偶数。从G中的任一结点v1开始，经过任一和v1关联的边e1到另一结点v2，再经过另一和v2关联的边e2到另一结点v3，

依此类推，可以得到一条包含G的边的简单回路C1：v1

e1

v2

e2

v3

em

v1。定理9.1.2证明定理9.1.2

连通无向图G为半欧拉图，当且仅当G中只有两个奇度数的结点,其余结点的出度和入度相等。证明在连通无向图G的两个奇度数的结点之间加一条边e得到图G

，则图G

的所有结点的度数都是偶数，有欧拉回路。在G

的欧拉回路中删去这条边e，则可得到一条包含G中所有边的欧拉通路。因此图G是半欧拉图。例题例9.1.2

在下图中，哪些是欧拉图？哪些是半欧拉图？欧拉图欧拉图半欧拉图欧拉有向图定义9.1.2

如果连通有向图G中有一条包含G中所有有向边的有向回路，称它为欧拉有向回路，称图G为欧拉有向图。如果连通有向图G中有一条包含G中所有有向边的有向通路，称它为欧拉有向通路，称图G为半欧拉有向图。欧拉有向图半欧拉有向图欧拉有向图的判断定理9.1.3

连通有向图G是欧拉图，当且仅当G中每个结点v的入度等于它的出度。定理9.1.4

连通有向图G是半欧拉图，当且仅当G中有且仅有两个奇度数结点，其中一个结点的入度比出度大1，另一个结点的入度比出度小1。例题例9.1.3

在图中，哪些是欧拉图？哪些是半欧拉图？欧拉图半欧拉图9.1.2哈密顿图环游世界问题哈密顿图定义9.1.3

设图G=（V，E）是无向图或有向图。若G中有一条包含G的所有结点(仅一次)的回路，称该回路为哈密顿回路，称图G为哈密顿图。若图G有一条包含G的所有结点的通路，称该通路为哈密顿通路，称图G为半哈密顿图。(1)是半哈密尔顿图(2)为哈密尔顿图(3)没有哈密顿通路，也没有哈

密顿回路哈密顿图存在的必要条件定理9.1.5

设无向图G=（V，E）是哈密顿图，则对于结点集V的每一个真子集S均有：W(G-S)

|S|,其中，W(G-S)是G-S的导出子图的连通分支数。例如：彼德森图中对于结点集V的每一个真子集S均有：W(G-S)

|S|。但彼德森图不是哈密顿图。哈密顿图存在的必要条件证明：设C为G中的一条哈密尔顿回路。对于V的任何一个非空子集S，在C中删去S中任一结点v1，则C-v1是连通的非回路。若再删去任一结点v2，分两种情况讨论：如v2

和v1邻接，则C-v1-v2是连通的；如v2

和v1不邻接，则C-v1-v2是不连通的，W(C-v1-v2)=2。所以，删去两个结点时有W(C-v1-v2)

2。依此类推，显然有W(C-S)

|S|。又因为C是G的生成子图，所以C-S是G-S的生成子图，因而W(G-S)

W(C-S)。因此有W(G-S)

|S|。例题例9.1.4

说明下图

所示的无向图G不是哈密顿图。解

在图中删去结点集S={v2，v4，v6，v8}，W(G−S)=5，不满足W(G-S)

|S|。所以G不是哈密顿图。哈密顿图存在的充分条件定理9.1.6

如果G是有n个结点的简单无向图，对于每一对不邻接结点u和v，满足d(u)+d(v)

n-1，那么G中存在哈密顿通路，图G是半哈密顿图。证明：首先用反证法证明图G是连通的。假设图G不连通，它至少有两个连通分支G1=（V1，E1）和G2=（V2，E2）。取任意结点v1

V1，v2

V2，因为G是简单无向图，所以d（v1）

|V1|-1，d（v2）

|V2|-1，因而d（v1）+d（v2）

|V1|+|V2|-2=n-2，与已知条件矛盾，所以图G是连通的。定理9.1.6证明（续1）证明：证明G中存在哈密顿通路。设L：v1v2

vk

是G的最长的基本通路，显然k

n。因为L是G的最长的基本通路，所以v1

和

vk的邻接点都在L上。若k=n，则L为G中经过所有结点的通路，即为哈密顿通路。若k<n，说明G中存在不在L上的结点。此时可以证明存在仅经过L上的所有结点的基本回路，证明如下：第一种情况：若在L上v1和vk相邻，则v1v2

vkv1是经过L上所有结点的基本回路。定理9.1.6证明（续2）第二种情况：若在L上v1和vk不相邻，设v1与L上的结点

vj1=v2,vj2,

vjm相邻（m

2，否则d(v1)+d(vk)

1+k-2<n-1），这时vk必与vj2

vjm

的邻接结点vj2-1

vjm-1之一相邻（否则d(v1)+d(vk)

m+k-2-(m-1)<n-1）。设vk与vjr-1（2

r

m）相邻，如图所示。在L中添加边（v1,vjr），（vk，vjr-1），删除边（vjr，vjr-1）得基本回路C=v1v2

vjr-1vkvk-1

vjrv1，经过L上的所有结点。定理9.1.6证明（续3）证明存在比L更长的通路。因为k

n，G中必有不在L上的结点vk+1。由于G是连通的，vk+1与L上的一个结点vt邻接，在L上删除边（vt-1，vt），添加边（vt，vk+1），于是可得到一条长度为k+1的基本通路vt-1

v1vjr

vkvjr-1

vtvk+1。重复（1）~（3），由于G中的结点数目有限，一定能在有限步内得到一条哈密顿通路。哈密顿图的充分条件推论1

如果图G是有n个结点的简单无向图，对于每一对不邻接结点u和v，满足d(u)+d(v)

n，那么G中存在哈密顿回路，图G是哈密顿图。推论2

如果G是有n个结点的简单无向图，G中每个结点的度数都至少为n/2，那么图G是哈密顿图。例题半哈密顿图哈密顿图非哈密顿图

非半哈密顿图应用1例9.1.5有7个人,A会讲英语,B会讲英语和汉语,C会讲英语、意大利语和俄语,D会讲日语和汉语,E会讲德语和意大利语,F会讲法语、日语和俄语,G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈,使得每个人都能与两旁的人交谈?图G的一条哈密顿回路是ABDFGECA，按这条哈密顿回路安排就坐成一圈,每个人都能与两旁的人交谈。应用2-格雷码例9.1.6

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码。表9.1.1是2位格雷码，表示数0~3，表9.1.2是3位格雷码，表示数0~7。格雷码用格雷码表示的最大数与最小数之间也仅一位数不同，即“首尾相连”，因此这种编码又称循环码。在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（如0110、1111等）。在特定情况下可能导致电路状态错误或输入输出错误。使用格雷码，变化到下一状态时只有1位不同，可以避免这种错误。格雷码要找到格雷码，可以用n立方体Qn来建模。在Qn图上找一条哈密顿回路，按哈密顿回路上的结点顺序对应的二进制码序列就是格雷码。例如，9.2带权图设G=<V,E,W>，V={v1，v2，…，vn}是顶点集合，E是边集合，W:VVR是赋值函数。旅行商问题(TSP)完全无向图的每个结点表示一个城市，用两个城市之间的距离作为边的权，可以得到一个边带权的完全无向图。旅行商问题是在这样的图中寻找一条旅行总距离最短的经过每个城市一次且仅一次，又回到出发城市的旅行线路的问题。这个问题等价于求带权完全图中总权值最小的哈密顿回路。9.2.1旅行商问题47,36,35旅行商问题n个结点的图上，以每个结点为起点的所有的哈密顿回路共有(n-1)!条，需要计算(n-1)!/2条回路的权值来求出答案。当结点较多时用这种方法解决旅行商问题是不切实际的，常用近似算法求解旅行商问题。

9.2.2最短路径问题在一个无向简单连通边带权图G=（V，E，W）中，从u到v的一条通路中包含的各条边的权值之和称为这条通路的长度。从u到v的所有通路中长度最短的通路称为u到v的最短路径。求给定两结点之间的长度最短的通路问题称为最短路径问题uadv是u到v的最短路径Dijkstra算法算法思想：构造一个结点集S。首先在图中的除u外的所有结点中找到距离u最近的结点，把该结点加入结点集S后，在剩余的结点中再求距离u最近的结点，按和u距离由近到远依次加入S，直到把结点v加入结点集S，即求得从u到v的最短路径。Dijkstra算法方法：采用给结点标记距离值的方法构造结点集S。加入到S中的结点标记为永久性标记，未加入到S中的结点标记为临时性标记放在集合T中。一个结点的永久性标记值是从u到该点的最短路径的长度。首先将u标记为0，其余结点为临时标记，值为

，然后通过逐步修改临时标记的结点的标记值，将其中的最小标记值的结点从集合T中移出，加入到集合S中。当结点v被加入到集合S中时，它的标记值就是从u到v的最短路径的长度，则求得从u到v的最短路径。Dijkstra算法若图G的结点u=v0，v1，，vn=v，权为W（vi，vj），如果（vi，vj）不是图G的边则W（vi，vj）=

。引入一个“中转点”标记t，如果两个结点vi和vj间路径长度，大于这两点通过“中转点”连接的路径长度，那么就修改这两点间的路径为vi-t-vj.Dijkstra算法步骤（1）初始化标记值。起始结点u的标记值为0，其余结点临时标记值为

，即L（u）=0，L（vi）=

，i=1，2，，n。S={u}，其余结点在集合T中。（2）修改集合T中和结点u相邻的结点vi的标记值：L（vi）=L（u）+W（u，vi）。（3）将集合T中具有最小标记值的结点移出，添加到结点集S中，并将该结点记为中转点t。（4）修改集合T中和中转点t相邻的结点vj的标记值：L（vj）=min（L（vj），L（t）+W（t，vj））。重复（3）和（4）直到结点v被添加到集合S中。Dijkstra算法9.2.3中国邮路问题一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他负责范围内的每一条街道，如何选择投递路线，邮递员可以走尽可能少的路程？这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮路问题．用图论的术语，在一个连通的带权图G=（V，E，W）中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的总权值最小，也就是说要从包含G的每条边的回路中找一条总权值最小的回路。中国邮路问题如果G是欧拉图，只要求出图G的一条欧拉回路即可。因此问题就转化为：在一个连通的带权图G（V，E，W）中，要寻找一条回路，使该回路包含G中的每条边至少一次（当图G不是欧拉图时可能包含一些边超过一次），且该回路的总权值最小。中国邮路问题首先注意到，若图G有奇数度结点，则G的奇数度结点必是偶数个．把奇数度结点配为若干对，每对结点之间在G中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E1．令G1=G+E1，即把附加边子集E1

叠加在原图G上形成一个多重图G1，这时G1中没有奇度数结点．显然G1是一个欧拉图，因而可以求出G1的欧拉回路．该欧拉回路不仅通过原图G中每条边，同时还通过E1

中的每条边，且均仅一次．邮递员问题的难点在于当G的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E1

的权数W(E1)为最小。中国邮路问题定理9.2.1设G（V，E，W）为一个连通的带权图，则使附加边子集E1

的各条边的权值和W(E1)为最小的充分必要条件是G+E1

中任意边至多重复一次，且G+E1

中的任意回路中重复边的权值之和不大于该回路各条边的权值和的一半。证明

（略）中国邮路问题先找出奇结点；对奇结点进行配对，找到每对结点间的一个基本通路，给每条通路所含的边加一条平行边；删去多于两条的重复边；检查每一条回路，若一条回路中重复边的权值和大于该回路权值的一半，把该回路的重复边删去，在没有平行边的边上加上平行边；若没有任何回路的重复边的权值之和大于该回路权值的一半，图中的任意一条欧拉回路就是最优邮路．中国邮路问题

（a)(b)

（c)(d)9.2.4关键路径定义9.2.1：在一个表示工程的带权有向图中，用结点表示事件（如v0），用有向边表示活动（如<v0,v1>=a1），边上的权值表示活动的持续时间，称这样的有向图为边表示的活动的网，简称AOE网（activityonedgenetwork）。在AOE网中，入度为0的结点称为源点，出度为0的结点称为汇点。定义9.2.2：在AOE网中，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。。AOE网在AOE网中，假设源点是v0，从v0到vi的最长路径长度叫做事件vi的最早发生时间，记为ve[i]。在AOE网中，只有结点vj代表的事件发生，以vj为起点的活动ai才能开始，即活动ai的最早开始时间等于该活动的起点表示的事件vj的最早开始时间。活动ai的最早开始时间记为ae[i]，ae[i]=ve[j]。在不推迟整个工程完成的前提下，活动ai最迟必须开始的时间是该活动的终点表示的事件的最迟发生时间和该活动的持续时间的差，称为活动ai的最迟开始时间，记为al[i]。在不推迟整个工程完成（即保证结束结点vn在ve[n]时刻发生）的前提下，事件vi最迟必须发生的时间，称为事件vi的最迟发生时间，记为vl[i]。关键活动al[i]=ae[i]的活动称为关键活动，要识别AOE网的关键活动就是找al[i]=ae[i]的活动。求al[i]和ae[i]：首先应求得事件的最早发生时间ve[i]和最迟发生时间vl[i]。活动ai由有向边<vi,vj>表示，持续时间记为weight(<vi,vj>),则活动ai的最早开始时间等于事件vi的最早发生时间，即ae[i]=ve[i]。活动ai的最迟开始时间等于事件vj的最迟发生时间减去活动的持续时间，即al[i]=vl[i]-weight(<vi,vj>)。关键活动ve[i]和vl[i]可以用下面的递推公式，分两步计算。第一步：从源点向汇点方向递推计算ve[i]。从指向事件vj的有向边的活动中，取最晚完成的一个活动的完成时间作为vj的最早发生时间ve[i]，即：ve[源点]=0，ve[j]=max(ve[i]+weight<vi,vj>)，<vi,vj>为所有到达vj的有向边。第二步：从汇点向源点方向递推计算vl[i]。由上一步可以求得汇点的最早发生时间ve[汇点]。因为汇点就是结束点，最迟发生时间和最早发生时间相同，即vl[汇点]=ve[汇点]。从结点vi出发的有向边表示的的活动中，取最早开始的活动的开始时间作为vi的最迟发生时间vl[i]，即：vl[汇点]=ve[汇点]，vl[i]=min(vl[j]-weight<vi,vj>)，<vi,vj>为所有从vi出发的有向边。例题例9.2.3：求图8.2.6的AOE网的关键路径。解：从源点向汇点方向递推计算事件的最早发生时间：ve[1]=0ve[2]=ve[1]+a1=0+3=3ve[3]=ve[1]+a2=0+2=2ve[4]=max(ve[2]+a3,ve[3]+a4)=max(3+2,2+4）=6ve[5]=ve[2]+a5=3+3=6ve[6]=max(ve[5]+a7,ve[4]+a6，ve[3]+a8)=max(6+2,6+1，2+6)=8从汇点向源点方向递推计算事件的最迟发生时间：vl[6]=ve[6]=8vl[5]=vl[6]-a7=8-2=6vl[4]=vl[6]-a6=8-1=7vl[3]=min(vl[6]-a8，vl[4]-a4）=min(8-6，7-4)=2vl[2]=min(vl[5]-a5，vl[4]-a3)=min(6-3,7-2)=3vl[1]=min(vl[2]-a1，vl[3]-a2)=min(3-3,3-2)=0例题（续）活动的最早发生时间：ae[1]=ve[1]=0ae[2]=ve[1]=0ae[3]=ve[2]=3ae[4]=ve[3]=2ae[5]=ve[2]=3ae[6]=ve[4]=6ae[7]=ve[5]=6ae[8]=ve[3]=2活动的最迟发生时间：al[1]=vl[2]-a1=3-3=0al[2]=vl[3]-a2=2-2=0al[3]=vl[4]-a3=7-2=5al[4]=vl[4]-a4=7-4=3al[5]=vl[5]-a5=6-3=3al[6]=vl[6]-a6=8-1=7al[7]=vl[6]-a7=8-2=6al[8]=vl[6]-a8=8-6=2关键活动有：a1、a2、a5、a7、a8，所以关键路径为v1-v2-v5-v6和v1-v3-v6。一个AOE网的关键路径可能有多条。9.2.5网络与网络流定义9.2.3：设G=（V，E）是一个无多重边和环的有向连通图，V是结点集，E是弧集。若图G满足如下条件：只有一个结点的入度为0，记为s，称为源点；只有一个结点的出度为0，记为t，称为汇点；在弧集E上定义一个非负整数集合C={cij}，每条弧(vi,vj)

E都有一个非负的权值cij，称之为弧的容量；则称图G是一个网络或流网络，记为G=（V，E，C）。称源点和汇点以外的其他结点为中间点。有向边也称为弧。流网络网络与网络流定义9.2.4：在网络G=（V，E，C）的弧集E上定义一个非负整数值函数f:(vi,vj)→{fij=f(vi,vj)},f满足下列条件：(1)容量限制：对

e=(vi,vj)

E，有fij≤cij；(2)流量守恒：对于除s和t外的每个中间点k，称f为网络G上的一个可行流，简称流，称fij

为弧(vi,vj)上的流量。若无弧（i,j)，则fij

定义为0。如果弧e=(vi,vj)满足fij

=cij，则称e为饱和弧，若fij<cij，则称e为非饱和弧；称fij

=0的弧为零流弧，fij>0的弧为非零流弧。网络流图用cij/fij表示弧(vi,vj)上的容量和流量。容量限制是流经每条弧的流量值应当不超过该弧的容量，流量守恒是对于除s和t外的每个中间点k，总流入量和总流出量应当守恒，即流量不生成也不损耗。最大流定义8.2.5：设f是网络G的一个流，源s的总流出量

，称为流

f的流量或者值。若G中无可行流f'，使Vf'>Vf，则称f为最大流。由于汇t的总流入量

，所以对于s和t有最小割定义9.2.6：设G=（V，E，C）是一个单源单汇网络。S⊆V,

T=V-S.用(S,T)表示起点在S中而终点在T中的所有弧的集合。若(S,T)是图G的弧割集，而且源点s∈S,汇点t∈T,则称弧割集(S,T)为网络G的一个s-t割。s-t割(S,T)的容量是指从S穿出，进入T的各条弧的容量之和，记为Cap(S,T)，即：定义8.2.7：对于网络G的s-t割(S,T)，若不存在s-t割(S',T')，使得Cap(S',T')

Cap(S,T)，则称(S,T)为最小割。定理定理9.2.2：对于给定的网络G=（V，E，C），设f是一个可行流，(S,T)是任一s-t割，则Vf≤Cap(S,T)。定理9.2.2告诉我们，网络G中任何可行流f的值小于等于任一割的容量，因而有最大流的值小于等于最小割的容量。定理定理9.2.3：对于给定的网络G=（V，E，C），设f是一个流，(S,T)是一个s-t割。若Vf=

Cap(S,T),则f是一个最大流且(S,T)是一个最小s-t割。证明：假设f1是任意一个流，则由定理9.2.2有

，所以f是一个最大流。假设(S1,T1)是任意一个s-t割，则由定理9.2.2有所以(S,T)是一个最小割。最大流的标号算法(Ford,Fulkerson)1、标号过程给定网络G，初始流为f，先给源点s标号（0，

），

(s)=

。选择一个已标号的结点vi，对vi所有未标号的相邻结点vj，按下列规则标号:(a)在弧(vi,vj)上,当fij<cij时，则给vj标号(vi,

(vj)),这里

(vj)=min[

(vi),cij-fij)，当fij=cij时，vj不标号。(b)在弧(vi,vj)上,当fji>0时，则给vj标号(-vi,

(vj)),这里

(vj)=min[

(vi),fji)，当fij=0时，vj不标号。重复第（2）步直到收点t被标号为止，或不再有结点可以标号为止。如果汇点t被标号,表明得到一条从s到t的可增广路,转入调整过程。若汇点t未被标号,标号过程进行不下去时,则算法结束,此时的可行流就是最大流.最大流的标号算法(Ford,Fulkerson)2、调整过程（1）寻找以t为汇点的可增广路

若汇点t的第一个标号为vk（或-vk），则弧(vk,t)（相应地(t,vk)）是可增广路上的弧;接下来检查vk的第一个标号，若为vi（或-vi），则弧(vi,vk)（相应地(vk,vi)）是可增广路上的弧；依次下去，直到s点为止。此时被找到的弧构成可增广路

。（2）修改流f。对于可增广路

上的前向弧流量增加

(t),向后弧流量减少

(t),得到新的流f'。流f‘的值为（3）去掉结点上的标号，对流f'重新进行标号过程。如果在收点t没有标号，不再有结点可以标号，算法结束。用P表示所有已标号的结点集，

表示所有未标号的结点集，得到的

是最小割，它的容量等于最大流的值。9.3匹配和二分图定义9.3.1

在图G=(V，E)中,若M

E,且M中任意两条边都不相邻，则称M为G的一个匹配。若在M中再加入任意其它的边e，M

{e}有相邻的边，则称M为G的极大匹配。若G中不存在匹配M1，使得|M1|>|M|，则称M为G的最大匹配。定义9.3.2若M是G的一个匹配，M的边和结点v关联，则称v为M饱和点，否则称v为M非饱和点。若G=（V，E）的每个结点都是M饱和点，则称M为G的一个完美匹配。匹配就是边独立集，极大匹配就是极大边独立集，最大匹配是最大边独立集，匹配数是边独立数。例题(1).{e1,e7}是图的一个匹配，也是一个极大匹配，{e2,e4,e8}是图的最大匹配，也是完美匹配。(2).{e2,e6}、{e3,e5}是图的匹配，也是极大匹配，{e1,e4,e7}是图的一个最大匹配，也是完美匹配。(3).{e3,e4}、{e1,e5}、{e2,e6}、{e4,e7}等都是极大匹配，也是最大匹配，没有完美匹配。M交错路和M可扩充路定义9.3.3若M是G=（V，E）的一个匹配，从G中的一个结点到另一个结点存在一条由属于M的边和不属于M的边交替出现组成的简单路，则称这条简单路为M交错路。若M交错路的两端点为M非饱和点时，称这条M交错路是M可扩充路。最大匹配的充分必要条件在图（1）中，M={e1，e7}是图的一个匹配，{e2,e1,e4,e7,e8}是M交错路，而且是M可扩充路。匹配M1={e2,e4,e8}比M更大。

定理9.3.1

M是图G=(V，E)的最大匹配的充分必要条件是G中不存在M可扩充路。例题求右图的最大匹配。解

在图中，M={（v2，v6），（v3，v5），（v4，v7）}是匹配，v1v5v3v6v2v7v4v8是M交错路，而且是M可扩充路。因此，存在比M更大的匹配M1={（v1，v5），（v3，v6），（v2，v7），（v4，v8）}。由于不存在M1可扩充路，所以M1是最大匹配。9.3.2二分图定义9.3.4

如果无（有）向图G=（V，E）的结点集V能划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二分（部）图（或二部图，偶图），V1和V2称为互补结点集，二分图通常记为G=（V1，V2，E）。若V1中每一结点与V2中每一个结点均有且仅有一条边相关联，则称二分图G为完全二分图。若|V1|=m

，|V2|=n

，则记完全二分图G为Km，n。注意，n(n>=2）阶零图为二分图。二分图例如，一个单位有一些不同类型的工作空缺，有一些应聘者申请这些空缺的工作岗位。每个应聘者能胜任这些工作中的某些工作。如工作岗位集合为{u1，u2，u3}，应聘者集合为{v1，v2，v3，v4，v5}。每个应聘者能胜任的工作岗位可以图9.3.3所示的二分图表示，其中线uivj表示工作岗位ui适合应聘者vj。二分图完全二分图二分图的判断定理9.3.2

一个无向简单图G=（V，E）是二分图，当且仅当G中无奇数长度的回路。证明(必要性)设无向简单图G=（V，E）是二分图，V1

V2=V，V1

V2=

。对于G中任一长度为n的回路可表示为v1e1v2e2

vnenv1。设v1

V1，则v2

V2，v3

V1，v4

V2

vn

V2。所以n必为偶数。（充分性）设无向简单图G=（V，E）的所有回路的长度都是偶数。u是图G的任一结点，d（v，u）表示结点v到结点u的距离。二分图的结点集V的两个子集可以表示为：V1={v|d(v,u)为偶数}，V2=V-V1。如果存在一条边e的两端点vi和vj都在结点集V1中，则从vi到vj存在一条有偶数条边的通路L。通路L和边e可以构成一条回路，回路的长度为奇数。和假设矛盾。同理可证，没有一条边的两端点都在结点集V2中。由此可见，图G的每条边的端点，必定一个在结点集V1中，另一个在结点集V2中，而且V1和V2是G的互补结点集。所以图G是二分图。例题判断图9.3.6中的图是否是二分图。完备匹配和完美匹配定义9.3.5

设G=（V，E）是二分图，V1和V2是G的互补结点集，若G的一个匹配M使得|M|=min{|V1|，|V2|}，称匹配M是G的完备匹配。这时，若|V1|

|V2|，称M是从V1到V2的一个完全匹配。如果|V1|=|V2|，称M是G的完美匹配。完备匹配完美匹配没有完全匹配完备匹配定理9.3.3（Hall定理）

设二分图G=(V,E)，V1和V2

是G的互补结点集，存在从V1到V2的完备匹配,当且仅当对于V1中的任意k个结点（k=1,2,,|V1|）至少邻接V2的k个结点。

定理9.3.3中的条件通常称为相异性条件。定理9.3.4

设G=（V，E）是二分图，V1和V2

是G的互补结点集。若存在正整数t，使（1）V1中的每个结点至少关联t条边，（2）V2中的每个结点至多关联t条边，则G中存在从V1到V2的完备匹配。定理9.3.4证明证明

由条件（1）可知，V1中的k个结点至少关联kt条边（1

k

|V1|）。由条件（2）可知，这些边至少关联V2中的k个结点。因此，V1中的k个结点至少邻接V2中的k个结点。由Hall定理,G中存在完备匹配。定理9.3.4的条件常称为t条件，是判断二分图存在完备匹配的充分条件，不是必要条件。

判断条件t比较简单，只需计算V1中结点的最小度数和V2中结点的最大度数。例题要分派5位教师A，B，C，D，E去上课。A可以上课的时间是星期二和星期三，B的时间是星期一和星期三，C的时间是星期四，和星期五，D的时间是星期二和星期五，E的时间是星期一和星期四。应如何排课才可以使每天都只有一位教师上课？例题M={（A，p2），（B，p3），（C，p4），（D，p5），（E，p1）}9.4平面图定义9.4.1

设G=（V，E）是一个无向图，如果能把G画在平面上，使得除结点处外，任意两条边都不相交，则称G为可平面图，简称平面图。将一个平面图G，画成除结点处外，任意两条边都不相交的和它同构的图，称这样的图为图G的平面嵌入。例题判断图9.4.1中的各图是否是平面图。

（1）

（2）

（3）

（4）解

（1）（2）（4）不是平面图，而(3)是平面图。

平面图定义9.4.2设G是一个平面嵌入，G的边将G所在的平面划分成若干个区域，每个区域称为G的一个面。其中，面积无限的区域称为无限面或外部面，记成f0，面积有限的区域称为有限面或内部面，记为f1，f2…，fk

。包围每个面的所有边所构成的回路称为该面的边界。一个面的边界包含的边数称为该面的次数，记为deg(f)。平面图面f0的边界回路是一个复杂回路，Deg(f0)=9，面f1的边界回路是环，Deg(f1)=1，面f2和f3的边界回路是简单回路，Deg(f2)=3，Deg(f3)=3定理定理9.4.1

平面图G的边数为e，G的边将G所在的平面划分成l个面，所有面的次数之和等于边数e的2倍，即证明

对图G的每一条边e，若e在两个面的公共边界上，则在计算这两个面的次数时，e各提供1.当e只在一个面的边界上出现时，它必在一个面的边界上出现2次，如图

所示，因而在计算这个面的次数时，e提供2.因此所有面的度数之和等于边数e的2倍。

极大平面图和极小非平面图定义9.4.3：设G为简单平面图，若在G的任意两个不相邻的结点之间加一条边，所得图为非平面图，则称G为极大平面图。K5和K3,3，删去任意一条边都是极大平面图，另外，K1，K2，K3，K4都是极大平面图，因为在这些图中不存在两个不相邻的结点。定义9.4.4:若在非平面图G中任意删除一条边，所得图为平面图，则称图G为极小非平面图。K5和K3,3都是极小非平面图。欧拉公式定理9.4.2

设G为任意的连通的平面图，G中有n个结点，e条边，f个面，则有公式n-e+f=2成立。该公式称为欧拉公式。证明

对边数e用归纳法。例9.4.2假定连通平面图G有30条边，若G的边把图分成20个区域，则这个图有多少个结点？解

根据题意，连通平面图G的边数e=30，面数f=20，代入欧拉公式n-e+f=2得：n=2+e-f=2+30-20=12所以这个图有12个结点。欧拉公式的推论推论1

设G是有n

（n

3）个结点，e条边，f个面的简单连通平面图，边数e

3n-6。证明

当n=3时，3个结点的简单连通平面图的边数e

3,因此e

3n-6成立。当n

3时，G的每个面至少由3条边围成，即每个面的度数deg(fi)

3,所以所有面的总度数

deg(fi)

3f。而

deg(fi)=2e,因而有2e

3f,即f

2e/3。代入欧拉公式2=n-e+f

n-e+2e/3有e

3n-6成立。因此e

3n-6成立。欧拉公式的推论

定理定理9.4.3

设G是有n个结点，e条边的简单连通平面图，则G中至少存在一个结点v，使得d（v）

5。证明

假设G中每个结点v，都有d（v）

6，则由握手定理有6n

d（v）=2e即有e

3n

3n-6，与推论1矛盾。欧拉公式的推广定理9.4.4（欧拉公式的推广）设G为任意的平面图，G有k个连通分支，n个结点，e条边，f个面，则有公式n-e+f=k+1成立。插入和删去结点、同胚定义9.4.3

设e=（u，v）是图G的一条边，在G中删去边e，增加新的结点w，使u，v均与w相邻，则称在图G中插入2度结点w；设w为G的一个度数为2的结点，w与u，v相邻，删去w及与w相关联的边(w，u)，(w，v)，同时增加新边(u，v

)，则称在图G中删去2度结点w。定义9.4.4

若两个图G1和G2同构或通过反复插入或删除2度结点后是同构的，则称G1和G2是同胚的。平面图的充分必要条件定理9.4.5（库拉托斯基定理）设G是无向图，则G是平面图的充分必要条件是图G不含和K5或K3，3同胚的子图。推论

设G是无向图，则G是平面图的充分必要条件是图G没有可收缩为K5或K3，的子图。例题彼得森图中删去边（7,8）和（4,5）的子图，

和K3，3同胚。所以彼得森图不是平面图。9.4.3对偶图与着色定义9.4.5

设G是平面图。在图G的每个面中指定一个新结点，对两个面公共的边，指定一条新边与其相交。由这些新结点和新边组成的图称为G的对偶图G*。给定平面图G，用如下的方法构造G的对偶图G*：在G的每一个面fi中任取一个结点vi*作为G*的结点；若ek是G的两个面fi和fj的公共边，有一条边ek*=（vi*，vj*）作为G*的边，且（vi*，vj*）与ek相交；若ek只是G的一个面fi的边界时，以fi中的结点vi*为结点做环ek*，ek*与ek相交，ek*是G*的一个环。对偶图定理

设n、e、f分别为平面图G的结点数、边数和面数，n*、e*、f*分别为G的对偶图G*的结点数、边数和面数，按照对偶图的定义有n*=f,e*=e,f*=n。对偶图平面图G的一个平面嵌入的对偶图G*具有如下性质：(1)G*是平面图，而且是平面嵌入。(2)G*是连通的。(3)同构平面图的对偶图，不一定是同构的。(4)G的对偶图的对偶图也不一定与G同构。同构的图的对偶图不一定同构。G的对偶图的对偶图也不一定是与G同构。面着