7-2路与回路.ppt

《7-2路与回路.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、7-2路与回路在现实世界中，常常要考虑这样的问题：如何从一个图中的给定结点出发，沿着一些边连续移动而达到另一指定结点，这种依次由点和边组成的序列，就形成了路的概念。学习本节要熟悉如下术语(22个)：路、路的长度、迹、回路、通路、圈、连通、连通分支、点割集、连通图、割点、点连通度、边割集、边连通度、割边、可达、单侧连通、强连通、强分图、弱连通、弱分图、单侧分图掌握5个定理，一个推论。一、路定义7-2.1给定图G=,设v0,v1,…,vnV，e1,…,enE,其中ei是关联于结点vi-1,vi的边，交替序列v0e1v1e2…envn称为

2、结点v0到vn的路（拟路径Pseudopath）。v0和vn分别称为路的起点和终点，边的数目n称作路的长度。当v0=vn时，这条路称作回路（闭路径closedwalk）。若一条路中所有的边e1,…,en均不相同,称作迹（路径walk）。若一条路中所有的结点v0,v1,…,vn均不相同,称作通路（Path）。闭的通路,即除v0=vn之外，其余结点均不相同的路，称作圈（回路circuit）。见图7-2.1中路的例子。例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3迹：v5e8v4e5v2e6v5e7v3e4v2通路：v4e8v5e6v2e

3、1v1e2v3圈：v2e1v1e2v3e7v5e6v2在简单图中一条路v0e1v1e2…envn，由它的结点序列v0，v1，…，vn确定，所以简单图的路，可由其结点序列表示。在有向图中，结点数大于一的—条路亦可由边序列e1e2…en表示。定理7-2.1在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。证明思路：多于n-1条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过n-1条边。定理7-2.1的推论在一个具有n个结点的图中，如果从结点vj到

4、结点vk存在一条路，则从结点vj到结点vk必存在一条边数小于n的通路。定理7-2.1的证明如果从结点vj到vk存在一条路，该路上的结点序列是vj…vi…vk，如果在这条中有l条边，则序列中必有l+1个结点，若l>n-1，则必有结点vs，它在序列中不止出现一次，即必有结点序列vj…vs…vs…vk，在路中去掉从vs到vs的这些边，仍是vj到vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从vj到vk的不多于n-1条边的路。如在图7-2.1中有5个结点。v1到v3的一条路为：v1e2v3e3v2e3v3e4v2e6v5e7v3此

5、路中有6条边，去掉e3有路v1e2v3e4v2e6v5e7v3有4条边。v1到v3最短的路为v1e2v3二、无向图的连通性：1、连通见281页图7-2.2定义7-2.2在无向图G中，如果从结点u和结点v之间若存在一条路，则称结点u和结点v是连通的（connected）。结点之间的连通性是结点集V上的等价关系，对应该等价关系，必可将作出一个划分，把V分成非空子集V1,V2,…,Vm,使得两个结点vj和vk是连通的，当且仅当它们属于同一个Vi。把子图G(V1),G(V2),…,G(Vm)称为图G的连通分支（connectedcomponents）,图

6、G的连通分支数记为W(G)。2、连通图定义7-2.3：若图G只有一个连通分支，则称G是连通图。显然在连通图中，任意两个结点之间必是连通的。对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。删除结点：所谓在图中删除结点v，即是把v以及与v关联的边都删除。删除边：所谓在图中删除某条边，即是把该边删除。v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e3、割点定义7-2.4设无向图G=是连通图,若有结点集V1V,使图G中删除了V1的所有结点后,所得到的子图是不连通图,而删除了V1的任何真子集

7、后,所得到的子图仍是连通图,则称V1是G的一个点割集(cut-setofnodes)。若某一个点构成一个点割集，则称该点为割点。如282页图7-2.4(a)中的点s就是割点。sabcdabcdba点连通度：是为了产生一个不连通图需要删去的点的最少数目，也称为连通度，记为k(G)。即k(G)=min{

8、V1

9、

10、是G的点割集}称为图G的点连通度(node-connectivity)。(1)若G是平凡图则V1=，k(G)=0(2)k(Kn)=n-1(3)若图存在割点，则k(G)=1(4)规定非连通图的连通度k(G)=0v5v1v2v3v4v5v1v3

11、v4点割集V1={v2}4、割边定义7-2.5设无向图G=是连通图,若有边集E1E，使图G中删除了E1的所有边后，所得到的子