7.2 通路、迹、连通.ppt

《7.2 通路、迹、连通.ppt》由会员分享，可在线阅读，更多相关《7.2 通路、迹、连通.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、通路给定图G.设G中顶点和边的交替序列为v0e1v1e2elvl,若满足如下条件:vi-1和vi是ei的端点(在G是有向图时,要求vi-1是ei的始点,vi是ei的终点),i1,2,l,则称为顶点v0到vl的通路.v0和vl分别称为此通路的起点和终点,中边的数目l称为的长度.当v0vl时,此通路称为回路.迹若中的所有边e1,e2,el互不相同,则称为简单通路或一条迹.若回路中的所有边互不相同,称此回路为简单回路或一条闭迹.初级通路若通路的所有顶点v0,v1,vl互不相同(从而所有边互不相同),则称此通路为初级通路或一条路径.若回路中,除v0vl外,其余顶点各不相同,所有边也各不相同,则称此回路

2、为初级回路或圈.复杂通路有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路.由定义可知,初级通路(回路)是简单通路(回路),但反之不真.定理在一个n阶图中,若从顶点vi到vj(vivj)存在通路,则从vi到vj存在长度小于等于n1的通路.推论在一个n阶图中,若从顶点vi到vj(vivj)存在通路,则从vi到vj存在长度小于等于n1的初级通路.定理及推论在一个n阶图中,如果存在vi到自身的回路,则从vi到自身存在长度小于等于n的回路.推论 在一个n阶图中,如果vi到自身存在一条简单回路,则从vi到自身存在长度小于等于n的初级回路.连通在一个无向图G中,若从顶点vi到vj存在通路(当然

3、从vj到vi也存在通路),则称vi与vj是连通的.规定vi到自身总是连通的.在一个有向图D中,若从顶点vi到vj存在通路,则称vi可达vj.规定vi到自身总是可达的.短程线(无向图)设vi,vj为无向图G中的任意两点,若vi与vj是连通的,则称vi与vj之间长度最短的通路为vi与vj之间的短程线,短程线的长度称为vi与vj之间的距离,记作d(vi,vj).短程线(有向图)设vi,vj为有向图D中任意两点,若vi可达vj,则称从vi到vj长度最短的通路为vi到vj的短程线,短程线的长度称为vi到vj的距离,记作d.性质若vi不可达vj,规定d.d具有下面性质:(1)d 0,vivj时,等号成立.

4、(2)满足三角不等式,即 d+d d.在无向图中,还有对称性,即 d(vi,vj)d(vj,vi).例在在(a)(a)中有：中有：d(vd(v2 2，v v1 1)1 1，d(vd(v1 1，v v2 2)2 2，d(vd(v3 3，v v1 1)2 2，d(vd(v1 1，v v3 3)4 4；在在(b)(b)中有：中有：d(vd(v1 1，v v3 3)2 2，d(vd(v3 3，v v7 7)3 3，d(vd(v1 1，v v7 7)4 4。连通图(无向图)若无向图G是平凡图,或G中任意两顶点都是连通的,则称G是连通图;否则,称G是非连通图.无向图中,顶点之间的连通关系是等价关系.设G为

5、一个无向图,R是G中顶点之间的连通关系,按着R可将V(G)划分成k(k1)个等价类,记成V1,V2,Vk,由它们导出的导出子图GV1,GV2,GVk称为G的连通分支,其个数记为p(G).例G1是连通图，p(G1)1；G2是非连通图，且p(G2)4。连通图(有向图)设D是一个有向图,如果略去D中各有向边的方向后所得无向图G是连通图,则称D是连通图,或称D是弱连通图.若D中任意两顶点至少一个可达另一个,则称D是单向连通图.若D中任何一对顶点都是相互可达的,则称D是强连通图点割集设无向图G,若存在顶点子集V V,使G删除V将V中顶点及其关联的边都删除)后,所得子图GV的连通分支数与G的连通分支数满足p(G-V)p(G),而删除V的任何真子集V后,p(G-V)p(G),则称V为G的一个点割集.若点割集中只有一个顶点v,则称v为割点.边割集若存在边集子集E E,使G删除E(将E中的边从G中全删除)后,所得子图的连通分支数与G的连通分支数满足p(G-E)p(G),而删除E的任何真子集E后,p(G-E)p(G),则称E是G的一个边割集.若边割集中只有一条边e,则称e为割边或桥.例v2,v7，v3，v4为点割集，v3，v4为割点e1,e2，e1,e3,e4，e6，e7,e8，e2,e3,e4等都是割集，其中e6是桥。返 回