1 基本概念
1.1 图与连通性的回顾
图分离建立在图的基本结构与连通性概念之上。一个图通常由顶点集合与边集合构成，用于描述对象之间的连接关系。在研究分离问题时，首先要明确图是否连通，以及连通性如何随删除操作而改变。
1.1.1 无向图与有向图
无向图中的边不区分方向，适合表示对称关系，例如道路连接或双向联络。有向图中的边带有方向，更适合表示单向传递、依赖或流程关系。对于分离问题而言，无向图常讨论顶点删除或边删除后是否仍保持连通；有向图则更关注强连通性、可达性以及在方向约束下的分割效果。
1.1.2 连通图与非连通图
无向图若任意两点之间都存在路径，则称为连通图；否则称为非连通图。非连通图由多个连通分量组成，各分量内部连通，但分量之间没有边相连。图分离的核心目的，就是研究如何通过移除少量元素，使原本连通的图变成非连通图，或使连通分量的数量增加。
1.2 图分离的定义
图分离指的是通过删除某些顶点、边或两者的组合，使图的连通性被破坏，从而将图分割成两个或更多互不连通的部分。这一过程既可以针对整体图，也可以针对指定顶点对之间的连接关系。
1.2.1 顶点分离
顶点分离是指删除若干顶点及其关联边后，图被拆分为多个部分。若删除一个顶点就能使图不再连通，这个顶点就具有关键分离作用。顶点分离常用于研究网络中的关键节点、枢纽位置以及脆弱结构。
1.2.2 边分离
边分离是指删除若干边后，图的连通性受到破坏。与顶点分离相比，边分离更直接地体现连接通道的中断。某些图即使删除多个顶点仍保持连通，但只要去掉一条关键边，就可能立即发生分裂。
1.2.3 分离后连通分量的变化
图分离之后，原图的连通分量数通常增加。若删除的元素足够少却导致分量数明显上升，说明图在结构上存在较弱的连接环节。通过观察分离前后的分量变化，可以判断图的稳健程度及局部结构的重要性。
1.3 图分离的直观理解
图分离可以被形象地理解为“剪断”图中的连接。某些点或边像桥梁一样维系着两个区域，一旦被移除，原本整体一致的图就会被切开。
1.3.1 “切断”图的结构
从直观上看，分离相当于在图中寻找合适的切口。若图像一张网，分离点或分离边就像网中的薄弱位置，轻轻一断便使结构分开。这个类比有助于理解割点、割边等概念的作用。
1.3.2 图的脆弱点与稳定性
图中的脆弱点通常是那些一旦删除便显著改变全局结构的元素。与之相对，稳定性较高的图往往具有较多冗余连接，即使局部损坏也不会立即失去连通性。图分离研究的一个重要任务，就是识别脆弱点并衡量整体稳定程度。
2 相关术语与类型
2.1 割点与割边
割点和割边是图分离中最基本、最常见的对象。它们分别对应顶点层面的关键分离元素与边层面的关键分离元素。
2.1.1 割点的定义
割点是指删除该顶点及其关联边后，图的连通分量数增加的顶点。换言之，这类顶点承担着连接多个区域的作用，是图结构中的关键节点。
2.1.2 割边的定义
割边又称桥，是指删除该边后，图的连通分量数增加的边。割边说明这条连接是某一部分与另一部分之间的唯一通道，具有明显的结构敏感性。
2.1.3 割点与割边的判定条件
割点和割边的判定通常依赖于图中是否存在替代路径。若某顶点或边不在任何可替代的闭合路径中，并且其去除会破坏连通性，就往往构成割点或割边。在算法上，这类判定常与深度优先搜索中的回溯信息有关。
2.2 割集与割空间
割集是比单个割点或割边更一般的概念，指一组元素共同构成分离作用。割空间则与图的边结构线性化描述相关，常出现在图论的代数表达中。
2.2.1 顶点割集
顶点割集是指删去一组顶点后能够使图分离的顶点集合。若其中任一元素都不可少，则可视为较小规模的关键分离结构。顶点割集在网络保护与节点冗余分析中十分常见。
2.2.2 边割集
边割集是指删去一组边后使图断开的边集合。它描述了连接关系的整体薄弱面，而不局限于单条边。对于多通道系统而言，边割集有助于识别一组同时失效时的风险边界。
2.2.3 最小割集
最小割集是指在保持分离效果的前提下，无法再删去其中任何元素的割集。它强调“不可再缩减”的性质。最小割集往往对应结构上的核心瓶颈，在理论分析和优化设计中都具有重要意义。
2.3 分离对与分离集
分离对与分离集通常用于描述“两个对象之间被切断”的情形，而不一定要求整个图完全非连通。它们更关注指定点对、边对之间的可达性。
2.3.1 点分离对
点分离对是指一对顶点之间存在某种最小顶点删除集合，使它们不再连通。研究点分离对时，常将注意力集中在两个特定端点之间的隔离问题上。
2.3.2 边分离对
边分离对对应于通过删除某些边，使指定两点之间失去连通路径。它在通路控制、备用线路规划等场景中较为实用，便于衡量局部连接的可靠程度。
2.3.3 多重分离结构
当分离不只涉及一个点对或一条边，而是涉及多个区域或多个目标时，就形成多重分离结构。这类结构更复杂，常表现为多个割集叠加、交叉或嵌套，适合描述大规模网络中的层级脆弱性。
3 数学性质
3.1 连通度
连通度是衡量图分离难易程度的重要参数。它反映了图抵抗删除操作的能力，数值越高，通常表示图越不容易被切断。
3.1.1 点连通度
点连通度是使图失去连通性所需删除的最少顶点数。该数值越大，说明图对顶点故障越不敏感。对于高度冗余的图，点连通度往往较高。
3.1.2 边连通度
边连通度是使图失去连通性所需删除的最少边数。它体现了图对边失效的容忍程度。若边连通度较低，则说明存在少量边就能造成结构断裂。
3.1.3 连通度与最小分离规模
连通度本质上刻画了最小分离规模。它将“需要删除多少元素才能使图分离”这一问题数值化，从而为比较不同图的结构稳固性提供了统一标准。
3.2 图的不变性与极值性质
图分离研究中，很多问题关心的是删除后的结构保持程度，以及在极端条件下图能达到何种分离与连通平衡。
3.2.1 删除顶点后的图结构
删除顶点后，图中的某些局部结构可能完全消失，也可能仅改变邻接关系。若删除的是关键顶点，图的模块边界会变得明显；若删除的是普通顶点，则整体结构可能变化不大。
3.2.2 删除边后的图结构
删除边往往比删除顶点更“温和”，但当边位于关键位置时，影响依然显著。图中若存在多条平行通路，则删边后的结构通常仍保持一定完整性；反之，若边本身就是唯一通道，后果就会非常直接。
3.2.3 最小分离与图最优设计
在图的设计问题中，人们常希望在保持高连通性的同时减少资源消耗。最小分离分析能够帮助识别真正必要的连接，并指导在冗余与成本之间取得平衡，这也是图最优设计的重要依据之一。
3.3 与路径和回路的关系
图分离与路径、回路之间有紧密联系。路径提供了连接的基本形式，而回路则往往意味着替代通道和结构冗余。
3.3.1 Menger定理的关联
Menger定理揭示了点对之间的独立路径数与分离集大小之间的对应关系。它说明，若两点之间存在很多彼此独立的路径，则要切断它们通常需要更大的分离集。这一定理是分离理论中的基础结论之一。
3.3.2 独立路径与分离
独立路径越多，图越不容易被小规模删除所破坏。相反，如果两个区域之间只有少量彼此重叠很少的路径，那么这些路径上的关键点或关键边就更容易构成分离结构。
3.3.3 回路中的分离特征
回路通常能提供替代连接，因此回路中的边或顶点往往不容易成为割点或割边。只有当回路与外部结构相接的方式较为单薄时，相关元素才可能在更大范围内表现出分离作用。
4 判定与算法
4.1 割点检测算法
割点检测是图算法中的经典问题，常借助深度优先搜索在较低复杂度内完成。
4.1.1 DFS低点法
DFS低点法通过记录每个顶点在搜索树中的访问顺序及其可回溯到的最早祖先位置，判断某个顶点是否为割点。若某个子树无法通过返祖边回到足够高的位置，则其父节点可能是关键分离点。
4.1.2 Tarjan思想
Tarjan思想强调利用一次深度优先遍历，同时获取多个结构信息，如时间戳、低点值以及回边关系。它使割点、割边等问题可以在统一框架下高效求解，因此具有很强的通用性。
4.1.3 时间复杂度分析
基于DFS的割点检测通常可在与顶点数和边数线性相关的时间内完成，即 O(V+E)。这类算法适合大规模图处理，也体现了图分离判定在工程上的可行性。
4.2 割边检测算法
割边检测同样是经典图问题，核心思路与割点检测类似，但判定对象转向边。
4.2.1 深度优先搜索判定
在深度优先搜索过程中，若某条边连接的子树无法通过其他路径回到祖先，则该边很可能是割边。算法利用搜索树结构与回溯关系，识别唯一通道。
4.2.2 桥的识别方法
桥的识别通常依赖低点值与访问顺序的比较。若某条边所连接的后代部分缺乏替代回路，那么这条边在图中就是桥。该方法直观且高效，是桥检测的标准思路。
4.2.3 算法实现要点
实现时需要注意无向图中边的双向存储、父边排除以及重复访问的处理。若处理不当，容易将树边与返祖边混淆，从而影响判定结果。
4.3 最小割问题
最小割问题研究如何在代价最小的条件下将图分开。它是组合优化中的重要主题，也常与流量模型结合。
4.3.1 经典最大流最小割
最大流最小割定理指出，网络中的最大可行流量等于最小割容量。这一结果把“流的极限”和“切断的最小代价”联系起来，是图分离在优化理论中的代表性应用。
4.3.2 顶点割转化技巧
顶点割问题常可通过拆点等方法转化为边割问题，以便应用最大流算法。此类技巧把顶点删除的约束编码为边容量限制，从而统一到流网络框架中处理。
4.3.3 计算复杂度与应用
最小割问题在一般情形下计算代价较高，但许多特殊图和特定约束下可得到高效算法。它广泛用于网络设计、资源分配、模块划分及可靠性评估等领域。
5 理论扩展
5.1 点分离与边分离的对比
点分离与边分离在对象、影响和算法处理上均有明显区别。
5.1.1 结构影响差异
删除顶点通常会同时移除其所有邻接关系，因此破坏面更广；删除边则只影响单一连接，作用更局部。前者更像切除枢纽，后者更像切断通道。
5.1.2 计算难度差异
从理论上看，点分离和边分离都可以在许多经典模型下有效处理，但具体问题的难度并不完全相同。某些图类中，边分离的判定更直接，而顶点分离常需要额外转化。
5.1.3 应用场景差异
点分离适合分析关键节点、控制中心和故障节点；边分离更适合研究线路、链路或连接通道的可靠性。两者在实际系统中往往共同使用，以获得更全面的脆弱性评估。
5.2 图分解中的分离思想
分离不仅用于判断图是否被切断，也用于将复杂图拆解为更易处理的部分。
5.2.1 块与块树
块是图中较大且不含割点的连通部分。将块及其割点按层次组织起来，可以得到块树这一结构。块树反映了图在割点层面的分解关系，便于研究整体骨架。
5.2.2 分支分解
分支分解是一种把图结构递归拆分的方式，强调通过分离边界来构造层次化表示。它常用于分析图的复杂度、可分解性以及局部子结构之间的联系。
5.2.3 树分解中的分离
树分解将图映射为若干“袋”的组合，并要求相邻袋在结构上满足一定连通条件。分离思想在其中体现为：通过较小的交界部分把全图拆成层级结构，进而简化许多计算问题。
5.3 特殊图中的分离性质
不同类型的图，其分离特征差异明显。某些图几乎不可能被小规模分离，而另一些图则天然具有明显的脆弱点。
5.3.1 树中的分离
树没有回路，因此任意一条边都是割边，除叶子外的很多顶点也可能成为割点。树的分离性质非常明显，几乎每一次删除都可能带来分量增加。
5.3.2 完全图中的分离
完全图中任意两个顶点之间都有直接相连的边，结构高度冗余。要使其分离，通常需要删除较多顶点或边，因此它具有很高的连通度和较强的稳定性。
5.3.3 二分图中的分离
二分图的顶点可分为两部分，边只连接不同部分之间的顶点。其分离性质与两侧的连接模式密切相关，尤其在稀疏二分图中，少量关键点或边就可能形成明显的分离结构。
6 应用
6.1 通信网络可靠性
通信网络常被抽象为图模型，图分离理论可用于分析链路中断、节点失效和系统恢复能力。
6.1.1 故障容忍分析
通过识别割点、割边和最小割集，可以判断网络在单点或多点故障下的脆弱程度。这有助于评估系统是否具备基本容错能力。
6.1.2 冗余路径设计
为了降低分离风险，网络设计通常会引入多条备用路径。冗余路径越充分，系统越不容易因为局部失效而被切断。
6.1.3 网络鲁棒性评估
鲁棒性评估关注网络面对攻击、故障或拥塞时的持续连通能力。图分离提供了直接的结构指标，能够帮助定量衡量网络的稳健程度。
6.2 交通与电路网络
交通系统和电路系统都具有明显的图结构特征，分离分析在这些领域具有很强的现实意义。
6.2.1 关键节点识别
在交通网络中，某些枢纽站点或交叉点一旦失效，可能导致大范围不便；在电路网络中，关键元件的失效也会影响整条线路。图分离可用于识别这些核心位置。
6.2.2 线路中断分析
线路中断本质上对应边分离问题。通过分析哪些线路属于桥或接近桥的结构，可以提前发现容易引发系统分裂的薄弱环节。
6.2.3 系统冗余规划
在规划阶段加入冗余线路、备用通道或替代连接，可以有效降低分离风险。图分离理论能够为这些规划提供形式化依据，使设计更合理。
6.3 算法与数据结构
图分离不仅是理论问题，也直接影响若干算法与数据结构的设计。
6.3.1 图的结构优化
许多图算法会先识别并处理割点、割边或割集，再对剩余部分进行优化。这样可以减少问题规模，并将复杂图拆成更简单的子结构。
6.3.2 子图提取与模块化
分离结构有助于提取具有内部紧密连接、外部连接较少的子图模块。模块化处理便于并行计算、局部维护以及分层分析。
6.3.3 依赖关系分析
在依赖图中，图分离可用来判断某些任务、对象或状态之间是否存在单点依赖。若某一元素是分离点，就意味着它在依赖链中具有关键地位，必须加以关注。