1 基本概念
割问题是图论与组合优化中的基础主题，核心思想是将图或网络中的顶点集合分成若干部分，并考察跨越这些部分的边、容量或代价。它既可以作为一个抽象的数学模型，也可以对应通信、运输、分组和结构分解等实际任务。不同场景下，割的目标可能是最小化被切断的连接代价，也可能是最大化两部分之间的分离程度。
1.1 割的定义
在无向图或有向图中，割通常指将顶点集划分为两个互不相交且并集为全集的子集。若以集合表示，可将顶点集记为 \(V\)，并把割写作 \((S, V\\setminus S)\)，其中 \(S\) 是顶点集的一个非空真子集。凡是两端分别落在两个部分中的边，便称为跨割边或割边。
在网络语境中，割不仅描述分组方式，还隐含着对连接关系的“切断”效果。因此，割的研究往往与连通性、流量、容量和路径结构紧密相关。
1.2 割的类型
割可以按划分部分的数量、是否指定源汇点、是否要求平衡性等标准进行分类。不同类型的割对应不同的优化目标，也决定了所使用的算法和理论工具。
1.2.1 二分割
二分割是最常见的形式，即将顶点集分为两个部分。它的目标通常是寻找一条“最省代价”的分界线，使得跨越两部分的边权总和尽可能小。二分割在图像分割、聚类和网络分区中尤为常见。
1.2.2 s-t割
s-t割是指在图中指定两个特殊顶点 \(s\) 和 \(t\)，要求划分后的两个部分分别包含 \(s\) 与 \(t\)。这类问题常用于研究从源点到汇点的流动能力，并与最大流问题形成经典对应关系。
1.2.3 多重割
多重割涉及三个或更多指定终端点或终端集合，目标是在同一图中同时分离多个对象。与二分割相比，多重割通常更复杂，常出现在多方通信隔离、群体分区和多终端网络设计中。
1.3 割值与容量
割值是衡量一个割优劣的核心指标，通常定义为跨越割的边权之和或容量总和。若图中边带有权重，则割值可理解为被切断连接的总成本；若边具有容量，则割值常用于表示该分割所允许通过的最大“通行量”。
在流网络中，割值还具有明显的物理或工程含义。例如，它可以表示管道、线路或链路中被隔离部分所承受的总输送能力。
1.4 割问题的建模方式
割问题的建模通常以图、网络或超图为基础。最常见的方法是用顶点表示对象，用边表示对象之间的联系，再通过定义权重、容量或惩罚函数来反映实际需求。若目标是分离特定节点，可加入源汇约束；若目标是保持群组结构，则可加入平衡条件或连通性要求。
在优化建模中，割问题也常被写成整数规划、线性规划或图能量最小化形式。这样可以把离散分割问题转化为可计算的数学模型，为算法设计提供统一框架。
2 图论中的割问题
图论中的割问题强调结构性质与连通性破坏之间的关系。通过分析删除哪些边或顶点会导致图的分裂，可以深入理解图的脆弱性、冗余性以及局部结构的稳定程度。
2.1 边割与点割
边割是指删除一组边后使图失去连通性，点割则是删除一组顶点后导致图分裂。两者分别对应边的承载能力和顶点的结构枢纽作用，是图连通性研究中的两个基本方向。
2.1.1 边连通性
边连通性衡量图在多少条边被删除后仍能保持连通。若一个图的边连通性较高，说明它具有较强的边冗余，少量边的失效不至于导致整体断开。该概念广泛用于网络可靠性分析。
2.1.2 点连通性
点连通性考察删除若干顶点后图是否会分裂。一个点连通性高的图通常具有较强的抗节点失效能力。与边连通性相比，点连通性更能反映关键节点的作用，因为某些顶点可能承担桥梁式功能。
2.2 最小割
最小割指在满足特定条件下，使割值最小的割。它是割问题中最核心的优化目标之一，具有很强的理论意义和算法价值。根据约束不同，最小割可以是全局性的，也可以是局部性的。
2.2.1 全局最小割
全局最小割不预先指定源点和汇点，而是在整个图中寻找使图分裂代价最低的割。它反映的是图最脆弱的分离位置，常用于网络鲁棒性评估和最弱环节定位。
2.2.2 局部最小割
局部最小割通常限定某些特殊顶点、区域或标签，要求在这些局部约束下寻找代价最低的分割。它在特定子网络的隔离、社区边界识别和局部结构提取中较为常见。
2.3 割集与割边
割集是指能够使图不连通的一组边或顶点集合。若讨论边割，则这些边构成一个边割集；若讨论点割，则对应顶点割集。割边是割集中的单条边，通常指删除后会直接使连通分量增加的边。
在实际分析中，识别割集有助于找出网络中的关键薄弱点，也有助于确定哪些连接在整体结构中不可或缺。
2.4 割与连通分量
一个割的作用往往体现在改变连通分量的数量上。删除跨割连接后，原本连通的图可能被拆分成多个连通分量。连通分量的变化程度，直接反映了割的结构破坏能力。
从分解角度看，割也常被用于将大图拆成较小、相对独立的部分，以便于后续分析、并行处理或局部优化。
3 经典理论结果
割问题之所以重要，很大程度上源于一系列经典定理建立了它与流、路径和连通性的深层联系。这些结果不仅统一了许多表面上不同的问题，也为算法设计提供了理论支撑。
3.1 最大流-最小割定理
最大流-最小割定理是网络优化中的核心定理之一，说明源点到汇点的最大可行流量，恰好等于分隔源汇的最小割容量。它把“通过多少”与“切断多少”联系起来，形成极为优雅的对偶关系。
3.1.1 定理表述
在容量网络中，从源点 \(s\) 到汇点 \(t\) 的最大流值，等于所有 s-t 割中容量最小者的值。换言之，网络中可以从源到汇输送的最大总量，受到最小瓶颈割的严格限制。
3.1.2 证明思路
证明通常依赖流守恒、增广路径与残量网络等概念。直观上，若不存在可继续增广的路径，则剩余网络中必然形成一个将源与汇分开的割；该割的容量正好与当前最大流相等。由此即可建立两者一致性。
3.2 Menger定理与割
Menger定理揭示了两点之间互不相交路径的数量与它们之间最小割规模之间的对应关系。它说明，能找到多少条彼此独立的路径，受到图中最小分离结构的严格限制。
该定理在连通性分析、网络容错和路径冗余设计中具有基础地位，也常被视为割理论与路径理论的桥梁。
3.3 割的对偶关系
在许多优化模型中，割与流、路径、覆盖等对象之间存在明显对偶关系。割问题往往描述“分离成本”，而其对偶问题则描述“传输能力”或“可行路径数量”。这种对偶性使得原本复杂的离散问题可以借助更容易处理的形式求解。
在更抽象的层面，割还常与线性规划对偶、图的对偶结构以及组合最优化中的互补松弛条件联系在一起。
3.4 割函数的性质
割函数通常具有对称性、次模性或近似次模性等重要性质。对称性意味着将两侧互换后割值不变；次模性则反映出一种“边际收益递减”的结构特征。正因为这些性质，割函数在理论分析和算法设计中都十分有用。
这些性质也解释了为什么很多与割相关的问题可以通过松弛、分解或贪心策略获得较好结果。
4 算法与计算复杂性
割问题既有可高效求解的经典形式，也有计算上相当困难的变体。算法研究通常围绕精确求解、近似求解以及大规模实例处理三条主线展开。
4.1 确定性算法
确定性算法在给定输入下产生固定输出，适合研究最小割、最大流和全局割等基础问题。许多经典算法已成为算法教材中的标准内容。
4.1.1 Ford-Fulkerson算法
Ford-Fulkerson算法通过不断寻找增广路径并提高流值来逼近最大流。其思想简单直观，核心在于利用残量网络中的可扩展路径逐步改进当前解。对于整数容量网络，它可在适当条件下终止并得到最优解。
4.1.2 Edmonds-Karp算法
Edmonds-Karp算法是Ford-Fulkerson方法的一个具体实现，使用最短增广路作为选择准则。由于每次增广都沿最少边数路径进行，它具有明确的多项式时间复杂度，因而更适合理论分析和教学使用。
4.1.3 Stoer-Wagner算法
Stoer-Wagner算法是求无向图全局最小割的经典确定性算法。它通过一系列“收缩”和“紧密度”构造，逐步找到候选割并更新最优值。该算法在无向带权图上表现稳定，是全局最小割计算的重要方法。
4.2 近似算法
对于许多困难变体，精确求解代价过高，因此常采用近似算法，在可接受时间内获得接近最优的结果。近似比为评价这类算法的重要指标。
4.2.1 2-近似与界限
2-近似算法意味着所得解的代价最多是最优解的两倍。对某些割问题而言，这一界限既是可实现的，也是理论上较易分析的。它常出现在二分割、聚类和若干网络分割模型中。
4.2.2 随机化算法
随机化算法利用随机选择、概率分析或随机采样提升求解效率或解的质量。在割问题中，随机化常用于构造近似解、估计割值或提高大规模实例的计算可行性。某些情况下，随机化还可帮助突破确定性算法的局部最优限制。
4.3 复杂性分类
割问题的复杂性差异很大，取决于图类型、目标函数和附加约束。部分问题可在多项式时间内求解，而另一些则被证明具有NP困难性。
4.3.1 多项式时间可解问题
典型的多项式时间可解问题包括最大流、s-t最小割以及无向图全局最小割等。它们之所以可高效求解，往往得益于结构较强、对偶关系清晰或可利用网络流工具。
4.3.2 NP困难的割问题变体
当割问题加入平衡约束、多终端约束、容量限制或复杂的组合条件后，往往会变得NP困难。此时通常无法期待在一般情形下得到快速精确算法，因而需要借助近似、启发式或参数化方法。
4.4 割问题的参数化算法
参数化算法以某个结构参数作为复杂性度量，例如割大小、终端数、树宽或反馈边集规模。若参数较小，即使整体问题很难，也可能在实践中获得可接受的运行时间。
这种方法特别适合“难但稀疏”或“难但局部结构简单”的实例，在理论计算机科学和实际优化中都具有重要价值。
5 常见变体
割问题在不同应用背景下形成了多种变体。这些变体往往通过增加平衡条件、多个终端、权重或约束来适应现实需求。
5.1 全局割问题
全局割问题关注整个图中最容易被分开的地方，不预设源点与汇点。它常被用于评估网络总体脆弱性，并寻找最小的结构瓶颈。
5.2 平衡割问题
平衡割要求分割后的两部分在规模、权重或其他指标上尽量接近，避免出现一边过大、一边过小的极端情况。它特别适合聚类、分区和负载均衡类任务。
5.2.1 最小平衡割
最小平衡割在满足平衡条件的前提下，使割代价最小。由于加入了平衡约束，该问题通常比普通最小割更难，但也更符合实际分组需求。
5.2.2 谱割
谱割利用图拉普拉斯矩阵的特征向量构造分割方案，是平衡割的重要近似思路。它通过连续优化近似离散划分，在数据聚类和图像处理里使用频繁。
5.3 多割问题
多割问题要求同时分离多个终端对或终端集合。随着终端数量增加，问题复杂度迅速上升，但它在多方通信隔离、资源分区和层次聚类中很有意义。
5.4 超图割问题
超图割将边推广为连接多个顶点的超边，因此可表示更复杂的群组关系。对应的割问题不再局限于二元连接，而要考虑超边跨越多个部分时的代价分配。
5.5 带权割问题
带权割把顶点或边赋予权重，使得割值不仅反映连接数量，还体现连接强弱、重要性或成本。它更贴近实际场景，也更便于表达异质网络中的差异。
5.6 约束割问题
约束割问题是在基本割模型上附加额外条件，如连通性要求、容量上限、终端必须分离等。此类模型灵活性高，但也更容易导致求解难度增加。
6 数学模型与优化方法
割问题常通过优化模型来描述，随后再借助整数规划、连续松弛或分解技术进行求解。不同方法之间可以相互转换，也可以组合使用。
6.1 整数规划模型
整数规划是表达割问题的标准工具之一。它通过二元变量表示顶点是否属于某一部分，并用线性约束和目标函数刻画割代价。
6.1.1 0-1变量表示
在0-1模型中，每个顶点或边对应一个布尔变量，变量取值表示其所属分区。跨分区的边会在目标函数中被计入，从而把割的优化转化为整数最优化问题。
6.1.2 线性松弛
线性松弛通过放宽整数约束，使变量可取连续值，以便使用线性规划求解。虽然松弛解通常不是最终可行割，但它可为下界估计、近似算法和后续舍入提供依据。
6.2 凸松弛与半定规划
凸松弛将原本离散的割问题嵌入连续凸优化框架中，常见形式包括二次规划和半定规划。半定规划在某些图割与聚类问题中尤其重要，因为它能较好保留原问题的结构信息。
6.3 拉格朗日松弛
拉格朗日松弛通过把部分难处理约束并入目标函数，引入乘子进行协调。这样一来，复杂问题有时可分解为若干更容易求解的子问题，适合大规模优化和分布式计算场景。
6.4 割平面方法
割平面方法并不是“割问题”本身，而是一种用于求解整数规划的技术。它通过不断识别违反约束的解，并加入新的切平面，把连续松弛逐步逼近整数最优解。
6.5 启发式与元启发式方法
对于难以精确求解的大型实例，启发式方法常用于快速构造可行解，元启发式方法则通过遗传算法、模拟退火、局部搜索等机制提升全局探索能力。这些方法通常不保证最优，但在工程中具有较高实用性。
7 应用领域
割问题的应用范围非常广，几乎涉及所有需要“分开”“隔离”“分区”或“寻求瓶颈”的场景。它在理论上是抽象模型，在实践中则是有效工具。
7.1 网络流与通信网络
在通信网络中，割用于分析链路瓶颈、设计容错结构以及评估系统吞吐能力。通过找出最小割，可以识别网络中最容易造成拥塞或中断的关键位置。
7.2 图像分割
图像分割把像素或区域看作图中的顶点，把相似性或邻接关系表示为边，随后通过割将图划分为不同对象区域。这种方法在医学影像、目标识别和场景理解中非常常见。
7.2.1 二值分割
二值分割将图像划分为前景和背景两类，是最基础的图割应用之一。它通常依赖像素强度、边缘信息和先验约束来构造能量函数。
7.2.2 能量最小化
许多图像分割问题可写成能量最小化模型，其中数据项描述像素与标签的匹配程度，平滑项描述邻近像素的一致性。割问题提供了将这类能量转化为可计算分割的有效途径。
7.3 社交网络分析
在社交网络中，割可用于识别社区边界、分离弱联系结构以及分析群体之间的连接强度。它还能帮助研究网络中的桥接节点和跨群组传播路径。
7.4 生物信息学
在生物网络分析里，割问题可用于蛋白质相互作用网络、基因调控网络和功能模块识别。通过寻找合适的分割，可以把复杂系统划分为若干功能相对一致的子模块。
7.5 电路与系统设计
在电路布局、系统分层和模块化设计中，割可用于减少跨模块连线、降低通信延迟并提高可维护性。它对于芯片分区和系统集成具有现实意义。
7.6 物流与供应链网络
在物流网络中，割问题可帮助识别运输瓶颈、规划仓储分区以及优化供应链结构。通过合理分割网络，可以在成本、时效与鲁棒性之间取得平衡。
8 相关概念与拓展
割问题与图论中的多个分支彼此交织，形成了丰富的理论与方法网络。理解这些相关概念，有助于把割问题放在更广阔的数学背景中考察。
8.1 最小割与最大流的联系
最小割与最大流之间的联系是割理论最著名的成果之一。一个描述“切断能力”，另一个描述“运输能力”，二者在数学上恰好相等，这种对应关系是网络优化中的基本范式。
8.2 割与谱图理论
谱图理论通过研究图拉普拉斯矩阵和邻接矩阵的特征值，揭示图结构与割结构之间的联系。某些特征值可以反映图的连通性和可分性，因此在谱聚类与谱割中应用广泛。
8.3 割与子模函数
许多割函数具有子模性，这意味着它们在集合扩张时表现出递减边际效应。子模函数是离散优化中的重要类函数，与贪心算法、凸性推广和集合函数优化密切相关。
8.4 割与图聚类
图聚类旨在把相似或联系紧密的顶点聚在一起，而割则提供了衡量“分开是否合适”的标准。聚类与割在目标上往往互为镜像：一个强调内部紧密，一个强调外部分离。
8.5 割问题中的典型实例
典型实例包括电信网络中的链路分离、社交图中的社区切分、图像中的前景背景分割以及运输网络中的瓶颈识别。它们共同体现了割问题从抽象结构到具体任务的可迁移性。
9 研究进展与发展方向
割问题的研究已经形成较为成熟的理论体系，但随着数据规模增大、网络结构复杂化以及应用场景多样化，新的算法需求仍在持续出现。
9.1 经典成果回顾
早期研究主要建立了最大流-最小割定理、Menger定理和若干基础算法，这些结果奠定了割问题的理论骨架。随后，针对全局最小割、平衡割和多割等方向，又发展出大量精细化方法。
9.2 现代算法框架
现代研究更强调结合随机化、近似、松弛和分解思想的复合框架。与此同时，半定规划、谱方法与参数化算法也不断扩展割问题的可解范围，使其能适应更加复杂的实例。
9.3 大规模图上的计算挑战
面对百万级甚至更大规模图，内存占用、并行效率和数值稳定性成为主要挑战。如何在保持较好解质量的同时降低计算成本，是当前研究中的重要问题。
9.4 未来应用场景
随着复杂网络、智能系统和大规模数据分析的发展，割问题仍将在模式识别、网络安全、资源调度和系统分解中发挥作用。未来的趋势可能更偏向于可扩展算法、在线处理以及与机器学习方法的结合。