7.2通路、回路与图的连通性 简单通(回)路,初级通(回)路,复杂通(回)路 ■无向连通图,连通分支 弱连通图,单向连通图,强连通图 ■点割集与割点 边割集与割边(桥)
1 7.2 通路、回路与图的连通性 ▪简单通(回)路, 初级通(回)路, 复杂通(回)路 ▪无向连通图, 连通分支 ▪弱连通图, 单向连通图, 强连通图 ▪点割集与割点 ▪边割集与割边(桥)
通路与回路 定义给定图G-<V,E>(无向或有向的),G中顶点与边的交 替序列=v1v12…eP (1)若v(1≤K),V1,v是e的端点对于有向图,要求v是始点, ν是终点,则称/为通路,v是通路的起点,是通路的终点, 为通路的长度又若v="’则称/为回路. (2)若通路(回路)中所有顶点对于回路,除v=v)各异,则称为 初级通路(初级回路初级通路又称作路径,初级回路又称 作圈 (3)若通路(回路)中所有边各异,则称为简单通路(简单回路), 否则称为复杂通路(复杂回路)
2 通路与回路 定义 给定图G=<V,E>（无向或有向的），G中顶点与边的交 替序列=v0 e1 v1 e2…el vl， (1) 若i(1il), vi−1 , vi是ei的端点(对于有向图, 要求vi−1是始点, vi是终点), 则称为通路, v0是通路的起点, vl是通路的终点, l为通路的长度.又若v0 =vl，则称为回路. (2) 若通路(回路)中所有顶点(对于回路, 除v0 =vl )各异，则称为 初级通路(初级回路).初级通路又称作路径, 初级回路又称 作圈. (3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路)
通路与回路(续) 说明: ■表示方法 ①用顶点和边的交替序列定义),如n=ve”e2…e" ②用边的序列,如c=e2e ③简单图中,用顶点的序列,如厂=n…n ④非简单图中,可用混合表示法,如n=2n23 ■环是长度为1的圈,两条平行边构成长度为2的圈. 在无向简单图中,所有圈的长度≥3;在有向简单图 中,所有圈的长度≥2
3 通路与回路(续) 说明: ◼ 表示方法 ① 用顶点和边的交替序列(定义), 如=v0 e1 v1 e2…el vl ② 用边的序列, 如=e1 e2…el ③ 简单图中, 用顶点的序列,如=v0 v1…vl ④ 非简单图中,可用混合表示法,如=v0 v1 e2v2e5v3v4v5 ◼ 环是长度为1的圈, 两条平行边构成长度为2的圈. ◼ 在无向简单图中, 所有圈的长度3; 在有向简单图 中, 所有圈的长度2
通路与回路(续) ■在两种意义下计算的圈个数 ①定义意义下 在无向图中,一个长度为l(3)的圈看作21个不同的 圈.如vv"2v,v2v1,n2v1v2看作3个不同的圈 在有向图中,一个长度为l(3)的圈看作个不同的 ②同构意义下 所有长度相同的圈都是同构的,因而是1个圈
4 通路与回路(续) ◼ 在两种意义下计算的圈个数 ① 定义意义下 在无向图中, 一个长度为l(l3)的圈看作2l个不同的 圈. 如v0 v1 v2v0 , v1 v2v0v1 , v2v0v1 v2看作3个不同的圈. 在有向图中, 一个长度为l(l3)的圈看作l个不同的 圈. ② 同构意义下 所有长度相同的圈都是同构的,因而是1个圈
通路与回路(续) 定理在n阶图G中,若从顶点ν到v,(ν≠v;)存在通 路,则从v到v存在长度小于等于n-1的通路 推论在n阶图G中,若从顶点到y(以2y)存在通 路,则从ν到ν存在长度小于等于n-1的初级通路 定理在一个n阶图G中,若存在ν到自身的回路,则 定存在v到自身长度小于等于n的回路. 推论在一个n阶图G中,若存在ν到自身的简单回 路,则一定存在长度小于等于n的初级回路
5 通路与回路(续) 定理 在n阶图G中，若从顶点vi到vj（vivj）存在通 路，则从vi到vj存在长度小于等于n−1的通路. 推论 在n阶图G中，若从顶点vi到vj（vivj）存在通 路，则从vi到vj存在长度小于等于n−1的初级通路. 定理 在一个n阶图G中，若存在vi到自身的回路，则 一定存在vi到自身长度小于等于n的回路. 推论 在一个n阶图G中，若存在vi到自身的简单回 路，则一定存在长度小于等于n的初级回路