《离散数学》课程教学资源（PPT课件讲稿）图的连通性

图的连通性

图的连通性 1

回顾 口内容1:图的定义 口内容2:图的应用 口内容3:图的表示 口内容4:图的运算 口内容5:图的同构

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

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

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

通路的定义(无向图) 口定义:图G中从而到v的长度为m的通路是G的m条边 3cn的序列,满足下列性质 口存在vV使得v1和是e的两个端点(1≤m) 口相关点 口不必区分多重边时,可以用相应项点的序列表示通路。 口长度为0的通路由单个项点组成。 口回路:超点与终点相同,长度大于0 口简单通路:边不重复,即,ⅵi→e托 口初级通路:点不重复,亦称为“路径

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

通路(举例) 口简单通路:a,d,c,f,e。长度为4 口回路:b,c,f,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 通路（举例）

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

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

通路(举例) 口简单通路:v,V4,V,。长度为3 口回路:2咋,四,吃0长度为3 口通路:2,3,听,V,,吟。长度为5

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

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

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

通路与同构

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

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

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