无向图的连通性 11 口定义：无向图G称为是连通的，如果G中任意两个不 同顶点之间都有通路。 a G2
定义：无向图G称为是连通的，如果G中任意两个不 同顶点之间都有通路。 11 a c b e d a c b e d G1 G2 无向图的连通性
连通分支 12 口每个无向图是若干个互不相交的连通分支的并。 “顶点之间存在通路”是一个等价关系，任一等价类上 的导出子图即为一个连通分支。 口若图G中存在从u到的通路，则一定有从u到的简 单通路/初级通路。 最短通路必是简单的，也是初级的（没有重复顶点）
每个无向图是若干个互不相交的连通分支的并。 “顶点之间存在通路”是一个等价关系，任一等价类上 的导出子图即为一个连通分支。 若图G中存在从u到v的通路，则一定有从u到v的简 单通路/初级通路。 最短通路必是简单的，也是初级的（没有重复顶点）。 12 连通分支
点的删除与连通分支数量的增减 13 口设p(G)表示图G中连通分支数 p(G-v(其中v是G中任意一个顶点)的情况比较多 (注意：删除顶点意味着同时删除该点关联的边) 口连通分支的数量可能会… 口减少（删除孤立点） (孤立点) 口不变（例如：删除悬挂点） (悬挂点) 口增加很多个（例如：star)
设p(G)表示图G中连通分支数 p(G-v)(其中v是G中任意一个顶点)的情况比较多 （注意：删除顶点意味着同时删除该点关联的边） 连通分支的数量可能会…… 减少 (删除孤立点) 不变 (例如：删除悬挂点) 增加很多个 (例如：star) 13 （孤立点） （悬挂点） 点的删除与连通分支数量的增减
割点(cut vertex,articulation vertex) 14 o定义：G是图，vEVc,若p(G-v)>p(G),则称v是割点 割点 (注意：只需考虑割点所在的连通分支，以下讨论不妨只 考虑连通图)
割点（cut vertex, articulation vertex） 定义：G是图, v∈VG, 若p(G-v)>p(G), 则称v是割点 (注意：只需考虑割点所在的连通分支，以下讨论不妨只 考虑连通图) 14 割点
关于割点的三个等价命题 15 口以下三个命题等价： (1)v是割点。 (②)存在V-{v}的分划{V1,V2},使u∈V1,w∈V2,uw-通路均包含vo (③)存在顶点u,w(u≠V,w≠v),使得任意的uw-通路均包含v。 口证明： (I)→(2)：.v是割点，G-v至少存在两个连通分支，设其中一个的顶 点集是V1。令V2=V-(V1U{v}),则u∈V1,wEV2,u,w一定在G-v的 不同的连通分支中。.在G中，任何uw-通路必含v。 (2)→(3：注意：(3)是(2)的特例。 (3)→(1)：显然，在G-v中已不可能还有uw-通路，∴.G-v不连通，∴.v 是割点
以下三个命题等价： (1) v是割点。 (2) 存在V-{v}的分划{V1 , V2}, 使u∈V1 , w∈V2 , uw-通路均包含v。 (3) 存在顶点u,w(u≠v, w≠v)，使得任意的uw-通路均包含v。 证明： (1)(2): ∵v是割点，G-v至少存在两个连通分支，设其中一个的顶 点集是V1。令V2=V-(V1∪{v}), 则u∈V1 , w∈V2 , u,w一定在G-v的 不同的连通分支中。∴在G中，任何uw-通路必含v。 (2)(3): 注意：(3)是(2)的特例。 (3)(1): 显然，在G-v中已不可能还有uw-通路，∴G-v不连通，∴v 是割点。 15 关于割点的三个等价命题