《路与回路》PPT课件.ppt

《《路与回路》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《路与回路》PPT课件.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学Discrete Mathematics 课程回顾课程回顾图的定义图的定义：结点集、边集、图的分类、点和：结点集、边集、图的分类、点和边的关联、点与点的相邻、边与边的邻接、边的关联、点与点的相邻、边与边的邻接、孤立结点、零图、平凡图、环、平行边孤立结点、零图、平凡图、环、平行边点的度数点的度数：度数、出度、入度、最大度、最：度数、出度、入度、最大度、最小度、小度、握手定理握手定理、相关定理、相关定理特殊的图特殊的图：多重图、：多重图、简单图简单图、完全图完全图、补图、补图、子图、生成子图、图的同构子图、生成子图、图的同构第七章第七章 图论第图论第2讲讲 72 路与回路路与回路7-2 路

2、与回路路与回路 在实际应用中，比如在市内乘出租车去在实际应用中，比如在市内乘出租车去参观一个博览会，一定要司机选一条最短参观一个博览会，一定要司机选一条最短的路。到博览会后，最好选一条这样的路的路。到博览会后，最好选一条这样的路径，使得每个展台都参观一次后，再回到径，使得每个展台都参观一次后，再回到原来存包处。这就是原来存包处。这就是路与回路路与回路的问题。的问题。学习本节要熟悉如下术语（学习本节要熟悉如下术语（22个）：个）：路、路、路的长度、路的长度、迹、迹、回路、回路、通路、通路、圈、圈、连通、连通、连通分支、连通分支、点割集、点割集、连通图、连通图、割点、割点、点连通度、点连通度、边割

3、集、边割集、边连通度、边连通度、割边、割边、可达、可达、单侧连通、单侧连通、强连通、强连通、强分图、强分图、弱连通、弱连通、弱分图、弱分图、单侧分图单侧分图掌握掌握5个定理，一个推论。个定理，一个推论。一、路一、路 定义定义7-2.1 给定给定图图G=,设设 v0,v1,vn V，e1,en E,其中其中ei是关联于结是关联于结点点vi-1,vi的边，交替序列的边，交替序列v0e1v1e2envn称为结点称为结点v0到到vn的的路路（拟路径拟路径Pseudo path）。v0和和vn分别称为路的分别称为路的起点起点和和终点终点，边的数目边的数目n称作路的称作路的长度长度。当当v0=vn时，这条

4、路称作时，这条路称作回路回路（闭路径闭路径closed walk）。若一条路中所有的边若一条路中所有的边e1,en均不相同均不相同,称称作作迹迹（路径路径walk）。若一条路中所有的结点若一条路中所有的结点v0,v1,vn均不相均不相同同,称作称作通路通路（Path）。闭的通路闭的通路,即除即除v0=vn之外，其余结点均不相之外，其余结点均不相同的路，称作同的路，称作圈圈（回路回路circuit）。注注：通路都是迹，迹不都是通路。（没有重复结：通路都是迹，迹不都是通路。（没有重复结点亦没有重复边）点亦没有重复边）在简单图中一条路在简单图中一条路v0e1v1e2envn，由它的结点序列由它的结点

5、序列v0v1vn确定，所以确定，所以简单简单图的路，可由其结点序列表示图的路，可由其结点序列表示。在有向图在有向图中，结点数大于中，结点数大于1的一条路亦可由边序列的一条路亦可由边序列e1e2en表示。表示。路长度路长度：边的数目：边的数目n。结点数结点数=边数边数+1回路回路(closed walk):当当v0=vn时时 v0e1 v1e2 vi-1eivienvn 结点数结点数=边数边数图图7-2.1例例路：路：v1e2v3e3v2e3v3e4v2e6v5e7v3迹：迹：v5e8v4e5v2e6v5e7v3e4v2通路：通路：v4e8v5e6v2e1v1e2v3圈：圈：v2e1v1e2v3

6、e7v5e6v2v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e1e2e3e4e5e6e7e8v2v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e1e2e3e4e5e6e7e8从从v1到到v3的一条的一条路，长路，长度为度为6从从v5到到v2的一条的一条迹，长迹，长度为度为5从从v4到到v3的一条的一条通路，通路，长度为长度为4从从v2到到v2的一条的一条圈，长圈，长度为度为4定理定理7-2.1 在一个具有在一个具有n个结点的图中，如果从个结点的图中，如果从结点结点vj到结点到结点vk存在一条路，则从结点存在一条路，则从结点vj到结点到结点v

