《离散数学》课程PPT教学课件（讲稿）第7章 图的基本概念（7.2-7.3）通路、回路与图的连通性、图的矩阵表示

7.2通路、回路与图的连通性 简单通(回)路,初级通(回)路,复杂通(回)路 ■无向连通图,连通分支 弱连通图,单向连通图,强连通图 ■点割集与割点 边割集与割边(桥)

1 7.2 通路、回路与图的连通性 ▪简单通(回)路, 初级通(回)路, 复杂通(回)路 ▪无向连通图, 连通分支 ▪弱连通图, 单向连通图, 强连通图 ▪点割集与割点 ▪边割集与割边(桥)

通路与回路 定义给定图G-(无向或有向的),G中顶点与边的交 替序列=v1v12…eP (1)若v(1≤K),V1,v是e的端点对于有向图,要求v是始点, ν是终点,则称/为通路,v是通路的起点,是通路的终点, 为通路的长度又若v="’则称/为回路. (2)若通路(回路)中所有顶点对于回路,除v=v)各异,则称为 初级通路(初级回路初级通路又称作路径,初级回路又称 作圈 (3)若通路(回路)中所有边各异,则称为简单通路(简单回路), 否则称为复杂通路(复杂回路)

2 通路与回路 定义 给定图G=（无向或有向的），G中顶点与边的交 替序列=v0 e1 v1 e2…el vl， (1) 若i(1il), 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(l3)的圈看作2l个不同的 圈. 如v0 v1 v2v0 , v1 v2v0v1 , v2v0v1 v2看作3个不同的圈. 在有向图中, 一个长度为l(l3)的圈看作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（vivj）存在通 路，则从vi到vj存在长度小于等于n−1的通路. 推论 在n阶图G中，若从顶点vi到vj（vivj）存在通 路，则从vi到vj存在长度小于等于n−1的初级通路. 定理 在一个n阶图G中，若存在vi到自身的回路，则 一定存在vi到自身长度小于等于n的回路. 推论 在一个n阶图G中，若存在vi到自身的简单回 路，则一定存在长度小于等于n的初级回路

无向图的连通性 设无向图G=, u与v连通:若u与ν之间有通路.规定u与自身总连通 连通关系R={<,|,∈且~w是V上的等价关系 连通图:平凡图,任意两点都连通的图 连通分支:关于R的等价类的导出子图 设VR={V1,V2,…,Vh},GIV1l,GIV2l,…GIVA是G的 连通分支,其个数记作p(O=k G是连通图台→p(G)=1

6 无向图的连通性 设无向图G=, u与v连通: 若u与v之间有通路. 规定u与自身总连通. 连通关系 R={| u,v V且uv}是V上的等价关系 连通图: 平凡图, 任意两点都连通的图 连通分支: V关于R的等价类的导出子图 设V/R={V1 ,V2 ,…,Vk }, G[V1 ], G[V2 ], …,G[Vk ]是G的 连通分支, 其个数记作p(G)=k. G是连通图 p(G)=1

短程线与距离 u与之间的短程线:l与υ之间长度最短的通路 与v连通) 与之间的距离d(u,v):u与之间短程线的长度 若u与v不连通,规定l(u,y)=∞ 性质: d(u,y)≥20,且d(un,y)=0分>u=v d(u, v)=(v,u) d(u, v)+(v, m)2d(u, w)

7 短程线与距离 u与v之间的短程线: u与v之间长度最短的通路 (u与v连通) u与v之间的距离d(u,v): u与v之间短程线的长度 若u与v不连通, 规定d(u,v)=∞. 性质： d(u,v)0, 且d(u,v)=0  u=v d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)

点割集 记G-v:从G中删除ν及关联的边 GV:从G中删除V中所有的顶点及关联的边 G-e:从G中删除e G-E:从G中删除E中所有边 定义设无向图G=,VcV若p(G-V)>p(O且 VcV,p(G-V)=p(G),则称V为G的点割集.若 吵为点割集,则称p为割点

8 点割集 记 G−v: 从G中删除v及关联的边 G−V: 从G中删除V中所有的顶点及关联的边 G−e : 从G中删除e G−E: 从G中删除E中所有边 定义 设无向图G=, VV, 若p(G−V)>p(G)且 VV , p(G−V)=p(G), 则称V为G的点割集. 若 {v}为点割集, 则称v为割点

点割集(续) 例{v1,”4},{}是点割集,v是割点 {v2,3}是点割集吗? V

9 点割集(续) 例 {v1 ,v4 }, {v6 }是点割集, v6是割点. {v2 ,v5 }是点割集吗？

边割集 定义设无向图G=,EE,若p(G-E)>p(G)且VE"<E, p(G-E)=p(G),则称E为G的边割集若{e}为边割集,则称e 为割边或桥. 在上一页的图中,{e1e2},{e1;e33s},{es}等是边割集, e3是桥,{en,,sy}是边割集吗? 几点说明: K无点割集 n阶零图既无点割集,也无边割集 若G连通,E为边割集,则p(GE")=2 若G连通,V为点割集,则p(G-V)≥2 10

10 边割集 定义 设无向图G=, EE, 若p(G−E)>p(G)且EE , p(G−E)=p(G),则称E为G的边割集.若{e}为边割集,则称e 为割边或桥. 在上一页的图中，{e1 ,e2 }，{e1 ,e3 ,e5 ,e6 }，{e8 }等是边割集， e8是桥，{e7 ,e9 ,e5 ,e6 }是边割集吗？ 几点说明： Kn无点割集 n阶零图既无点割集，也无边割集. 若G连通，E为边割集，则p(G−E)=2 若G连通，V为点割集，则p(G−V)2