图的割秩与二分宽度 图的割秩是图论中一个衡量图“可分性”的结构参数，它与图的二分宽度紧密相关。它源于对电路布局、VLSI设计等实际问题的抽象，用于量化将图划分为两个相对平衡部分所需切断的边数。 1. 基本定义：割与割的秩 割 ：对于一个图 \( G = (V, E) \)，一个割是一个边的集合 \( C \subseteq E \)，使得存在一个顶点子集 \( S \subseteq V \)，满足 \( C \) 恰好是那些一个端点在 \( S \) 中、另一个端点在 \( V \setminus S \) 中的边的集合。我们称这个割是由子集 \( S \) 诱导的。 割的秩 ：对于一个由顶点子集 \( S \) 诱导的割 \( C \)，其秩定义为集合 \( S \) 和 \( V \setminus S \) 中顶点数较小者，即 \( \min(|S|, |V \setminus S|) \)。直观上，割的秩衡量了这个划分的“平衡程度”。秩越小，表示划分出的两个部分大小越悬殊。 2. 图的割秩 图的割秩定义为图中所有非空割（即 \( S \) 既不是空集也不是 \( V \) 自身）的秩的最小值。 形式化地： \[ \text{割秩}(G) = \min \{ \min(|S|, |V \setminus S|) : \emptyset \subset S \subset V \} \] 这个参数反映了将图分成两个非空部分时，所能达到的最“不平衡”程度。割秩越小，意味着存在一种方式，只需切断很少的边（具体数量是另一个概念，见下文），就能将图分成一个非常小的部分和一个非常大的部分。 3. 图的二分宽度 与割秩密切相关但侧重点不同的一个概念是 二分宽度 。 二分宽度 ：图的二分宽度定义为，在所有将顶点集 \( V \) 划分为两个子集 \( A \) 和 \( B \)（要求 \( |A| = \lfloor |V|/2 \rfloor \) 且 \( |B| = \lceil |V|/2 \rceil \)，即尽可能平衡的划分）中，连接 \( A \) 和 \( B \) 的边的最小数目。 形式化地： \[ \text{二分宽度}(G) = \min \{ |E(A, B)| : A \subseteq V, |A| = \lfloor n/2 \rfloor, B = V \setminus A \} \] 这里 \( E(A, B) \) 表示一个端点在 \( A \)、另一个端点在 \( B \) 的边的集合。 4. 割秩与二分宽度的关系 割秩和二分宽度都描述了图的“可分离性”，但关注点不同： 割秩 关注的是划分的 平衡性下限 。它告诉你，无论如何划分，较小的那块至少有多大。它是一个关于图结构“脆弱性”的度量——是否存在一个非常小的顶点集，可以通过切断与其余部分的连接而被分离出来。 二分宽度 关注的是在 强制平衡划分 的前提下，需要切断的 边的数量 。它衡量的是将图平分成两半的难度。 对于具有 \( n \) 个顶点的图 \( G \)，存在以下重要关系： \[ \text{二分宽度}(G) \ge \text{割秩}(G) \] 这个不等式成立是因为，二分宽度是在一个非常严格的平衡条件（\( |A| \approx n/2 \)）下最小化边割的大小，而割秩的定义放松了对平衡性的要求（只要求两边非空），因此其最小值对应的边割大小（不一定是最小割的大小，但与该划分相关的边数）为割秩提供了一个下界。实际上，一个具有小割秩的图，其二分宽度也可能很小，因为它容易在某个不平衡点被分开。 5. 计算复杂性与应用 计算复杂性 ：计算一个给定图的精确割秩或二分宽度都是NP-难问题。这意味着没有已知的多项式时间算法能对所有图精确计算出这些参数。在实际中，通常使用近似算法或启发式算法来估计它们。 应用 ：这两个参数在算法设计和分析中非常重要。特别是二分宽度，如果一个图的二分宽度很小，那么许多NP-难问题在该图上可能存在高效的动态规划算法。其思想是，先找到图的一个小的平衡顶点分隔器（由小的二分宽度保证），然后递归地求解子问题，最后合并解。这种方法在布局布线、矩阵计算、图划分等领域有广泛应用。割秩则更多地用于理论分析，作为图结构脆弱性的一个基本度量。