关于割点的三个等价命题 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 关于割点的三个等价命题