关于割点的三个等价命题 以下三个命题等价： (1)v是割点。 (2)存在V-{w}的分划{V,V,,使u∈V,w∈V,uw-通路均包含v。 (3)存在顶点u,w(uy,w≠y),使得任意的uw-通路均包含v。 ·证明： (1)→(2)：.v是割点，G-v至少存在两个连通分支，设其中一个的 顶点集是V1。令V,=V-(V,U{v),则u∈V,w∈V,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是割点。 13