割点
离散数学名词
在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。
定义
在无向联通图 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间的每条路上;
,使得,v在u与w间的每条路上。
证明 (1)(3):设是的一个割点,则的连通分支数大于G的连通分支数,于是至少有两个连通分支。令U是G-v的一个连通分支的顶点集,W是其他各连通分支构成的的子图的顶点集。
显然,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间的每条路上。
参考资料
最新修订时间:2024-08-06 22:13
目录
概述
定义
相关性质
参考资料