3.1 图论地基：最小割、最短路、斯坦纳树

3.1 图论地基：最小割、最短路、斯坦纳树

本节摘要：物理实现反复调用的三个图论原语——最小割（划分问题的理论核心）、最短路（布线的路径骨架）、斯坦纳树（线长估计与树形布线的下界工具）。本节讲清每个问题的形式化定义、代表算法与复杂度数字，并指出 EDA 使用它们时的特殊变形。这是本章的数学工具箱，之后六节处处取件。

切一刀的学问：最小割

把一张图切成两块、使跨块边权和最小——这就是最小割问题，它是 3.3 节电路划分的理论心脏。它的第一层惊喜是对偶定理：图中两点间的最大流等于它们之间的最小割容量。这一定理把看似组合的"找最优切法"变成了多项式可解的网络流问题。第二层惊喜是复杂度的台阶差：一般图的最小割有近线性时间算法（Stoer-Wagner 算法，O(VE) 加对数因子），而带割平衡约束的最小割（划分真正需要的版本）立刻变成 NP 难。EDA 工程师对这对台阶的感受是具体的：无约束割可以在百万节点图上秒级求解，一旦加上"两块大小都必须在 45% 到 55% 之间"的平衡约束，就只能退到启发式（FM 算法）或指数精确算法（小规模分支定界）。

最大流算法的演进值得记三个坐标点：Ford-Fulkerson 增广路框架（每次增广一条可行路径，伪多项式复杂度）；Dinic 分层网络算法（O(V²E)，至今是多数场景的实用主力）；预流推进族（HIPR 等实现，稠密图上更快）。使用时还有两个 EDA 特有的变形：一是多路割（切成 k 块，NP 难，工程用递归二分近似）；二是容量含义的转译——划分问题里跨块边容量不是物理带宽，而是"切割代价"，两块之间的连线条数直接决定后续布线的拥塞与延迟。

找一条路：最短路及其加速

布线的每一根线都是图上的路径，最短路算法因此是布线引擎的心脏。三个经典算法覆盖了全部场景。Dijkstra 算法：非负边权下的标准解，二叉堆实现 O((V+E) log V)，是大多数场景的默认选择。A* 搜索：在 Dijkstra 基础上给每个节点加一个"到终点的乐观估计"（曼哈顿距离），搜索直接朝目标方向展开——布线场景里目标坐标已知，曼哈顿距离恰好是曼哈顿布线下的下界，A* 实测能减少一两个数量级的展开节点数，是布线器内嵌最短路的标准形态。Bellman-Ford：容忍负权边，O(VE)，EDA 里几乎不用，但时序分析的某些差分约束建模会借它的思想。

EDA 的变形重点在图怎么建。布线图不是抽象图而是网格图：每个金属层切成轨道，轨道交叉点为节点，相邻节点间的边带方向与层信息。一张 14 纳米块级设计的布线网格，节点数可达 10 的 9 次方量级——这意味着最短路不是"调一个库函数"，而是要在内存放不下的网格上做高效搜索：分层寻址、按需扩展、位压缩的距离数组都是工程必需。这个变形让"教科书复杂度"与"实际耗时"差出几个数量级，也是 3.7 节协商式布线存在的直接原因——单次最短路够快了，但百万条线网的次序与冲突需要更高层的博弈机制。

一棵树的下界：斯坦纳树

一个网（net）往往有 3 个以上引脚，把所有引脚连起来的最短树形结构不是最小生成树——允许添加中间点（斯坦纳点）通常更短。直角坐标下的矩形斯坦纳树（RST）问题：给定平面上的引脚集，允许引入额外点，求总长最小的直角树。精确解 NP 难，但有个漂亮的近似结构：Hanan 网格定理保证存在一个最优解，其全部斯坦纳点都落在过引脚点的水平垂直线交点上，搜索空间因此从连续平面缩到有限网格。工程上最常用的是 1.5 倍近似算法（基于最小生成树的孪生边修正），保证解长不超过最优的 1.5 倍、期望约 1.1 倍出头，线性到近线性时间。

斯坦纳树在 EDA 里的角色有三重：布线前的线长估计（布局阶段的线长目标函数常取矩形斯坦纳树长，比包围盒周长准、比真布线快）；时钟树与时钟网的综合骨架（3.6 节的偏差约束会叠加在树结构上）；以及全局布线的拓扑生成（先定树形拓扑，再逐段分配几何路径）。三重角色的共同点是"结构先于几何"——先用树论定拓扑骨架，再用最短路填几何细节，层次拆分正是大规模布线可解的原因。

从原语到引擎的距离

把三个原语放进真实工具，还需要一层"调度学"。单条线的最短路再快，百万条线也不能各自为政——先后次序、拥塞分摊、时序优先级都需要外层机制，这是 3.7 节协商式布线的主题。单次割再准，千万单元也要先划分出规模合适的子问题，这是 3.3 节的分层框架。斯坦纳树再短，也要服从制造规则里的间距与绕障约束，这是 3.7 节详细布线的规则感知扩展。原语提供正确性与复杂度的底座，引擎设计解决规模、次序与冲突——这对区分贯穿本章余下各节，读的时候可以随时回头对照：每节提出的算法，究竟是在改进原语，还是在设计调度。

补一个直观例子把三个原语串起来：一个含 4 个触发器与 12 个门的小模块要切到两块 FPGA 上。划分用最小割语言描述目标（跨块连线最少、两块均衡）；切完之后每条跨块连线要选引脚与走线，用最短路算出每条线的候选路径长度；而模块内部每个多位信号的引脚集合，先用斯坦纳树估出树长作为线长下界，才能公平地决定哪些信号值得留在同侧。三个原语在同一个小问题上各司其职——这就是"工具箱"的含义。

本节要点回顾

• 最小割对偶：最大流等于最小割，无约束版近线性可解；加平衡约束立刻 NP 难，只能启发式。
• 最短路三件：Dijkstra 是默认，A* 靠曼哈顿下界在布线网格上省一到两个数量级展开。
• 网格规模：先进节点块级布线网格节点数可达 10 的 9 次方，复杂度理论与工程耗时差距巨大。
• 斯坦纳树：NP 难但有 1.5 倍近似与 Hanan 网格缩域，是线长估计与时钟树骨架。
• 结构先于几何：树论定拓扑、最短路填细节的层次拆分，是大规模布线可解的根本原因。
• 原语与引擎之分：原语保正确与复杂度下限，调度设计解决次序与冲突——本章余节的读法地图。