7、k必存在一条不多于必存在一条不多于n-1条边的路。条边的路。证明思路：多于证明思路：多于n-1条边的路中必有重复出现的条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过后，剩余的边数不会超过n-1条边。条边。定理定理7-2.1示例示例:VsVkVjVsVsVkVjVjVk 定理定理7-2.1的证明的证明 如果从结点如果从结点vj到到vk存在一条路，该路上的结存在一条路，该路上的结点序列是点序列是vjvivk，如果在这条路中有，如果在这条路中有L条边，条边，则序列中必有则序列中必有 L+1个结点，若个结点，若Ln-1，则

8、必有结，则必有结点点vs，它在序列中不止出现一次，即必有结点序，它在序列中不止出现一次，即必有结点序列列vjvsvsvk，在路中去掉从，在路中去掉从vs到到vs的这些的这些边，仍是边，仍是vj到到vk的一条路，但此路比原来的路边的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从数要少，如此重复进行下去，必可得到一条从vj到到vk的不多于的不多于n-1条边的路。条边的路。定理定理7-2.1的推论的推论 在一个具有在一个具有n个结点的图中，个结点的图中，如果从结点如果从结点vj到结点到结点vk存在一条路，则从结点存在一条路，则从结点vj到结点到结点vk必存在一条边数小于必存在一条

9、边数小于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，规定结点到

10、自身是连，规定结点到自身是连通的。通的。（2）由定义不难看出，无向图中结点之间的连）由定义不难看出，无向图中结点之间的连通关系通关系 R=|u,vV且且u与与v连通连通是自反是自反的，对称的，传递的，因而的，对称的，传递的，因而R是是V上的上的等价关系等价关系。结点之间的连通性是结点集结点之间的连通性是结点集V上的等价关系，对上的等价关系，对应该等价关系，必可将作出一个划分，把应该等价关系，必可将作出一个划分，把V分成非空分成非空子集子集V1,V2,Vm,使得两个结点使得两个结点vj和和vk是连通的，是连通的，当且仅当它们属于同一个当且仅当它们属于同一个Vi。把子图把子图G(V1),G(V2)

11、,G(Vm)称为图称为图G的的连通分支连通分支（connected components）,图图G的连通分支数记为的连通分支数记为W(G)。例例例例:W(G)=3G见见281页图页图7-2.2练习1：下图中连通分支数目？练习2：下图中连通分支数目？2645132、连通图、连通图 定义定义7-2.3 若图若图G只有一个连通分支，则只有一个连通分支，则称称G是连通图。否则称是连通图。否则称G是非连通图或分离图。是非连通图或分离图。显然在连通图中，任意两个结点之间必显然在连通图中，任意两个结点之间必是连通的。是连通的。见见281页图页图7-2.2图图7-2.2(a)是连通图是连通图 对于连通图，常常

12、由于删除了图中的点或边，而影响了对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。图的连通性。删除结点删除结点删除结点删除结点：所谓在图中删除：所谓在图中删除：所谓在图中删除：所谓在图中删除结点结点v，即是把即是把v以及与以及与v关联关联的边都删除。的边都删除。删除边删除边删除边删除边：所谓在图中删除某条边所谓在图中删除某条边所谓在图中删除某条边所谓在图中删除某条边，即是把该边删除。，即是把该边删除。见见282页图页图7-2.3v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e3、割点、割点定义定义7-2.4 设无向设无向设无向设无向图图G=是

13、是连通图连通图,若有结点集若有结点集V1 V,使使图图G中中删除了删除了删除了删除了V1的所有结点后的所有结点后的所有结点后的所有结点后,所得到的子图是不连通图所得到的子图是不连通图所得到的子图是不连通图所得到的子图是不连通图,而而而而删除了删除了删除了删除了V1的任何真子集后的任何真子集后的任何真子集后的任何真子集后,所得到的子图仍是所得到的子图仍是所得到的子图仍是所得到的子图仍是连通图连通图,则称则称V1是是G的一个的一个点割集点割集(cut-set of nodes)。若某一个点构成一个若某一个点构成一个点割集，则称该点为点割集，则称该点为割点割点。如下图中的点如下图中的点s就是割点。就

14、是割点。sabcdabcdba上图中上图中: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(

15、G)=0v5v1v2v3v4v5v1v3v4点割集点割集V1=v2 4.定理定理7-2.3 一个连通一个连通一个连通一个连通无向图无向图G的结点的结点v是割点的充分是割点的充分必要条件是存在两个结点必要条件是存在两个结点u和和w,使得结点使得结点u和和w的每一条的每一条路都通过路都通过v。证明思路：证明思路：1)先证先证:v是割点是割点存在结点存在结点u和和w的每条路都通过的每条路都通过v 若若v是连通图是连通图G=割点，设删去割点，设删去v得到的子图得到的子图G,则则G至少至少包含两个连通分支包含两个连通分支G1=和和G2=。任取任取u V1，w V2，因为因为G是连通的，故在是连通的，故在

