通路的定义(有向图) 口定义:有向图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 iV, 使得v i-1和vi分别是ei的起点和终点(1in)。 相关点 不必区分多重边时，可以用相应顶点的序列表示通路。 长度为0的通路由单个顶点组成。 回路：起点与终点相同，长度大于0。 简单通路：边不重复，即，i, j, ij 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 本节提要