什么叫做割点?
发布网友
发布时间：2024-07-09 10:21
共1个回答
热心网友
时间：2024-07-11 06:06
在无向联通图 G=(V,E)中：若对于x∈V， 从图中删去节点x以及所有与x关联的边之后， G*成两个或两个以上不相连的子图， 则称x为G的割点。 简而言之， 割点是无向联通图中的一个特殊的点， 删去中这个点后， 此图不再联通， 而所以满足这个条件的点所构成的集合即为割点集合。
例如下图中，顶点u和v都是割点，其他顶点都不是割点。
对于铁路和公路等交通图，割点和桥在军事、经济上有重要的意义。而如果uv是桥且deg(u)≥2，则u是一个割点。
扩展资料：
定理1：
每个非平凡的连通图中至少有两个顶点不是割点。
证明 每个非平凡的连通图必有生成树，非平凡的树至少有两个度数为1的顶点，它们就不是非平凡的连通图的割点。
定理2：
设x为连通图
的边，则下列命题等价：
(1)x是G的桥；
(2)x不在G的任一圈上；
(3)存在两个不同的顶点u和w，使得x在每一条u与w间的每条路上；
(4)存在V的一个2-划分
，使得
，x在u与w间的每条路上。
参考资料来源：百度百科-割点