16、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=是是连通图

17、连通图,若有边若有边集集E1 E，使图，使图 G中删除了中删除了E1的所有边后，所得到的的所有边后，所得到的子图是不连通图，而删除了子图是不连通图，而删除了E1的任何真子集后，所得的任何真子集后，所得到的子图仍是连通图，则称到的子图仍是连通图，则称E1是是G的一个的一个边割集边割集(cut-set of edges)。若某一条边就构成一个边割集，若某一条边就构成一个边割集，则称该边为则称该边为割边割边或或桥桥。割边割边e使图使图G满足满足W(G-e)W(G)。边边边边连通度连通度(edge-connectivity)(G)定义定义：非：非平凡图的边连通度为平凡图的边连通度为 (G)=min|E

18、1|E1是是G的边割集的边割集 边连通度边连通度 (G)是为了产生一个不连通图需要是为了产生一个不连通图需要删去的边的最少数目。删去的边的最少数目。(1)若若G是平凡图则是平凡图则E1=，(G)=0(2)若若G存在割边，则存在割边，则(G)=1，(3)规定非连通图的边连通度为规定非连通图的边连通度为(G)=05、定理定理7-2.2 对于任何一个对于任何一个图图G,有有k(G)(G)(G)。在在7-1节定义了图的最小度：节定义了图的最小度：(G)=min(deg(v)，v V)下面的定理给出了点连通度下面的定理给出了点连通度k(G)、边连通度、边连通度(G)和图的最小度和图的最小度(G)之间的关

19、系。之间的关系。282页图页图7-2.3k(G)=1,(G)=1,(G)=1例例:sabcdak(G)=1,(G)=2,(G)=2 证明证明 若若G不连通，则不连通，则k(G)=(G)=0，故上式成立。，故上式成立。若若G连通，连通，可分两步证明上式也成立：可分两步证明上式也成立：1)先证明先证明(G)(G)：如果如果G是平凡图，则是平凡图，则(G)=0(G)，若若G是非平凡图，则因每一结点的所有关联边必含一是非平凡图，则因每一结点的所有关联边必含一个边割集，个边割集，(因因(G)=mindeg(v)|v V，设，设u V使的使的deg(u)=(G)，与，与u相关联的相关联的 条边必包含一个边

20、割集，至条边必包含一个边割集，至少这少这 条边删除使图不连通。条边删除使图不连通。)故故(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的端点，把

21、这些端点删去则必至少删去的端点，把这些端点删去则必至少删去(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是可达的。是可达的。有向图的可达性：有向图的可达性：对于任何一个有向对于

22、任何一个有向图图G=,从结点从结点u和到结点和到结点v有一条路有一条路,称为称为从从u可达可达v。可达性可达性(accesible),是结点集上的二元是结点集上的二元关系，它是自反的和传递的，但是一般来说关系，它是自反的和传递的，但是一般来说不是对称的。故可达性不是等价关系。不是对称的。故可达性不是等价关系。可达性示例可达性示例:baedcced cedabedc 如果如果u可达可达v，它们之间可能不止一条路，它们之间可能不止一条路，在所有这些路中，最短路的长度称为在所有这些路中，最短路的长度称为u和和v之间之间的的距离距离（或短程线），记作（或短程线），记作d，它满足下，它满足下列性质：列性

23、质：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中的任何中

24、的任何一对结点两者之间是相互可达的，则称这个图一对结点两者之间是相互可达的，则称这个图是是强连通强连通的。如果在图的。如果在图G中略去边的方向，将中略去边的方向，将它看成无向图后，图是连通的，则称该图为它看成无向图后，图是连通的，则称该图为弱弱连通连通的。的。显然，强连通图显然，强连通图单侧连通图单侧连通图弱连通图。弱连通图。而逆推均不成立。而逆推均不成立。v2v3v4v1(a)强连通强连通v2v3v4v1(b)单侧连通单侧连通v2v3v4v1(c)弱连通弱连通 证明证明 充分性：如充分性：如G中有一条有向回路，经过每一点至少一次，中有一条有向回路，经过每一点至少一次，则则G中任意两点中任意两

25、点u，vV，u可以沿着该有向回路的一部分可以沿着该有向回路的一部分的而到达的而到达v，则，则G是强连通图。是强连通图。3、定理定理7-2.4(强连通图判别定理强连通图判别定理)一个有向图是强一个有向图是强连通的充要条件是连通的充要条件是G有一个回路，它至少包含每个有一个回路，它至少包含每个结点一次。结点一次。必要性：任取必要性：任取u，vV，图，图G是强连通图，则是强连通图，则uv有有有有向路，向路，vu也有有向路，则也有有向路，则uvu构成了一个有向回路，构成了一个有向回路，如果该有向回路没有包含如果该有向回路没有包含w，而，而uw，wu均有有向路，均有有向路，则则uvuwu又是一个有向回路

26、，一直下去可以将图中又是一个有向回路，一直下去可以将图中所有的点均包含进去。所有的点均包含进去。单向连通图判别定理单向连通图判别定理 有向图有向图G单向连通单向连通 G中有路通过中有路通过每个结点至少一次每个结点至少一次.4、分图、分图定义定义7-2.7 在简单有向图中，具有强连通性质的在简单有向图中，具有强连通性质的最大最大子图子图，称为，称为强分图强分图；具有单侧连通性质的最大子图，；具有单侧连通性质的最大子图，称为称为单侧分图单侧分图；具有弱连通性质的最大子图，称为；具有弱连通性质的最大子图，称为弱分图弱分图。v4v2v3v1(b)v4v2v3v1(a)v5例如例如,给定有向图给定有向图

27、G,如图所示如图所示:求它的强分图、单侧求它的强分图、单侧分图和弱分图分图和弱分图.解解:强分图强分图:由由a,g,hbc def导出的子图导出的子图.单侧分图单侧分图:由由a,g,h,b,f,d,eb,c,f,d,e导出的子导出的子图图.弱分图弱分图:G本身是弱分图本身是弱分图.定理定理7-2.5 在有向图在有向图G=中，它的每一个结中，它的每一个结点位于且只位于一个强分图中。点位于且只位于一个强分图中。证明思路：证明思路：1)1)先证先证:每一个结点每一个结点必必位于一个强分图中。位于一个强分图中。2)2)再证再证:每一个结点每一个结点只只位于一个强分图中。位于一个强分图中。练习练习286

