图的连通性
图的连通性 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 iV, 使得v i-1和vi是ei的两个端点(1in)。 相关点 不必区分多重边时，可以用相应顶点的序列表示通路。 长度为0的通路由单个顶点组成。 回路：起点与终点相同，长度大于0。 简单通路：边不重复，即，i, j, ij 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 通路（举例）