离散数学7.2.ppt

通路 给定图G＝V,E.设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互不相同(从而所有边互不相同),则称此通路为初级通路或一条路径. 若回路中,除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到自身存在一条简单回路,则从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长度最短的通路为vi到vj的短程线, 短程线的长度称为vi到vj的距离,记作dvi,vj. 性质 若vi不可达vj,规定dvi,vj＝∞. dvi,vj具有下面性质: (1) dvi,vj ≥0,vi＝vj时,等号成立. (2)满足三角不等式,即 dvi,vj +dvj,vk ≥dvi,vk. 在无向图中,还有对称性,即 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中任意两顶点都是连通的,则称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中任何一对顶点都是相互可达的,则称D是强连通图． 点割集 设无向图G＝V,E,若存在顶点子集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的一个边割集. 若边割集中只有一条边e,则称e为割边或桥. 例 定义14.17 设G是一无向连通图，称(κ(G)为G的点连通度， κ(G)=min{|V‘| | V′ 是G的点割集 或V′使G-V′成平凡图｝ 称λ（G）为G的边连通度， λ（G）=min{|E’| |E′是G的边割集} 由定义容易得到下面结论： （1）若