《路与回路》PPT课件

离散数学Discrete Mathematics,课程回顾,图的定义：结点集、边集、图的分类、点和边的关联、点与点的相邻、边与边的邻接、孤立结点、零图、平凡图、环、平行边,点的度数：度数、出度、入度、最大度、最小度、握手定理、相关定理,特殊的图：多重图、简单图、完全图、补图、子图、生成子图、图的同构,第七章 图论第2讲 72 路与回路,7-2 路与回路,在实际应用中，比如在市内乘出租车去参观一个博览会，一定要司机选一条最短的路。到博览会后，最好选一条这样的路径，使得每个展台都参观一次后，再回到原来存包处。这就是路与回路的问题。,学习本节要熟悉如下术语（22个）：,路、,路的长度、,迹、,回路、,通路、,圈、,连通、,连通分支、,点割集、,连通图、,割点、,点连通度、,边割集、,边连通度、,割边、,可达、,单侧连通、,强连通、,强分图、,弱连通、,弱分图、,单侧分图,掌握5个定理，一个推论。,一、路,定义7-2.1 给定图G=,设 v0,v1,vnV， e1,enE, 其中ei是关联于结点vi-1,vi的边，交替序列v0e1v1e2envn称为结点v0到vn的路（拟路径Pseudo path） 。 v0和vn分别称为路的起点和终点， 边的数目n称作路的长度。 当v0=vn时，这条路称作回路（闭路径closed walk） 。,若一条路中所有的边e1, , en均不相同,称作迹（路径walk） 。 若一条路中所有的结点v0, v1, vn均不相同,称作通路（Path） 。 闭的通路,即除v0=vn之外，其余结点均不相同的路，称作圈（回路circuit） 。 注：通路都是迹，迹不都是通路。（没有重复结点亦没有重复边）,在简单图中一条路v0e1v1e2envn，由它的结点序列v0v1vn确定，所以简单图的路，可由其结点序列表示。在有向图中，结点数大于1的一条路亦可由边序列e1e2en表示。 路长度 ：边的数目n。 结点数=边数+1,回路(closed walk) : 当v0=vn时 v0e1 v1e2 vi-1eivienvn 结点数=边数,图7-2.1例 路：v1e2v3e3v2e3v3e4v2e6v5e7v3 迹：v5e8v4e5v2e6v5e7v3e4v2 通路：v4e8v5e6v2e1v1e2v3 圈：v2e1v1e2v3e7v5e6v2,v1,v2,v3,v4,v5,e1,e2,e3,e4,e5,e6,e7,e8,v2,从v1到v3的一条路，长度为6,从v5到v2的一条迹，长度为5,从v4到v3的一条通路，长度为4,从v2到v2的一条圈，长度为4,定理7-2.1 在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。,证明思路：多于n-1条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过n-1条边。,定理7-2.1示例:, 定理7-2.1的证明 如果从结点vj到vk存在一条路，该路上的结点序列是vjvivk，如果在这条路中有L条边，则序列中必有 L+1个结点，若Ln-1，则必有结点vs，它在序列中不止出现一次，即必有结点序列vjvsvsvk，在路中去掉从vs到vs的这些边，仍是vj到vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从vj到vk的不多于n-1条边的路。 ,定理7-2.1的推论 在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条边数小于n的通路。,如在图7-2.1中有5个结点。 v1到v3的一条路为：v1e2v3e3v2e3v3e4v2e6v5e7v3 此路中有6条边，去掉e3有路 v1e2v3e4v2e6v5e7v3 有4条边。 v1到v3最短的路为v1e2v3,二、无向图的连通性 1、连通,定义7-2.2 在无向图G中，如果从结点u和结点v之间若存在一条路，则称结点u和结点v是连通的（connected） 。,注：（1）对于所有vV，规定结点到自身是连通的。 （2）由定义不难看出，无向图中结点之间的连通关系 R=|u,vV且u与v连通是自反的，对称的，传递的，因而R是V上的等价关系。,结点之间的连通性是结点集V上的等价关系，对应该等价关系，必可将作出一个划分，把V分成非空子集V1, V2, , Vm,使得两个结点vj和vk是连通的，当且仅当它们属于同一个Vi 。把子图G(V1) , G(V2) , , G(Vm)称为图G的连通分支（connected components）,图G的连通分支数记为W(G) 。,例: W(G)=3,见281页图7-2.2,练习1：下图中连通分支数目？,练习2：下图中连通分支数目？,2、连通图 定义7-2.3 若图G只有一个连通分支，则称G是连通图。否则称G是非连通图或分离图。 显然在连通图中，任意两个结点之间必是连通的。,见281页图7-2.2 图7-2.2(a)是连通图,对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。 删除结点：所谓在图中删除结点v，即是把v以及与v关联的边都删除。 删除边：所谓在图中删除某条边，即是把该边删除。,见282页图7-2.3,3、割点 定义7-2.4 设无向图G =是连通图,若有结点集V1V,使图G中删除了V1的所有结点后,所得到的子图是不连通图,而删除了V1的任何真子集后,所得到的子图仍是连通图,则称V1是G的一个点割集(cut-set of nodes) 。若某一个点构成一个点割集，则称该点为割点。,如下图中的点s就是割点。,上图中:b,f, b,g, f,k,k,g以及a,d,i,l是点割集. 不存在割点.,点连通度：是为了产生一个不连通图需要删去的点的最少数目，也称为连通度，记为k(G) 。 即k(G)=min|V1| | V1是G的点割集 称为图G的点连通度(node-connectivity) 。 (1)若G是平凡图则V1=，k(G)=0 (2)k(Kn)=n-1 (3)若图存在割点，则k(G)=1 (4)规定非连通图的连通度k(G)=0,4.定理7-2.3 一个连通无向图G的结点v是割点的充分必要条件是存在两个结点u和w,使得结点u和w的每一条路都通过v 。, 证明思路： 1) 先证:v是割点存在结点u和w的每条路都通过v 若v是连通图G=割点，设删去v得到的子图G , 则G至少包含两个连通分支G1=和G2= 。任取uV1，wV2，因为G是连通的，故在G中必有一条连结u和w的路C，但u和w在G中属于两个不同的连通分支，故u和w必不连通，因此C必须通过v，故u和w之间的任意一条路都通过v 。 2)再证:存在结点u和w的每条路都通过v v是割点 若连通图G中的某两个结点的每一条路都通过v，则删去v得到子图G ，在G中这两个结点必然不连通，故v是图G的割点。 ,5、割边 定义7-2.5 设无向图G =是连通图,若有边集E1E，使图 G中删除了E1的所有边后，所得到的子图是不连通图，而删除了E1的任何真子集后，所得到的子图仍是连通图，则称E1是G的一个边割集(cut-set of edges) 。若某一条边就构成一个边割集，则称该边为割边或桥。 割边e使图G满足W(G-e)W(G) 。,边连通度(edge-connectivity) (G)定义：非平凡图的边连通度为 (G)=min |E1| | E1是G的边割集 边连通度 (G)是为了产生一个不连通图需要删去的边的最少数目。 (1)若G是平凡图则E1=，(G)=0 (2)若G存在割边，则(G)=1， (3)规定非连通图的边连通度为(G)=0,5、定理7-2.2 对于任何一个图G,有k(G)(G)(G) 。,在7-1节定义了图的最小度： (G)=min(deg(v)，vV) 下面的定理给出了点连通度k(G) 、边连通度(G)和图的最小度(G)之间的关系。,282页图7-2.3,k(G)=1,(G)=1,(G)=1,例:,a,k(G)=1,(G)=2,(G)=2, 证明 若G不连通，则k(G)=(G)=0，故上式成立。 若G连通，可分两步证明上式也成立： 1)先证明(G)(G)： 如果G是平凡图，则(G)=0(G)， 若G是非平凡图，则因每一结点的所有关联边必含一个边割集，(因(G)=mindeg(v)|vV，设uV使的deg(u)=(G)，与u相关联的条边必包含一个边割集，至少这条边删除使图不连通。)故(G)(G)。,定理7-2.2 对于任何一个图G,有 k(G)(G)(G) 。,2)再证k(G)(G)： (a)设(G)=1，即G有一割边，显然这时k(G)=l，上式成立。 (b)设(G)2，则必可删去某(G)条边，使G不连通，而删去其中(G)-1条边，它仍是连通的，且有一条桥e=(u，v)。对(G)-1条边中的每一条边都选取一个不同于u，v的端点，把这些端点删去则必至少删去(G)-1条边。若这样产生的图是不连通的，则k(G)(G)-1(G)，若这样产生的图是连通的，则e仍是桥，此时再删去u或v就必产生一个不连通图，故k(G)(G)。由1)和2)得k(G)(G)(G)。 ,三、有向图的连通性 1、可达： 在无向图G中，从结点u到v若存在一条路，则称结点u到结点v是可达的。,有向图的可达性：对于任何一个有向图G=, 从结点u和到结点v有一条路,称为从u可达v。 可达性(accesible),是结点集上的二元关系，它是自反的和传递的，但是一般来说不是对称的。故可达性不是等价关系。,可达性示例:,baedc ced ced,如果u可达v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为u和v之间的距离（或短程线），记作d，它满足下列性质： d0 d =0 d + d d,有关距离的概念对无向图也适用，把 D=max d, u,vV 称作图的直径。,如果从u到v是不可达的，则通常写成 d = 注意：当u可达v，且v也可达u时， d 不一定等于d,2、简单有向图分类（据连通性） 定义7-2.6 在简单有向图G中，任何一对结点间，至少有一个结点到另一个结点是可达的，则称这个图是单侧连通的 。如果对于图G中的任何一对结点两者之间是相互可达的，则称这个图是强连通的。如果在图G中略去边的方向，将它看成无向图后，图是连通的，则称该图为弱连通的。,显然，强连通图单侧连通图弱连通图。而逆推均不成立。, 证明 充分性：如G中有一条有向回路，经过每一点至少一次，则G中任意两点u，vV，u可以沿着该有向回路的一部分的而到达v，则G是强连通图。,3、定理7-2.4(强连通图判别定理) 一个有向图是强连通的充要条件是G有一个回路，它至少包含每个结点一次。,必要性：任取u，vV，图G是强连通图，则uv有有向路，vu也有有向路，则uvu构成了一个有向回路，如果该有向回路没有包含w，而uw，wu均有有向路，则uvuwu又是一个有向回路，一直下去可以将图中所有的点均包含进去。 ,单向连通图判别定理,有向图G单向连通 G中有路通过每个结点至少一次.,4、分图 定义7-2.7 在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图。,例如,给定有向图G,如图所示:求它的强分图、单侧分图和弱分图. 解: 强分图:由a,g,hbc def导出的子图. 单侧分图:由a,g,h,b,f,d,eb,c,f,d,e导出的子图. 弱分图:G本身是弱分图.,定理7-2.5 在有向图G=中，它的每一个结点位于且只位于一个强分图中。,证明思路： 1)先证:每一个结点必位于一个强分图中。 2)再证:每一个结点只位于一个强分图中。 ,练习286、287页习题,说明：在等价关系的关系图上，一个等价类中含有的所有元素（结点）恰好同在强分图中。等价类的数目等于它的关系图强分图的数目。,练习7-2（1） 在无向图G中，从结点u到结点v有一条长度为偶数的通路，从结点u到结点v又有一条长度为奇数的通路，则在G中必有一条长度为奇数的回路。,证明 设从结点u到结点v的长度为偶数的通路为u e1 u 1e2 u2 e2m v ，从结点u到结点v的长度为奇数的通路为u e1 v 1 e2 v 2 e2n-1 v ，则 u e1 u 1e2 u2 e2m v e2n-1 v 2 e2 v 1 e1 u 为一条回路，其长度为 2m+2n-1=2(m+n)-1为奇数，故在G中必有一条长度为奇数的回路。 ,练习7-2（2） 若无向图G中恰有两个奇数度的结点，则这两个结点之间必有一条路。,证明 设无向图G中两个奇数度的结点为u和v。 从u开始构造一条迹，即从u出发经关联于结点u的边e1到达结点u1，若deg(u1)为偶数，则必可由u1再经关联于结点u1的边e2到达结点u2，如此继续下去，每边只取一次，直到另一个奇数度结点停止，由于图G中只有两个奇数度结点，故该结点或是u或是v。如果是v，那么从u到v的一条路就构造好了。如果仍是结点u，此路是闭迹。,闭迹上每个结点都是关联偶数条边，而deg(u)为奇数，所以至少还有一条关联于结点u的边不在此闭迹上。继续从u出发，沿着该边到达另一个结点u1，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。 ,练习7-2（4） 当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。, 证明 必要性。设e是连通图G的割边，e关联的两个结点是u和v。如果e包含在G的一个回路中，那么除边e=(u,v)外还有另一条分别以u和v为端点的路，所以删去边e后，G仍为连通图，这与e是割边相矛盾。,充分性。 如果边e不包含在G的任一条回路中，那么连接结点u和v的边只有e，而不会有其它连接u和v的任何路。因为如果连接u和v还有不同于边e的路，此路与边e就组成一条包含边e的回路，从而导致矛盾。所以删去边e后，u和v就不连通，故边e是割边。 ,补充练习 若G是 一个简单图，且(G)|V|-2，则k(G)=(G), 证明 因为G是简单图，所以每个结点的度数最多为|V|-1(即(G)|V|-1)，现有(G)|V|-2，所以只要讨论以下两种情况即可： （1）若(G) =|V|-1，则G=K|V|，因此 k(G)=|V|-1= (G),（2）若(G) =|V|-2，则必有两个结点不相邻接，设v1,v2V且v1与v2不相邻接。于是，对于任意的v3V，都有v1v3，v2v3E。因此，对于V中任意的|V|-3个结点的集合V1，G-V1一定是连通的， 故必有k(G)|V|-2=(G) 。而由定理7-2.2可知 (G) k(G) 所以有(G)=k(G)。 ,作业 287页（3）(5) （8） （10） 选做： （7）,本节内容到此结束,谢谢大家！,