离散数学—图论126版.ppt

第8章 图论第第8章章 图论图论 8.1 图的基本概念图的基本概念 8.2 路径和回路路径和回路8.图的矩阵表示图的矩阵表示8.二部图二部图8.5 平面图平面图8.6 树树8.7 有向树有向树8.8 运输网络运输网络问题是要从这四块陆问题是要从这四块陆地中任何一块开始，地中任何一块开始，通过每一座桥正好一通过每一座桥正好一次，再回到起点。次，再回到起点。欧拉在欧拉在17361736年解决了年解决了这个问题这个问题 。判定法则：如果通奇数座桥的地方不止两个，那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中任何一地出发找到所要求的路线。若没有一个地 方通奇数座桥，则从任何一地出发，所求的路线都能实现 第8章 图论定义8.11一个图图G是一个三重组V(G),E(G),G,其中V(G)是一个非空的结点结点(或叫顶点)集合,E(G)是边边的集合,G是从边集E到结点偶对集合上的函数。一个图可以用一个图形表示。例例1设G=V(G),E(G),G,其中V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d),G(e7)=(b,b)则图G可用图8.11表示。8.1 图的基本概念图的基本概念 8.1.1 图图第8章 图论第8章 图论定义中的结点偶对可以是有序的,也可以是无序的。若边e所对应的偶对a,b是有序的,则称e是有向边有向边。有向边简称弧,a叫弧e的始点,b叫弧e的终点,统称为e的端点。称e是关联于结点a和b的,结点a和结点b是邻邻接的接的。若边e所对应的偶对(a,b)是无序的,则称e是无无向边向边。无向边简称棱,除无始点和终点的术语外,其它术语与有向边相同。每一条边都是有向边的图称为有有向向图图,第三章中的关系图都是有向图的例子。每一条边都是无向边的图称为无无向向图图；如果在图中一些边是有向边,而另一些边是无向边,则称这个图是混混合合图图。我们仅讨论有向图和无向图,且V(G)和E(G)限于有限集合。第8章 图论约定用a,b表示有向边,(a,b)表示无向边,既表示有向边又表示无向边时用a,b。有向图和无向图也可互相转化。例如,把无向图中每一条边都看作两条方向不同的有向边,这时无向图就成为有向图。又如,把有向图中每条有向边都看作无向边,就得到无向图。这个无向图习惯上叫做该有向图的底有向图的底图图。在图中,不与任何结点邻接的结点称为弧立结点弧立结点；全由孤立结点构成的图称为零图零图。关联于同一结点的一条边称为自回路自回路；自回路的方向不定。自回路的有无不使有关图论的各个定理发生重大变化,所以有许多场合都略去自回路。第8章 图论在有向图中,两结点间(包括结点自身间)若同始点和同终点的边多于一条,则这几条边称为平行边平行边。在无向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为平行边。两结点a、b间互相平行的边的条数称为边边a,b的重数的重数。仅有一条时重数为1,无边时重数为0。定义8.12含有平行边的图称为多重图多重图。非多重图称为线图线图。无自回路的线图称为简单图简单图。在图8.13中,(a)、(b)是多重图,(c)是线图,(d)是简单图,关系图都是线图。第8章 图论图8.13第8章 图论定义8.13赋权图赋权图G是一个三重组V,E,g或四重组V,E,f,g,其中V是结点集合,E是边的集合,f是定义在V上的函数,g是定义在E上的函数。右图给出一个赋权图。V=v1,v2,v3 E=e1,e2=(v1,v2),(v2,v3)f(v1)=5,f(v2)=8,f(v3)=11g(e1)=4.6,g(e2)=7.5第8章 图论8.1.2结点的次数定义8.14在有向图中,对于任何结点v,以v为始点的边的条数称为结点v的引出次数(或出度),记为deg+(v);以v为终点的边的条数称为结点v的引入次数(或入度),记为deg-(v);结点v的引出次数和引入次数之和称为结点v的次数次数(或度数),记作deg(v)。在无向图中,结点v的次数是与结点v相关联的边的条数,也记为deg(v)。孤立结点的次数为零。第8章 图论定理8.11设G是一个(n,m)图,它的结点集合为V=v1,v2,vn,则证因为每一条边提供两个次数,而所有各结点次数之和为m条边所提供,所以上式成立。在有向图中,上式也可写成:第8章 图论定理8.12在图中,次数为奇数的结点必为偶数个。证 设次数为偶数的结点有n1个,记为 (i=1,2,n1)。次数为奇数的结点有n2个,记为 (i=1,2,n2)。由上一定理得因为次数为偶数的各结点次数之和为偶数。所以前一项次数为偶数;若n2为奇数,则第二项为奇数,两项之和将为奇数,但这与上式矛盾。故n2必为偶数。证毕。第8章 图论图8.15第8章 图论定义8.15各结点的次数均相同的图称为正则图,各结点的次数均为k时称为k正则图。下图所示的称为彼得森(Petersen)图,是3正则图。第8章 图论8.1.3图的同构定义8.1.6设G=V,E和G=V,E是两个图,若存在从V到V的双射函数,使对任意a、bV,a,bE当且仅当(a),(b)E,并且a,b和(a),(b)有相同的重数,则称G和G是同构的同构的。上述定义说明,两个图的各结点之间,如果存在一一对应关系,而且这种对应关系保持了结点间的邻接关系(在有向图时还保持边的方向)和边的重数,则这两个图是同构的,两个同构的图除了顶点和边的名称不同外实际上代表同样的组合结构。第8章 图论例2(a)、(b)两图是同构的。因为可作映射:g(1)=v3,g(2)=v1,g(3)=v4,g(4)=v2。在这映射下,边1,3,1,2,2,4和3,4分别映射到v3,v4,v3,v1,v1,v2和v4,v2,而后面这些边又是(b)中仅有的边。第8章 图论两图同构的必要条件:(1)结点数相等;(2)边数相等;(3)度数相同的结点数相等。但这不是充分条件。例如下图中(a)、(b)两图虽然满足以上3条件,但不同构。(a)中的x应与(b)中的y对应,因为次数都是3。但(a)中的x与两个次数为1的点u,v邻接,而(b)中的y仅与一个次数为1的点w邻接。第8章 图论8.1.4图的运算图的常见运算有并、交、差、环和等,现分别定义于下:定义8.17设图G1=V1,E1和图G2=V2,E2 (1)G1与G2的并,定义为图G3V3,E3,其中V3=V1V2,E3=E1E2,记为G3=G1G2。(2)G1与G2的交,定义为图G3V3,E3,其中V3=V1V2,E3=E1E2,记为G3=G1G2。(3)G1与G2的差,定义为图G3V3,E3,记为G3=G1-G2。其中E3=E1-E2,V3=(V1-V2)E3中边所关联的顶点。(4)G1与G2的环和,定义为图G3V3,E3,G3=(G1G2)-(G1G2),记为G3=G1G2。第8章 图论除以上4种运算外,还有以下两种操作:(1)删去图G的一条边e;(2)删去图G的一个结点v。它的实际意义是删去结点v和与v关联的所有边。第8章 图论8.1.5子图与补图定义8.18设G=V,E和G=V,E是两个图。(1)如果VV和EE,则称G是G的子图子图。如果VV和EE,则称GG的真子图真子图。(注意:“G是图”已隐含着“E中的边仅关联V中的结点”的意义。)(2)如果V=V和EE,则称G为G的生成子图生成子图。(3)若子图G中没有孤立结点,G由E唯一确定,则称G为由边集E导出的子图导出的子图。(4)若在子图G中,对V中的任意二结点u、v,当u,vE时有u,vE,则G由V唯一确定,此时称G为由结点集V导出的子图。第8章 图论第8章 图论定义8.19在n个结点的有向图G=V,E中,如果E=VV,则称G为有向完全图有向完全图;在n个结点的无向图G=V,E中,如果任何两个不同结点间都恰有一条边,则称G为无向完全图无向完全图,记为Kn。图8.111是4个结点的有向完全图和无向完全图的图示。定义8.110设线图G=V,E有n个顶点,线图H=V,E也有同样的顶点,而E是由n个顶点的完全图的边删去E所得,则图H称为图G的补图补图,记为,显然,。第8章 图论8.2 路径和回路路径和回路 8.2.1路径和回路定义8.21在有向图中,从顶点v0到顶点vn的一条路径路径是图的一个点边交替序列（v0e1v1e2v2envn）,其中vi-1和vi分别是边ei的始点和终点,i=1,2,n。在序列中,如果同一条边不出现两次,则称此路径是简单简单路径路径,如果同一顶点不出现两次,则称此路径是基本路径基本路径(或叫链)。基本路径也一定是简单路径。第8章 图论如果路径的始点v0和终点vn相重合,即v0=vn,则此路径称为回路回路,没有相同边的回路称为简单回路,通过各顶点不超过一次的回路称为基本回路。(a)P1=(v1e1v2e7v5)是一条基本路径。(b)P2=(v2e2v3e3v3e4v1e1v2)是一简单回路非基本回路。第8章 图论在无向图上,以上各术语的定义完全类似,故不重复。路径和回路可仅用边的序列表示,在非多重图时也可用顶点序列表示。第8章 图论定义8.22路径P中所含边的条数称为路径P的长度。长度为0的路径定义为单独一个顶点。(但注意习惯上不定义长度为0的回路。)定理8.21在一个具有n个结点的简单图G=V,E中,如果从v1到v2有一条路径,则从v1到v2有一条长度不大于n-1的基本路径。简证简证假定从v1到v2存在一条路径,(v1,vi,v2)是所经的结点,如果其中有相同的结点vk,例(v1,vi,vk,vk,v2),则删去从vk到vk的这些边,它仍是从v1到v2的路径,如此反复地进行直至(v1,vi,v2)中没有重复结点为止。此时,所得的就是基本路径。基本路径的长度比所经结点数少1,图中共n个结点,故基本路径长度不超过n-1。第8章 图论定理8.22在一个具有n个结点的简单图G=V,E中,如果经v1有一条简单回路,则经v1有一条长度不超过n的基本回路。定义8.23在图G=V,E中,从结点vi到vj最短路径的长度叫从vi到vj的距离,记为d(vi,vj)。若从vi到vj不存在路径,则d(vi,vj)=。注意,在有向图中,d(vi,vj)不一定等于d(vj,vi),但一般地满足以下性质:(1)d(vi,vj)0;(2)d(vi,vi)=0;(3)d(vi,vj)+d(vj,vk)d(vi,vk)。第8章 图论8.2.2连通图定义8.24设G=V,E是图,且vi、vjV。如果从vi到vj存在一条路径,则称vj从vi可达。vi自身认为从vi可达。定义8.25在无向图G中,如果任两结点可达,则称图G是连通的;如果G的子图G是连通的,没有包含G的更大的子图G是连通的,则称G是G的连通分图(简称分图)。第8章 图论图8.22一个无向图或者是一个连通图,如图8.22(a)所示,或者是由若干个连通分图组成,如图8.22(b)所示。第8章 图论定理8.23设G是任一(n,m)无向简单图,是其分图个数,则定义8.26在有向图中,如果在任两结点偶对中,至少从一个结点到另一个结点是可达的,则称图G是单向连通的;如果在任两结点偶对中,两结点都互相可达,则称图G是强连通的;如果它的底图是连通的,则称图G是弱连通的。第8章 图论强连通的也一定是单向连通和弱连通的,单向连通的一定是弱连通的,但其逆均不真。在下图中,(a)是强连通的,(b)是单向连通的,(c)是弱连通的。第8章 图论定义8.27在有向图G=V,E中,G是G的子图,若G是强连通的(单向连通的,弱连通的),没有包含G的更大子图G是强连通的(单向连通的,弱连通的),则称G是G的强分图(单向分图,弱分图)。在下图中,强分图集合是:1,2,3,e1,e2,e3,4,5,6,7,8,e7,e8第8章 图论单向分图集合是:1,2,3,4,5,e1,e2,e3,e4,e5,6,5,e6,7,8,e7,e8弱分图集合是:1,2,3,4,5,6,e1,e2,e3,e4,e5,e6,7,8,e7,e8第8章 图论8.2.3赋权图中的最短路径设G=V,E,W是个赋权图,W是从E到正实数集合的函数,边i,j的权记为W(i,j),称为边的长度。若i和j之间没有边,那么W(i,j)=。路径P的长度定义为路径中边的长度之和,记为W(P)。图G中从结点u到结点v的距离记为d(u,v),定义为 minW(P)|P为G中从u到v的路径当从u到v不可达时第8章 图论本小节主要讨论在一个赋权的简单连通无向图G=V,E,W中,求一结点a(称为源点)到其它结点x的最短路径的长度,通常称它为单源问题。下面介绍1959年迪克斯特拉(E.W.Dijkstra)提出的单源问题的算法,其要点如下:(1)把V分成两个子集S和T。初始时,S=a,T=V-S。(2)对T中每一元素t计算D(t),根据D(t)值找出T中距a最短的一结点x,写出a到x的最短路径的长度D(x)。(3)置S为Sx,置T为T-x,若T=,则停止,否则再重复2。第8章 图论算法中步骤(1)和(3)是清楚的,现在对2给以说明。D(t)表示从a到t的不包含T中其它结点的最短通路的长度,但D(t)不一定是从a到t的距离,因为从a到t可能有包含T中另外结点的更短通路。首先我们证明“若x是T中具有最小D值的结点,则D(x)是从a到x的距离”,用反证法。若另有一条含有T中另外结点的更短通路,不妨设这个通路中第一个属于T-x的结点是t1,于是D(t1)D(x),但这与题设矛盾。可见以上断言成立。第8章 图论其次说明计算D(t)的方法。初始时,D(t)=W(a,t),现在我们假设对T中的每一个t已计算了D值。设x是T中D值最小的一个结点,记S=Sx,T=T-x,令D(t)表示T中结点t的D值,则 D(t)=minD(t),D(x)+W(x,t)现分情况证明上式。第8章 图论(a)如果从a到t有一条最短路径,它不包含T中的其它结点,也不含x点,则D(t)=D(t)。(b)如果从a到t有一条最短路径,它从a到x不包含T中的结点,接着是边W(x,t),在此情况下,D(t)是D(x)+W(x,t)。第8章 图论例1考虑图8.27中的图,起初S=a,T=v1,v2,v3,v4,D(a)=0,D(v1)=2,D(v2)=+,D(v3)=+,D(v4)=10。因为D(v1)=2是T中最小的D值,所以选x=v1。置S为Sx=a,v1,置T为T-x=v2,v3,v4。然后计算:D(v2)=min(+,2+3)=5D(v3)=min(+,+)=+D(v4)=min(10,2+7)=9如此类推,直至T=终止。整个过程概括于表8.21中。第8章 图论图8.27第8章 图论表8.21第8章 图论8.2.4欧拉路径和欧拉回路哥尼斯堡(Konigsberg,现加里宁格勒)位于普雷格尔(Pregel)河畔,河中有两岛。城市的各部分由7座桥接通,如图8.28(a)所示。古时城中居民热衷于一个问题:游人从任一地点出发,怎样才能做到穿过每座桥一次且仅一次后又返回原出发地。1736年欧拉用图论方法解决了此问题,写了第一篇图论的论文,从而成为图论的创始人。第8章 图论不难看出,如果用结点代表陆地,用边代表桥,哥尼斯堡七桥问题就等价在于图8.28(b)中找到这样一条路径,它穿程每条边一次且仅一次。穿程于图G的每条边一次且仅一次的路径,称为欧拉路径。穿程于图G的每条边一次且仅一次的回路,称为欧拉回路,具有欧拉回路的图称为欧拉图。显然,具有欧拉路径的图除孤立结点外是连通的,而孤立结点不影响欧拉路径的讨论。因此,下边讨论欧拉路径有关问题时均假定图是连通的。第8章 图论图8.28第8章 图论定理8.24无向连通图G具有一条欧拉路径当且仅当G具有零个或两个奇数次数的顶点。证必要性。如果图具有欧拉路径,那么顺着这条路径画出的时候,每次碰到一个顶点,都需通过关联于这个顶点的两条边,并且这两条边在以前未画过。因此,除路径的两端点外,图中任何顶点的次数必是偶数。如果欧拉路径的两端点不同,那么它们就是仅有的两个奇数顶点,如果它们是重合的,那么所有顶点都有偶数次数,并且这条欧拉路径成为一条欧拉回路。因此必要性得证。第8章 图论充分性。我们从两个奇数次数的顶点之一开始(若无奇数次数的顶点,可从任一点开始),构造一条欧拉路径。以每条边最多画一次的方式通过图中的边。对于偶数次数的顶点,通过一条边进入这个顶点,总可通过一条未画过的边离开这个顶点。因此,这样的构造过程一定以到达另一个奇数次数顶点而告终(若无奇数次数的顶点,则以回到原出发点而告终)。如果图中所有边已用这种方法画过,显然,这就是所求的欧拉路径。如果图中不是所有边被画过,我们去掉已画过的边,得到由剩下边组成的一个子图,这个子图的顶点次数全是偶数。第8章 图论并且因为原来的图是连通的,因此,这个子图必与我们已画过的路径在一个点或多个点相接。由这些顶点中的一个开始,我们再通过边构造路径,因为顶点次数全是偶数,因此,这条路径一定最终回到起点。我们将这条路径已构造好的路径组合成一条路径。如果必要,这一论证重复下去,直到我们得到一条通过图中所有边的路径,即欧拉路径。因此充分性得证。第8章 图论例2(a)一笔画问题。就是判断一个图形能否一笔画成,实质上就是判断图形是否存在欧拉路径和欧拉回路的问题。例如,图8.29(a)和(b)均可一笔画成,因为符合存在欧拉路径和欧拉回路条件。第8章 图论(b)我们想知道是否可能将28块不同的多米诺骨牌排成一个圆形,使得在这个排列中,每两块相邻的多米诺骨牌其相邻的两个半面是相同的。我们构造一个具有7个顶点的图,这些顶点对应于空白、1、2、3、4、5和6,在每两个顶点之间都有一条边,我们把这条边当作一块多米诺骨牌,并且把这条边相关联的两个顶点当作它的两个半面。第8章 图论图8.29第8章 图论定理8.25一个有向连通图具有欧拉回路,当且仅当它的每个顶点的引入次数等于引出次数。一个有向连通图具有欧拉路径,当且仅当它的每个顶点的引入次数等于引出次数,可能有两个顶点是例外,其中一个顶点的引入次数比它的引出次数大1,另一个顶点的引入次数比它的引出崐次数小1。证明是类似的,不重复。第8章 图论例3布鲁英(DeBruijn)序列。现以旋转鼓设计为例说明布鲁英序列。旋转鼓的表面分成8块扇形,如图8.210所示。图中阴影区表示用导电材料制成,空白区用绝缘材料制成,终端a、b和c是接地或不是接地分别用二进制信号0或1表示。因此,鼓的位置可用二进制信号表示。试问应如何选取这8个扇形的材料使每转过一个扇形都得到一个不同的二进制信号,即每转一周,能得到000到111的8个数。第8章 图论图8.210第8章 图论图8.210第8章 图论8.2.5哈密尔顿路径与哈密尔顿回路在无向图G=V,E中,穿程于G的每个结点一次且仅一次的路径称为哈密尔顿路径。穿程于G的每个结点一次且仅一次的回路称为哈密尔顿回路。具有哈密尔顿回路的图称为哈密尔顿图。哈密尔顿,爱尔兰数学家,1859年他首先提出这一类问题。它的问题如下:如何沿12面体的棱线,通过每个角一次且仅一次?(称为环游全世界游戏。)第8章 图论图8.211第8章 图论定理8.26若G=V,E是哈密尔顿图,则对V的每个非空真子集S均成立:(G-S)S这里|S|表示S中的顶点数,(G-S)表示G删去顶点集S后得到的图的连通分图个数。证设C是图的一条哈密尔顿回路,则对于V的任一非空真子集S有 (C-S)|S|第8章 图论这里(C-S),是C删去子集S后得到的图的分图个数。但G是由C和一些不在C中的边构成的,C-S是G-S的生成子图,所以 (G-S)(C-S)|S|应用本定理可以判定某些图不是哈密尔顿图,例如,图8.212所示的图,删去其中3个黑点,即知此图不符合必要条件,因而不是哈密尔顿图。但一般要考察多个真子集,应用不方便,例4给出了一种较简便的否定一个图是哈密尔顿图的方法,但也不是通用的。第8章 图论图8.212第8章 图论例4证明图8.213(a)中的图没有哈密尔顿路径。证用A标记顶点a,所有与A邻接的顶点标记为B。继续不断地用A标记所有邻接于B的顶点,用B标记所有邻接于A的顶点,直到所有顶点标记完,得到如图8.213(b)所示的图,图中有3个顶点标A和5个顶点标B,标号A和B崐相差2个,因此不可能存在一条哈密尔顿路径。第8章 图论图8.213第8章 图论定理8.26中的条件不是充分的,图8.15中给出的彼得森图,它对任意SV都满足(G-S)|S|,但不是哈密尔顿图。定理8.27设G=V,E是具有n个顶点的简单无向图,若在G中每一对顶点的次数之和大于等于n,则在G中存在一条哈密尔顿回路。第8章 图论证用反证法。设G是符合题设条件,但不是哈密尔顿图,通过把不相邻的顶点加边,总可得到一个最大的非哈密尔顿图G。由于G是最大的非哈密尔顿图,所以给G的不相邻的顶点u和v加上边(u,v),这时有(v1,v2,vn,v1)这条哈密尔顿回路,不妨设v1=u,vn=v,因为回路必经过(u,v)。于是必存在两个相邻的顶点vi和vi-1使v1与vi,vi-1与vn相邻,如图8.214所示。若不然,设在G中v1与 相邻,而vn与 都不相邻,则deg(vn)n-k-1,这样deg(v1)+deg(vn)n-1n,与题设不符。第8章 图论图8.214第8章 图论 v1与vi相邻,vn与vi-1相邻,于是G存在一条哈密尔顿回路(v1,v2,vi-1,vn,vn-1,vi+1,vi,v1),但这与G是最大的非哈密尔顿图矛盾。证毕。容易看出定理8.27的条件是充分的但非必要。例如,设G是一个n边形,n5,任何两个顶点的度数之和是4,但在G中有一条哈密尔顿回路。第8章 图论推论8.27在简单无向图中,若每一顶点的度数,则该图是哈密尔顿图。在有向图中,也可类似地定义出哈密尔顿有向回路和哈密尔顿有向路径,但结论不全相似,限于篇幅不详述了,现在介绍一个与哈密尔顿回路有联系的问题巡回售货员问题。第8章 图论一个售货员希望去访问n个城市的每一个,开始和结束于v1城市。每两城市间都有一条直接通路,我们记vi城市到vj城市的距离为W(i,j),问题是去设计一个算法,它将找出售货员能采取的最短路径。这个问题用图论术语叙述就是:G=V,E,W是n个顶点的无向完全图,这里W是从E到正实数集的一个函数,对在V中任意三点vi,vj,vk满足W(i,j)+W(j,k)W(i,k)试求出赋权图上的最短哈密尔顿回路。第8章 图论至今未找出有效的方法,但已找到了若干近似算法,现介绍其一最邻近算法,它为巡回售货员问题得出一个近似解。(1)选任意点作为始点,找出一个与始点最近的点,形成一条边的初始路径。然后用第(2)步方法逐点扩充这条路径。(2)设x表示最新加到这条路径上的点,从不在路径上的所有点中,选一个与x最邻近的点,把连接x与此点的边加到这条路径中。重复这一步,直至G中所有顶点包含在路径中。第8章 图论图8.215第8章 图论(3)把始点和最后加入的顶点之间的边放入,这样就得出一个回路。例如,对于图8.215(a)所示的图,如果我们从a点开始,根据最邻近算法构造一个哈密尔顿回路,过程如图(b)到(e)所示,所得回路的总距离是44,其实图8.215(a)的最小哈密尔顿回路应如(f)所示,总距离是43。第8章 图论8.二部图二部图 从本节起将讨论一些特殊的图,首先讨论二部图。定义8.41若无向图G=V,E的顶点集合V可以划分成两个子集X和Y,使G中的每一条边e的一个端点在X中,另一个端点在Y中,则称G为二部图或偶图。二部图可记为G=X,E,Y,X和Y称为互补结点子集。由定义可知,二部图不会有自回路。第8章 图论定义8.42二部图G=X,E,Y中,若X的每一顶点都与Y的每一顶点邻接,则称G为完全二部图,记为Km,n,这里m=X,n=Y。图8.41给出K2,4和K3,3的图示。图8.41第8章 图论定理8.41无向图G=V,E为二部图的充分必要条件为G中所有回路的长度均为偶数。证必要性。设G是具有互补结点子集X和Y的二部图。C是G中任一回路C:(v0,v1,v2,vk,v0)不妨设v0X,则v0,v2,v4,X,v1,v3,v5,Y,k必为奇数,不然,不存在边(vk,v0)。C中共有k+1条边,故C是偶数长度的回路。第8章 图论充分性。设G是连通图,否则对G的每个连通分图进行证明。设G=V,E只含有偶数长度的回路,定义互补结点子集X和Y如下:任取一个顶点v0,v0V,取X=v从v0到v的距离是偶数Y=V-X第8章 图论定义8.43给定一个二部图G=X,E,Y,如果E的子集M中的边无公共端点,则称M为二部图G的一个匹配。含有最多边数的匹配称为G的最大匹配。例如,图8.42中,M=(x1,y5),(x3,y1),(x4,y3)是G的一个匹配。求最大匹配要应用交替链概念,其定义如下。第8章 图论定义8.44如果二部图G中的一条链由不属于匹配M的边和属于M的边交替组成,且链的两端点不是M中边的端点,那么称此链为G中关于匹配M的交替链。例如,图8.42中的(x2,y1,x3,y4)是交替链。最短的交替链是由一条边组成,该边的两端点不是M中边的端点。第8章 图论图8.42第8章 图论交替链可用标记法找出,标记法的过程如下:首先把X中所有不是M的边的端点用()加以标记,然后交替进行以下所述的过程和。.选一个X的新标记过的结点,比如说xi,用(xi)标记不通过在M中的边与xi邻接且未标记过的Y的所有结点。对所有X的新标记过的结点重复这一过程。.选一个Y的新标记过的结点,比如说yi,用(yi)标记通过M的边与yi邻接且未标记过的X的所有结点。对所有Y的新标记过结点重复这一过程。第8章 图论例如,在图8.42中,可用如下标记过程:(1)把x2标记(*)。(2)从x2出发,应用过程,把y1和y3标记(x2)。(3)从y1出发,应用过程,把x3标记(y1)。从y3出发,应用过程,把x4标记(y3)。(4)从x3出发,应用过程,把y4标记(x3),因y4不是M中边的端点,说明已找到了一条交替链,即(x2,y1,x3,y4)。第8章 图论在二部图G中,如果能找出一条关于匹配M的交替链,则把中属于M的边从M中删去,而把中不属于M的边添到M中,得到一新集合M,此M也是G的匹配。这是因为添入的边自身不相交,又不与M中不属于的边相交。例如在图8.42中作这样变换后,所得的M(用粗黑线标出)如图8.43所示。但M比M多一条边。因此,反复进行这样的过程,直至找不出关于M的交替链为止,就可崐求出G的最大匹配,即M。第8章 图论图8.43第8章 图论例1求出图8.44中的二部图的最大匹配。解步骤、操作内容及M情况(1)置M为M=(2)找出一条边的交替链(x2,y2)M=(x2,y2)(3)找出一条边的交替链(x3,y3)M=(x2,y2),(x3,y3)(4)找出一条边的交替链(x4,y4)M=(x2,y2),(x3,y3),(x4,y4)第8章 图论(5)用标记法找出交替链(x1,y3,x3,y2,x2,y1),进行变换得 M=(x1,y3),(x3,y2),(x2,y1),(x4,y4)。(6)再用标记法找交替链。但已找不到交替链。所以M=(x1,y3),(x3,y2),(x2,y1),(x4,y4)就是所求的最大匹配。图8.44