28、、287页习题页习题说明说明：在等价关系的关系图上，一个等价类中：在等价关系的关系图上，一个等价类中含有的所有元素（结点）恰好同在强分图中。含有的所有元素（结点）恰好同在强分图中。等价类的数目等于它的关系图强分图的数目。等价类的数目等于它的关系图强分图的数目。练习练习7-2（1）在无向图在无向图G中，从结点中，从结点u到结点到结点v有一条长度为偶数有一条长度为偶数的通路，从结点的通路，从结点u到结点到结点v又有一条长度为奇数的通路，又有一条长度为奇数的通路，则在则在G中必有一条长度为奇数的回路。中必有一条长度为奇数的回路。证明证明 设从结点设从结点u到结点到结点v的长度为偶数的通路为的长度为偶

29、数的通路为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中两个奇数度的结

30、点为中两个奇数度的结点为u和和v。从从u开始构造一条迹，即从开始构造一条迹，即从u出发经关联于结点出发经关联于结点u的边的边e1到达结点到达结点u1，若，若deg(u1)为偶数，则必可由为偶数，则必可由u1再经关再经关联于结点联于结点u1的边的边e2到达结点到达结点u2，如此继续下去，每边如此继续下去，每边只取一次，直到另一个奇数度结点停止，由于图只取一次，直到另一个奇数度结点停止，由于图G中只中只有两个奇数度结点，故该结点或是有两个奇数度结点，故该结点或是u或是或是v。如果是如果是v，那么从那么从u到到v的一条路就构造好了。如果仍是结点的一条路就构造好了。如果仍是结点u，此此路是闭迹。路是闭

31、迹。闭迹上每个结点都是关联偶数条边，而闭迹上每个结点都是关联偶数条边，而deg(u)为为奇数，所以至少还有一条关联于结点奇数，所以至少还有一条关联于结点u的边不在此的边不在此闭迹上。继续从闭迹上。继续从u出发，沿着该边到达另一个结点出发，沿着该边到达另一个结点u1，依次下去直到另一个奇数度结点停下。这样，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点经过有限次后必可到达结点v，这就是一条从，这就是一条从u到到v的路。的路。练习练习7-2（4）当且仅当当且仅当G的一条边的一条边e不包含在不包含在G的回路中时，的回路中时，e才才是是G的割边。的割边。证明证明 必要性。设必要性。设e

32、是连通图是连通图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是割边。是割边。作业作业287页（页（3）(5)（8）（10）选做：选做：（7）