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