所有栏目

割点

作者:百科科普

在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。

如果某个割点集合只含有一个顶点X(也即{X}是一个割点集合),那么X称为一个割点。

割点定义

在无向联通图 G=(V,E)中: 若对于x∈V, 从图中删去节点x以及所有与x关联的边之后, G分裂成两个或两个以上不相连的子图, 则称x为G的割点。 简而言之, 割点是无向联通图中的一个特殊的点, 删去中这个点后, 此图不再联通, 而所以满足这个条件的点所构成的集合即为割点集合。

设G是一个图,x是G的一条边,如果G-x的连通分支数大于G的连通分支数,则称x是G的一个桥,或割边。

图1中,顶点u和v都是割点,其他顶点都不是割点,边uv是桥,其他边都不是桥。

对于铁路和公路等交通图,割点和桥在军事、经济上有重要的意义。显然有割点的图不是哈密顿图。而如果uv是桥且deg(u)≥2,则u是一个割点。

割点相关性质

割点定理1

设v是连通图

的一个顶点,则下列命题等价:

(1)v是G的一个割点;

(2)存在与v不同的两个顶点u和w,使得v在u与w间的每条路上;

(3)存在V{v}的一个2-划分

,使得

,v在u与w间的每条路上。

证明 (1)

(3):设

的一个割点,则

的连通分支数大于G的连通分支数,于是

至少有两个连通分支。令U是G-v的一个连通分支的顶点集,W是其他各连通分支构成的

的子图的顶点集。

显然

是V{v}的一个2-划分。对

,u与w不在

的同一个连通分支中,所以在

中u与w间没有路。而因为G是连通图,所以在G中u与w间有路。因此,在G中,v必在u与w间的每条路上。

(3)

(2):(2)是(3)的特例,所以(3)成立时(2)必成立。

(2)

(1):假设(2)成立,欲证(1)成立,只需证

是不连通图。用反证法。假设

连通,则在

中至少有一条u与w间的路。于是G中有一条不过v的u与w间的路,这与(2)矛盾。所以

是不连通图,从而v是G的一个割点。

割点定理2

每个非平凡的连通图中至少有两个顶点不是割点。

证明 每个非平凡的连通图必有生成树,非平凡的树至少有两个度数为1的顶点,它们就不是非平凡的连通图的割点。

割点定理3

设x为连通图

的边,则下列命题等价:

(1)x是G的桥;

(2)x不在G的任一圈上;

(3)存在两个不同的顶点u和w,使得x在每一条u与w间的每条路上;

(4)存在V的一个2-划分

,使得

,x在u与w间的每条路上。

热点导航
教育资讯 知道问答 公考资讯 司法考试 建筑知识 工作范文 大学排名 报考专业 学习方法 句子美文 秒知回答 作业解答 精选答案 知途问学