1 基本定义
割点是图论中用于描述“关键顶点”的概念，主要用来刻画一个连通结构中哪些点对整体连通性具有决定作用。若某个顶点的存在直接关系到图是否保持连通，则该顶点往往被视为结构中的薄弱环节。
1.1 图与连通性的基础概念
图由顶点和边组成，用于抽象表示对象及其相互关系。若任意两个顶点之间都存在路径相连，则称该图为连通图。连通性是讨论割点的前提，因为只有在连通图中，删除顶点后导致“断开”的现象才有明确意义。
在无向图中，路径表示沿边从一个顶点到达另一个顶点的可行路线。若去掉某些顶点后，图被分成互不相通的若干部分，则说明这些顶点在原图中承担了连接作用。
1.2 割点的定义
在一个连通图中，如果删除某个顶点以及与它相连的所有边后，图的连通分量数量增加，那么这个顶点就称为割点。换言之，割点是会使图“分裂”的顶点。
割点的定义强调的是删除顶点前后图结构的变化，而不是顶点本身的度数高低。一个顶点即便只连接少量边，也可能是割点；反之，度数较大的顶点未必是割点。
1.2.1 删除顶点后的图变化
删除顶点时，不仅要去掉该顶点本身，还要一并移除所有与之关联的边。随后观察剩余图的结构是否出现新的连通块。若原来可以互相到达的部分被切开，说明该顶点在连接路径中起到了桥梁作用。
这种变化常体现在图被分成多个彼此无法通过原有路径到达的区域。割点之所以重要，就在于它对应了结构上的“断裂点”。
1.2.2 连通分量数量的判定
判断一个顶点是否为割点，核心在于比较删除前后的连通分量数。若删除该点后连通分量数增加，则它是割点；若连通分量数不变，则它不是割点。
需要注意的是，对于本来就不连通的图，通常讨论割点时更常聚焦于其连通分量内部。也就是说，割点的定义多建立在连通图或连通子图上，以便明确结构变化。
1.3 割点与非割点
割点与非割点共同构成图中顶点的两种基本角色。前者会破坏整体连通性，后者则不会。两者的区分有助于识别图中真正影响结构稳定性的节点。
1.3.1 必要条件
一个顶点要成为割点，通常必须位于某些关键路径上，并且它的删除会使原图中至少两部分失去联系。直观上看，它像是多个区域之间的“转接站”。
但并非所有处于路径中间的顶点都是割点。只有当该顶点是某些部分相互连接的必经之点时，删除它才会造成连通分量增加。
1.3.2 典型反例
在一个三角形图中，任意删除一个顶点，剩余两个顶点仍可通过边相连，因此不存在割点。这说明“位于图中间”并不等同于“关键节点”。
另一个反例是完全图中的顶点。由于任意两个顶点之间都直接相连，删除其中一个并不会使图断开，因此这类图通常没有割点。
2 性质与判定
割点的性质既有一般规律，也会因图的结构类型而呈现不同表现。实际判断时，除了直接定义外，还可以借助深度优先搜索等算法高效识别。
2.1 基本性质
割点的存在与图的整体结构紧密相关。它往往出现在“分支交汇”或“链式连接”的位置，而在高度稠密的图中则较少出现。
2.1.1 割点与连通图的关系
在连通图中，割点的出现意味着图并非“高度冗余”的连接结构。删除某个顶点后若连通性受损，说明原图对该点存在依赖。
如果一个连通图没有割点，则称该图具有较强的顶点连通稳定性。这样的图在删除单个顶点时仍能保持连通，结构更为稳固。
2.1.2 割点与度数的关系
顶点度数较高并不必然意味着它是割点。度数只反映该点与多少边相连，而割点强调的是“是否承担连接不同部分的职责”。
不过，在一些树状或稀疏结构中，度数较高的顶点更容易成为割点，因为它们往往连接多个分支。相反，在稠密图里，即使顶点度数很大，也可能因替代路径充足而不是割点。
2.2 特殊图中的割点
不同类型的图对割点的表现有明显差异。通过研究典型图形，可以更直观地理解割点的定义和作用。
2.2.1 树中的割点
在树中，除叶子以外的大多数顶点通常都是割点。因为树是无环连通图，任意一个内部顶点的删除都可能使原图分成多个部分。
树的结构本身缺乏冗余路径，因此其连通性对中间顶点依赖较强。这也使树成为理解割点概念的经典例子。
2.2.2 完全图中的割点
完全图中任意两个顶点之间都存在直接边相连，因此删除一个顶点后，其余顶点仍然保持互相可达。故完全图中不存在割点。
这类图体现了高度冗余的连接方式，也说明“边多”通常会降低割点出现的可能性。
2.2.3 环图中的割点
环图中每个顶点都位于一个闭合回路上。删除任意一个顶点后，剩余部分仍可沿另一方向连接，因此环图中一般没有割点。
环结构提供了替代路径，这使得它比树更稳定，也更不容易因单点失效而断开。
2.3 判定方法
割点判定既可以通过直接尝试删除顶点，也可以借助更高效的图算法。前者直观但效率较低，后者适合大规模图处理。
2.3.1 朴素删除法
朴素删除法的思路很直接：依次删除每个顶点，观察图是否失去连通性。若删除某点后连通分量数增加，则该点为割点。
这种方法实现简单，适合教学演示或小规模图的手工分析。但由于每次删除都可能需要重新检查连通性，因此在大图中效率较低。
2.3.2 深度优先搜索法
深度优先搜索法是识别割点的经典算法。它利用图遍历过程中记录的发现时间、回溯信息以及低点值，判断某个顶点是否为连接子树与祖先的重要枢纽。
在搜索树中，如果某个子节点无法通过回边回到更早访问的祖先节点，那么其父节点就可能是割点。这种方法可以在线性时间内完成，因而广泛使用。
2.3.2.1 时间复杂度分析
采用深度优先搜索识别割点时，通常只需遍历每个顶点和每条边一次，因此时间复杂度为 O(V+E)，其中 V 为顶点数，E 为边数。
相比朴素删除法，这种复杂度在大图中优势明显。它使割点检测成为图算法中一项标准而高效的基础操作。
2.3.2.2 低点值与回边判断
低点值用于表示从某个顶点或其子树出发，沿树边和至多一条回边能够到达的最早访问顶点。通过比较子节点的低点值与父节点的发现时间，可以判断父节点是否为割点。
若某个子节点及其后代无法通过回边连接到父节点之前的祖先，则父节点的删除会切断该子树与图其余部分的联系。这个判据是深度优先搜索判定割点的核心。
3 相关概念
割点并不是孤立概念，它与割边、双连通分量、点连通度等内容密切相关。理解这些相关术语，有助于把握图的脆弱点与整体稳定性的关系。
3.1 割边
割边指的是删除后会使图的连通分量数量增加的边，也称为桥。它与割点类似，但研究对象从顶点转为边。
3.1.1 割点与割边的区别
割点关注的是顶点删除后的影响，割边则关注边删除后的影响。二者虽都体现“去除一个元素导致断开”，但作用对象不同。
有些图中存在割边但没有割点，例如一条简单链中的边往往是割边；也有些图存在割点却没有割边，例如某些由多个三角形通过单个公共顶点连接的结构。
3.1.2 共同点与联系
割点和割边都反映了图结构中的脆弱环节，都是连通性分析的重要工具。它们常用于寻找网络中的关键位置，判断系统是否存在单点失效风险。
从结构上看，二者都与“替代路径是否充足”密切相关。路径越多，割点和割边出现的概率通常越低。
3.2 双连通分量
双连通分量是图中不包含割点的极大子图。它描述的是一种更稳定的局部结构，在其中删除任意一个顶点都不会使子图断开。
3.2.1 顶点双连通图
若一个连通图删除任意一个顶点后仍保持连通，则称为顶点双连通图。这样的图没有割点，说明其顶点连接关系较为稳固。
顶点双连通性是研究图鲁棒性的重要指标之一。它常出现在需要强调结构连续性的场景中，如容错网络设计和图分块分析。
3.2.2 割点与双连通分解
一个连通图可以分解为若干双连通分量，而割点则起到连接这些分量的作用。也就是说，割点常位于分量之间的交界处。
这种分解方式为复杂图的分析提供了层次化视角。通过先找割点，再划分双连通分量，可以更清晰地认识图的内部结构。
3.3 点连通度
点连通度用于衡量图在顶点删除下的稳定程度。它表示使图失去连通性所需删除的最少顶点数，是连通性强弱的重要指标。
3.3.1 最小割点集
最小割点集是指删除后能使图不连通的最少顶点集合。若最小割点集只含一个顶点，那么该顶点就是割点。
更一般地，若一个图需要删除多个顶点才会断开，则其结构比存在单个割点的图更稳固。最小割点集因此可用来衡量图的“断裂门槛”。
3.3.2 与图鲁棒性的关系
点连通度越高，图通常越不容易因为少量顶点失效而分裂。换言之，点连通度反映了网络抵抗节点故障的能力。
在实际建模中，较高的点连通度意味着更强的冗余与容错性；而割点的存在则提示系统可能存在单点依赖。
4 应用
割点不仅是理论图论中的重要对象，也在网络分析、算法实现和教学训练中具有广泛用途。它帮助人们识别结构中的关键节点，并据此进行优化与维护。
4.1 网络结构分析
在各种网络模型中，割点可以被理解为连接多个局部区域的重要节点。它的识别有助于评估网络是否容易因局部故障而分裂。
4.1.1 通信网络中的关键节点
在通信网络中，割点对应那些一旦失效就可能导致部分设备失去互联能力的中继点或交换节点。识别这类节点，有助于提升系统冗余和可靠性。
工程上常通过增加备份链路、设置替代路径等方式降低割点带来的风险。这样即使某个节点故障，通信也不至于完全中断。
4.1.2 社交网络中的结构中介
在社交网络里，割点可对应连接不同群体的中介人物。其删除可能使原本有联系的圈层变得疏离，影响信息传播路径。
不过，实际社交网络往往较为复杂，很多连接并非单一路径，因此严格意义上的割点未必常见。即便如此，类似“关键中介”的概念仍常被借用来描述结构上的重要位置。
4.2 算法设计
割点检测是图算法中的基础任务之一，在图分解、动态维护和结构优化中都有实际价值。
4.2.1 图分解与维护
在图分解问题中，先识别割点有助于将大图拆分成更易处理的子结构。这样可以分别分析各部分，再整合结果，降低整体复杂度。
在动态图维护中，若边或顶点发生变化，及时更新割点信息可以帮助系统快速判断连通状态是否改变。这对需要实时响应的应用尤为重要。
4.2.2 关键点检测
关键点检测的目标是找出对图结构影响最大的顶点。割点检测正是其中最典型的一类问题。
在编程实现中，这类任务常作为深度优先搜索、连通分量、低点值维护等知识的综合练习。它既考验理解，也考验算法表达能力。
4.3 竞赛与教学
割点因定义明确、算法经典、应用广泛，常出现在离散数学课程和算法竞赛题中，是图论学习中的重点内容之一。
4.3.1 常见题型
常见题型包括：判断一个图中是否存在割点，输出所有割点，统计删除某点后连通分量的变化，以及结合双连通分量进行结构分析。
这类题目通常会与邻接表、深度优先搜索、时间戳和低点数组等知识结合出现，考查学生对图遍历过程的理解。
4.3.2 易错点与理解误区
学习割点时，常见误区包括把高阶顶点误认为割点、忽略“连通分量数量增加”这一判定核心，以及在有向图和无向图中混用概念。
另一个容易出错的地方，是把“删除顶点后图不再完全连通”与“割点”混为一谈。严格来说，割点强调的是连通分量数增加，而不是路径长度变化或局部边数减少。