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