点割集

设V^{'}\subset V 且 V^{'} 不为空集，使得在无向图中去掉 V^{'} 中的点之后，图的连通分支增加，则V^{'}称为无向图中的一个点割集

需要注意的是当删除V^{'} 的任何一个真子集中的点之后，不会增加图的连通分支。当集合V^{'} 中只含有一个元素时，该元素可称为图

的一个割点。

现给出以下例题方便大家理解。发现，当在图中删除点割集中的点之后，图会被分为两个或多个部分。集合{ v_{1}, v_{3} }为什么不是点割集？？？容易发现，该集合的真子集{ v_{3} } 是图的一个点割集。

边割集

参考点割集，在此不做多余的解释。

需注意，当边割集中只存在一个元素时，该边称做割边或桥。

什么真子集之类的对于边割集同样适用

 

割集的说明（划重点）

  1. K_{n}无点割集
  2. n阶零图既无点割集，也无边割集
  3. 若G连通，E^{'}为边割集，则p\left (G^{'}-E^{'}\right ) = 2 
  4. 若G连通，V^{'}为点割集，则p\left ( G^{'}-V^{'} \right )\geq 2

 

点连通度

使连通图G成为一个不连通图需要删除的点的最小数目，记为K，则图也可称作K-连通图

 

边连通度

使连通图G成为一个不连通图需要删去的边的最少数目，记为R，则图也可称作R边-连通图

 

点连通度与边连通度的关系

k\left ( G \right )\leqslant r\left ( G \right )\leqslant \delta \left ( G \right )

其中\delta \left ( G \right ) 表示图的最小度

Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

1.8B 体积、33 种语言互译｜腾讯混元 HY-MT1.5-1.8B 多语言机器翻译模型上线

在跨语言交流日益频繁的今天，阅读外语菜单、处理多语言邮件、与不同语言背景的人沟通，已经成为很多人日常工作与生活的一部分。过去，这类需求往往依赖联网翻译工具，而如今，—— 一部设备即可支持的相互翻译。当 AI 不再只是“逐字直译”，而是开始理解语境、风格与语言之间的细微差异，机器翻译就真正具备了今天为大家介绍一款高质量、多语言、支持端侧部署的机器翻译模型 ——，现已上线 AtomGit AI 社区，

avatar AtomGit开源社区
cover

LET：面向真实场景与长时序任务的人形机器人数据集

avatar AtomGit开源社区
cover

寒假充电计划启动！解锁 Flutter-OH 新技能 | 21 天训练营招募中

avatar AtomGit开源社区