在一个
无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的
连通分量增多,就称这个点集为割点集合。
在无向联通图 G=(V,E)中: 若对于x∈V, 从图中删去节点x以及所有与x关联的边之后, G分裂成两个或两个以上不相连的子图, 则称x为G的割点。 简而言之, 割点是无向联通图中的一个特殊的点, 删去中这个点后, 此图不再联通, 而所以满足这个条件的点所构成的集合即为割点集合。
设G是一个图,x是G的一条边,如果G-x的连通分支数大于G的连通分支数,则称x是G的一个
桥,或
割边。
对于铁路和公路等交通图,割点和桥在军事、经济上有重要的意义。显然有割点的图不是
哈密顿图。而如果uv是桥且deg(u)≥2,则u是一个割点。
证明 (1)(3):设是的一个割点,则的连通分支数大于G的连通分支数,于是至少有两个连通分支。令U是G-v的一个连通分支的顶点集,W是其他各
连通分支构成的的子图的顶点集。
(2)(1):假设(2)成立,欲证(1)成立,只需证是不连通图。用
反证法。假设连通,则在中至少有一条u与w间的路。于是G中有一条不过v的u与w间的路,这与(2)矛盾。所以是不连通图,从而v是G的一个割点。
证明 每个非平凡的连通图必有
生成树,非平凡的树至少有两个度数为1的顶点,它们就不是非平凡的连通图的割点。