资源描述：
《7.2 通路、迹、连通》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、通路给定图G＝.设G中顶点和边的交替序列为Γ＝v0e1v1e2…elvl,若Γ满足如下条件:vi-1和vi是ei的端点(在G是有向图时,要求vi-1是ei的始点,vi是ei的终点),i＝1,2,…,l,则称Γ为顶点v0到vl的通路.v0和vl分别称为此通路的起点和终点,Γ中边的数目l称为Γ的长度.当v0＝vl时,此通路称为回路.迹若Γ中的所有边e1,e2,···,el互不相同,则称Γ为简单通路或一条迹.若回路中的所有边互不相同,称此回路为简单回路或一条闭迹.初级通路若通路的所有顶点v0,v1···,vl互不相同(从而所有边互不相同),则称此通路为初级通路或
2、一条路径.若回路中,除v0＝vl外,其余顶点各不相同,所有边也各不相同,则称此回路为初级回路或圈.复杂通路有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路.由定义可知,初级通路(回路)是简单通路(回路),但反之不真.定理在一个n阶图中,若从顶点vi到vj(vi≠vj)存在通路,则从vi到vj存在长度小于等于n－1的通路.推论在一个n阶图中,若从顶点vi到vj(vi≠vj)存在通路,则从vi到vj存在长度小于等于n－1的初级通路.定理及推论在一个n阶图中,如果存在vi到自身的回路,则从vi到自身存在长度小于等于n的回路.推论在一个n阶图中,如果vi到自身
3、存在一条简单回路,则从vi到自身存在长度小于等于n的初级回路.连通在一个无向图G中,若从顶点vi到vj存在通路(当然从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长度最短的通路为
4、vi到vj的短程线,短程线的长度称为vi到vj的距离,记作d.性质若vi不可达vj,规定d＝∞.d具有下面性质:(1)d≥0,vi＝vj时,等号成立.(2)满足三角不等式,即d+d≥d.在无向图中,还有对称性,即d(vi,vj)＝d(vj,vi).例在(a)中有：d(v2，v1)＝1，d(v1，v2)＝2，d(v3，v1)＝2，d(v1，v3)＝4；在(b)中有：d(v1，v3)＝2，d(v3，v7)＝3，d(v1，v7)＝4。连通图(无向图)若无向图G是平凡图,或G中
5、任意两顶点都是连通的,则称G是连通图;否则,称G是非连通图.无向图中,顶点之间的连通关系是等价关系.设G为一个无向图,R是G中顶点之间的连通关系,按着R可将V(G)划分成k(k≥1)个等价类,记成V1,V2,···,Vk,由它们导出的导出子图G[V1],G[V2],…,G[Vk]称为G的连通分支,其个数记为p(G).例G1是连通图，p(G1)＝1；G2是非连通图，且p(G2)＝4。连通图(有向图)设D是一个有向图,如果略去D中各有向边的方向后所得无向图G是连通图,则称D是连通图,或称D是弱连通图.若D中任意两顶点至少一个可达另一个,则称D是单向连通图.若D中任何一对
6、顶点都是相互可达的,则称D是强连通图．点割集设无向图G＝,若存在顶点子集V'V,使G删除V'将V'中顶点及其关联的边都删除)后,所得子图G－V'的连通分支数与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的一个边割集.若边割
7、集中只有一条边e,则称e为割边或桥.例{v2,v7}，{v3}，{v4}为点割集，{v3}，{v4}为割点{e1,e2}，{e1,e3,e4}，{e6}，{e7,e8}，{e2,e3,e4}等都是割集，其中e6是桥。返回
