南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 19 图的连通性

图的连通性

图的连通性 1

回顾 2 口内容1：图的定义 ▣内容2：图的应用 口内容3：图的表示 ▣内容4：图的同构

回顾  内容1：图的定义  内容2：图的应用  内容3：图的表示  内容4：图的同构 2

本节提要 3 口内容1：通路与回路 ▣内容2：无向图的连通性 口内容3：有向图的连通性

 内容1：通路与回路  内容2：无向图的连通性  内容3：有向图的连通性 3 本节提要

通路的定义（无向图） 口定义：图G中从到vn的长度为n的通路是G的n条边 e,…,e的序列，满足下列性质 口存在∈V,使得y1和是e的两个端点(1≤Kn)。 相关点 口不必区分多重边时，可以用相应顶点的序列表示通路。 口长度为0的通路由单个顶点组成。 口回路：起点与终点相同，长度大于0。 口简单通路(trai训：边不重复，即，i,j,j→ee ▣初级通路(Path):点不重复，亦称为“路径

 定义：图G中从v0到vn的长度为n的通路是G的n条边 e 1 ,…, en的序列，满足下列性质  存在viV , 使得vi-1和vi是ei的两个端点 (1in)。  相关点  不必区分多重边时，可以用相应顶点的序列表示通路。  长度为0的通路由单个顶点组成。  回路：起点与终点相同，长度大于0。  简单通路(trail)：边不重复，即，i, j, ij  eiej  初级通路(path)：点不重复，亦称为“路径” 4 通路的定义（无向图）

通路（举例） 5 a b d e f ▣简单通路：a,d,c,￡，e。长度为4。 口回路：b,c,￡，e,b。长度为4。 ▣通路：a,b,e,d,a,b。长度为5。 口不是通路：d,e,c,b

 简单通路：a, d, c, f, e。 长度为4。  回路：b, c, f, e, b。长度为4。  通路：a, b, e, d, a, b。 长度为5。  不是通路：d, e, c, b。 5 a b c d e f 通路（举例）

通路的定义（有向图） 6 定义：有向图G中从到v,的长度为n的通路是G的n条 边e,…,en的序列，满足下列性质 口存在∈V,使得1和分别是e的起点和终点(1≤i≤n)。 相关点 口不必区分多重边时，可以用相应顶点的序列表示通路。 口长度为0的通路由单个顶点组成。 口回路：起点与终点相同，长度大于0。 口简单通路：边不重复，即，i,j,j→ee ▣初级通路：点不重复

 定义：有向图G中从v0到vn的长度为n的通路是G的n条 边e1 ,…, en的序列，满足下列性质  存在viV, 使得vi-1和vi分别是ei的起点和终点 (1in)。  相关点  不必区分多重边时，可以用相应顶点的序列表示通路。  长度为0的通路由单个顶点组成。  回路：起点与终点相同，长度大于0。  简单通路： 边不重复，即，i, j, ij  eiej  初级通路：点不重复 6 通路的定义（有向图）

通路（举例） 7 1 V2 V4 V3 口简单通路：，4,2，。长度为3。 口回路：2,1,4,2。长度为3。 口通路：2，，1,4,2，。长度为5

 简单通路：v1 , v4 , v2 , v3。 长度为3。  回路： v2 , v1 , v4 , v2。长度为3。  通路： v2 , v3 , v1 , v4 , v2 , v3 。 长度为5。 7 v1 v2 v4 v3 通路（举例）

通路与同构 8 口设图G的邻接矩阵为A ▣(A时：到的长度为k的通路个数 ▣(A:到的长度为的回路个数 口同构图的不变量：长度为的回路的存在性

 设图G的邻接矩阵为A  (Ak )i,j: vi到vj的长度为k的通路个数  (Ak )i,i: vi到vi的长度为k的回路个数  同构图的不变量：长度为k的回路的存在性。 8 通路与同构

通路与同构 9 ul u6 6 02 V2 u3 v3 us v5 u4 4 u2 V2 u3 Vi v3 us v4

9 u6 u2 u1 u5 u3 u4 v6 v2 v1 v5 v3 v4 u2 u5 u1 u3 u4 v2 v5 v1 v3 v4 通路与同构

本节提要 10 口内容1：通路与回路 口简单通路边不重复、初级通路点不重复 ▣内容2：无向图的连通性 ▣内容3：有向图的连通性

 内容1：通路与回路  简单通路边不重复、初级通路点不重复  内容2：无向图的连通性  内容3：有向图的连通性 10 本节提要