图建模案例集：这个问题其实是图问题

从 Art. 0 的全景图出发，我们走了四段弧线。Part 1”探”（Art. 1-5）：用 BFS/DFS 看清结构，用连通分量、拓扑排序、欧拉/哈密顿、树算法理解图的骨架。Part 2”量”（Art. 6-10）：用最短路径度量距离，用中心性排名节点，用社区发现揭示群体，用相似度/同构比较图，用团/密子图找密集核心。Part 3”优”（Art. 11-15）：用 MST 构建最小骨架，用网络流分配资源，用匹配对齐双方，用着色分配资源，用近似算法面对 NP-hard。Part 4”建模”（Art. 16-18）：用随机图模型理解真实网络的统计规律，用概率图模型做不确定性推断，用图嵌入/GNN 把图结构送进机器学习。

18 篇文章，19 个工具。我们一直在做一件事：拿到一张图，在上面运行算法。

但在真实世界中，你遇到的问题不会自称”我是图问题”。编译器工程师看到的是”变量冲突”，推荐系统工程师看到的是”用户偏好”，生物学家看到的是”蛋白质交互”，物流经理看到的是”配送路线”。识别出”这个问题其实是图问题”——这才是最关键的一步。

没有这个能力：

• 你拥有 19 个精良的工具，但不知道何时拿出哪一个
• 你看到一个陌生问题，无法将它映射到已有的算法框架
• 你错过了跨领域的联系——编译器的寄存器分配和无线频率分配其实是同一个图着色问题

本文是整条路径的终点站。我们反过来——从真实问题出发，识别其中的图结构，映射到前 18 篇文章的工具。每个案例统一格式：真实问题 → 建模为什么图 → 对应哪个图问题 → 用什么算法。

算法范式：本文是建模案例集，综合运用全路径的所有范式——BFS/DFS 探索、最短路径松弛、贪心、分治、DP、增广路、LP 松弛等。

总览：领域-算法映射

在逐个领域展开之前，先看全景。下面这张图展示了 8 个应用领域如何映射到我们学过的图工具。

同一个工具反复出现：最短路径同时服务于编译器数据流分析和交通导航；图着色同时服务于寄存器分配和频率规划；社区发现同时服务于推荐系统和蛋白质网络。这就是图的力量——它是跨领域的通用建模语言。

下面这个交互式索引表覆盖了全部 8 个领域的 30+ 个具体问题。点击领域名称展开，可以看到每个问题的图建模方式和对应算法。

应用领域点击展开 → 查看具体问题、图建模、对应算法

⚙编译器与程序分析5 个问题▼

🎯推荐系统4 个问题▼

🔬因果推断3 个问题▼

📝自然语言处理3 个问题▼

🧬生物信息学4 个问题▼

💻芯片设计 (VLSI)3 个问题▼

🚛交通与物流4 个问题▼

👥社交网络4 个问题▼

共 8 个领域、30+ 个问题，覆盖 Art. 0-18 全部工具

接下来，我们逐个领域深入。

案例 1：编译器与程序分析

编译器是”图算法的隐形大客户”。几乎每个编译优化 pass 都在某种图上运行，只是它们不叫”图算法”——它们叫”数据流分析”、“支配树构造”、“寄存器分配”。

控制流图 (CFG) → 可达性分析

真实问题：编译器需要知道”从函数入口出发，哪些代码块可能被执行”——这决定了死代码消除（dead code elimination）的范围。

建模：将程序的基本块（basic block，一段没有分支的连续指令）作为节点，条件跳转和无条件跳转作为有向边。得到的就是控制流图 (Control Flow Graph, CFG)。

对应图问题：从 Entry 节点出发的可达性分析——本质就是 Art. 1 的 BFS/DFS。所有不可达的基本块就是死代码，可以安全删除。

SSA 支配树 → 树上算法

真实问题：在 SSA（Static Single Assignment）形式中，需要计算”如果删除节点 B，是否所有从 Entry 到 C 的路径都断了”——这就是支配关系（dominance）。

建模：支配关系构成一棵支配树（dominator tree）。节点 A 支配节点 B 当且仅当从 Entry 到 B 的每条路径都经过 A。

对应图问题：支配树上的 LCA（最近公共祖先）查询、子树遍历等。支配边界（dominance frontier）的计算决定了 SSA $\phi$-函数的插入位置。Lengauer-Tarjan 算法在 $O(n \cdot \alpha(n))$ 时间内构建支配树。

数据流分析 → 迭代松弛

真实问题：活跃变量分析（liveness analysis）需要知道”变量 $x$ 在程序的哪些位置是活跃的”——它在某处被定义，在后面的某处被使用，中间都是活跃的。

建模：定义-使用链（def-use chain）在 CFG 上形成一个数据流方程组。每个基本块有 $\text{gen}$（新定义的变量）和 $\text{kill}$（被覆盖的变量）集合，然后在 CFG 上反向传播。

对应图问题：这是 Art. 6 介绍的迭代到不动点范式的变体。Bellman-Ford 风格的迭代松弛不只用于最短路径——任何满足格（lattice）结构的数据流方程都可以用相同范式求解。活跃变量、可用表达式（available expressions）、常量传播（constant propagation）都是数据流分析的实例。

寄存器分配 → 图着色

真实问题：CPU 只有有限个寄存器（x86-64 有 16 个通用寄存器）。如果两个变量同时活跃（即生命期重叠），它们不能分配到同一个寄存器。

建模：构建干涉图（interference graph）：变量 = 节点，如果两个变量的生命期重叠，则连一条边。$k$ 个寄存器 = $k$ 种颜色。

对应图问题：这就是 Art. 14 的图着色问题。Chaitin (1982) 首次将寄存器分配形式化为图着色。GCC 和 LLVM 都使用基于图着色的寄存器分配器，核心是 DSatur/贪心着色 + spill（当颜色不够时，把某些变量”溢出”到内存）。

算子融合 → 拓扑排序 + 关键路径

真实问题：深度学习编译器（TVM、XLA、TensorRT）需要决定”哪些算子可以融合成一个 kernel”以减少内存读写，以及”按什么顺序执行这些 kernel”。

建模：计算图是一个 DAG——算子 = 节点，数据依赖 = 有向边。

对应图问题：Art. 3 的拓扑排序决定执行顺序。DAG 上的关键路径（最长路径）决定了整个计算的最短完成时间——这就是 pipeline 延迟的下界。可融合的算子对应 DAG 中的链结构（无分叉的连续节点序列）。

案例 2：推荐系统

推荐系统的核心数据结构——用户与物品的交互记录——天然就是一张二部图。

协同过滤 → 二部图链接预测

真实问题：用户 A 看了电影 1、2、3，用户 B 看了电影 1、2、4。要不要给用户 A 推荐电影 4？

建模：用户和物品是两个节点集，评分/交互是边，权重可以是评分值。这就是一张加权二部图。

对应图问题：推荐 = 预测二部图中缺失的边。经典的协同过滤方法本质上是计算二部图中节点的相似度（Art. 9 的 Jaccard 相似度、余弦相似度）。更现代的方法使用 Art. 18 的图嵌入（如 LightGCN）将用户和物品映射到向量空间，然后用向量内积预测边的存在性。

社交影响力 → 中心性 + 社区

真实问题：在社交电商（如小红书、TikTok Shop）中，谁是”关键意见领袖”（KOL）？如何识别用户群体以便精准推荐？

建模：用户之间的关注/互动关系构成社交图。

对应图问题：KOL 识别 = Art. 7 的 PageRank / 介数中心性。用户分群 = Art. 8 的社区发现（Louvain/Leiden）。工业级推荐系统（如 Pinterest 的 PinSage）直接在这张异构图上跑 GNN（Art. 18），同时利用图结构和内容特征。

案例 3：因果推断

因果推断是统计学和机器学习中最深刻的问题之一：观测到的相关性不等于因果性。Pearl 的因果框架用一个工具彻底改变了这个领域——DAG。

因果图 → d-separation

真实问题：观测数据显示”吸烟和肺癌相关”。但如果存在共同原因（如基因同时影响吸烟倾向和癌症风险），简单的统计相关性可能产生虚假因果关系（spurious correlation）。如何从观测数据中识别真正的因果效应？

建模：Pearl 的因果图：变量 = 节点，因果关系 = 有向边。$A \to B$ 表示”干预 A 会改变 B 的分布”。整个因果结构是一个 DAG。

对应图问题：这就是 Art. 17 的 d-separation。给定因果 DAG，d-separation 算法判断”在条件化（controlling for）某些变量后，X 和 Y 是否统计独立”。这是纯粹的图结构问题——在 DAG 上检查是否存在”打开的路径”。

干预 vs 观察 → DAG 变换

真实问题：Pearl 的 $do$-calculus 区分”观察到 X=x”和”干预使 X=x”。$P(Y | do(X=x))$（干预）和 $P(Y | X=x)$（观察）在存在混杂变量时完全不同。

建模：干预 $do(X=x)$ 在图上的操作是删除所有指向 X 的入边——因为干预打断了 X 的自然原因。得到一个新的 DAG（mutilated graph）。

对应图问题：后门准则（backdoor criterion）的验证 = 在原始 DAG 上检查 d-separation；前门准则（frontdoor criterion）需要识别中介变量路径。这些都是 DAG 上的图搜索问题，用 Art. 1 的 BFS/DFS 和 Art. 3 的拓扑排序实现。

核心洞察：因果推断表面上是统计问题，但 Pearl 证明了一个惊人的结果——因果效应的可识别性完全由 DAG 的图结构决定。不需要知道任何数值参数，只需要图的拓扑结构就能判断某个因果效应是否可以从观测数据中估计。

案例 4：自然语言处理

语言结构天然具有图的形态：词之间的语法依存关系形成树，概念之间的语义关系形成知识图谱。

依存句法树 → 树上算法

真实问题：理解”The cat sat on the mat”的句法结构——“sat”是句子的核心谓语，“cat”是它的主语，“mat”是介词”on”的宾语。

建模：每个词是一个节点，语法依存关系是一条有向边（从 head 指向 dependent）。句子的依存结构恰好是一棵有根树——根节点是谓语动词。

对应图问题：句法分析的解码算法本质是在完全有向图上找最小（大）权有根树（maximum spanning arborescence），这是 Edmonds/Chu-Liu 算法——Art. 5 中树算法的推广。解析完成后，在依存树上做子树提取、路径查询（两个词之间的句法关系 = 树上路径）等操作。

知识图谱 → 链接预测 + 图嵌入

真实问题：知识图谱（如 Wikidata、Google Knowledge Graph）存储”爱因斯坦-出生于-德国”这样的三元组 $(h, r, t)$。已知的三元组只是冰山一角——如何自动发现缺失的关系？

建模：实体 = 节点，关系 = 有标签的有向边。知识图谱是一个大规模异构有向图。

对应图问题：知识图谱补全 = 链接预测。Art. 18 的图嵌入方法（TransE, RotatE, CompGCN）将实体和关系映射到向量空间，然后用评分函数预测缺失边。例如，TransE 的核心思想是 $\mathbf{h} + \mathbf{r} \approx \mathbf{t}$（头实体向量 + 关系向量 ≈ 尾实体向量）。

共指消解 → 连通分量

真实问题：“奥巴马在白宫发表演讲。他说经济正在好转。总统还提到了就业数据。” “奥巴马”、“他”、“总统”指代同一个实体。

建模：每个”提及”（mention）是一个节点。如果分类器判断两个提及可能共指，则连一条边。

对应图问题：聚类成共指链 = 找连通分量，这是 Art. 2 的基本操作。工业级系统用 Union-Find 在近乎 $O(n)$ 时间内完成。

案例 5：生物信息学

生物系统的核心——从蛋白质交互到代谢网络到基因组组装——几乎全是图问题。

蛋白质交互网络 → 社区发现 + 中心性

真实问题：蛋白质交互网络（Protein-Protein Interaction, PPI）中有数千个蛋白质和数万条交互。哪些蛋白质是”关键蛋白质”（essential proteins）？哪些蛋白质形成功能模块（functional module）？

建模：蛋白质 = 节点，实验检测到的物理交互 = 边。得到一个大规模无向图。

对应图问题：关键蛋白质识别 = Art. 7 的度中心性 / 介数中心性——移除高中心性蛋白质对网络连通性破坏最大，这与实验中敲除该基因导致致死（essential gene）高度相关。功能模块发现 = Art. 8 的社区发现——同一功能模块的蛋白质在 PPI 网络中形成密集连接的社区。

DNA 序列组装 → de Bruijn 图 + 欧拉路径

真实问题：高通量测序仪产出数亿条短序列（reads，通常 100-300bp），它们是基因组的随机片段。如何从这些短片段重建完整基因组？

建模：构建 de Bruijn 图——将每个 read 分解为长度 $k$ 的子串（$k$-mer），每个 $k$-mer 是一个节点。如果两个 $k$-mer 有 $k-1$ 个碱基的重叠（一个的后缀 = 另一个的前缀），则连一条有向边。

对应图问题：重建基因组 = 在 de Bruijn 图中找欧拉路径——这正是 Art. 4 的 Hierholzer 算法。为什么用欧拉路径而不是哈密顿路径？因为 de Bruijn 图的规模由 $k$-mer 数量（与基因组长度成正比）决定，而不是 read 数量（远大于基因组长度）。欧拉路径可以在 $O(|E|)$ 时间内找到，而哈密顿路径是 NP-hard。

这是整条路径中最漂亮的应用之一：Compeau, Pevzner & Tesler (2011) 的综述展示了如何用一个看似纯理论的图论结果（欧拉回路）解决一个重大的实际生物学问题。

代谢通路 → 网络流

真实问题：细胞的代谢系统可以看作一个”工厂”——葡萄糖进入，ATP 产出。代谢通路中的每个化学反应有速率上限。整个系统的最大产出是多少？哪些反应是瓶颈？

建模：代谢物 = 节点，化学反应 = 有向边（容量 = 反应速率上限），葡萄糖 = 源点，ATP = 汇点。

对应图问题：最大 ATP 产出 = Art. 12 的最大流问题。瓶颈反应 = 最小割中的边。实际上，通量平衡分析（Flux Balance Analysis, FBA）——系统生物学的标准工具——本质就是线性规划（LP），而最大流是 LP 的特例。

案例 6：芯片设计 (VLSI)

集成电路设计的核心挑战——将数百万个逻辑门放置在芯片上并连接它们——是图算法最大的工业用户之一。

VLSI 布局 → 图划分

真实问题：一个现代 SoC（System on Chip）有数亿个晶体管。物理设计的第一步是划分（partitioning）：将电路分成若干块，使得每块的面积均衡，且块间的信号连线（cross-partition wires）最少——因为跨块连线慢、耗电、占面积。

建模：门电路 = 节点，信号连线 = 边（或超边，因为一个信号可能连接多个门）。

对应图问题：这是 Art. 14 的平衡图划分——NP-hard 问题。工业标准是 METIS 的多级划分方法（粗化 → 初始划分 → 逐层细化）。Karypis & Kumar (1998) 的 METIS 算法在 VLSI CAD 工具中已经使用了超过 25 年。

布线 → Steiner Tree

真实问题：划分完成后，需要用金属线将属于同一信号网（net）的所有 Pin 连接起来，且总线长最短。

建模：芯片表面是一个网格图，Pin 是需要连接的终端节点。

对应图问题：这是 Steiner Tree 问题——Art. 11 的 MST 的推广（允许添加辅助节点来减少总长度）。Steiner tree 是 NP-hard 的，但 Pin 数量（每个信号网通常 2-20 个）有限，所以可以用 Art. 15 的 FPT 算法（参数 = Pin 数）。

时序分析 → DAG 关键路径

真实问题：芯片的时钟频率由关键路径决定——信号从输入到输出经过最长延迟的路径。

建模：逻辑门 = 节点（权重 = 门延迟），信号连接 = 有向边。由于没有组合环路，电路是一个 DAG。

对应图问题：关键路径 = DAG 上的最长路径——Art. 3 的拓扑排序后一次线性扫描即可。时序违规（timing violation）的修复方法：在关键路径上的门前插入 buffer（增加节点），或替换为更快的门（修改节点权重）。

案例 7：交通与物流

交通网络可能是图算法最直观的应用——路口是节点，道路是边——但其中的算法问题远比”找最短路”复杂。

路径规划 → 最短路径 + A*

真实问题：Google Maps / 高德地图的导航：从起点到终点的最快路线。

建模：路口 = 节点，道路 = 加权边（权重 = 行驶时间，考虑距离、限速、实时交通）。

对应图问题：Art. 6 的 Dijkstra 算法。但实际地图有数亿节点，原始 Dijkstra 太慢。工业级方案：A*（用直线距离作为启发函数），以及更高级的预处理方法——Contraction Hierarchies（CH）和 Hub Labeling——可以将查询时间从秒级降到微秒级。CH 的核心思想是利用道路网络的层次结构（高速公路 → 主干道 → 支路），预处理时添加”快捷边”（shortcut edges），查询时只需在高层图上搜索。

配送路线 → TSP / VRP

真实问题：物流公司有一个仓库和 100 个客户，如何规划配送路线使总行驶距离最短？如果有多辆车呢？

建模：客户 = 节点，仓库 = 特殊的源节点，距离 = 边权。单车 = TSP（旅行商问题），多车 = VRP（Vehicle Routing Problem）。

对应图问题：Art. 15 的 NP-hard 问题。实践中使用 Christofides 近似 + 2-opt/3-opt 局部搜索。Google OR-Tools 是开源的工业级 VRP 求解器，UPS 的 ORION 系统每年节省 4 亿美元。

交通流量 → 网络流

真实问题：城市规划师需要评估”如果关闭某条道路进行施工，交通会受多大影响”？

建模：区域 = 节点，道路 = 有向边（容量 = 道路通行能力），住宅区 = 源点，商业区 = 汇点。

对应图问题：Art. 12 的最大流 / 最小割。最小割给出了”切断交通的瓶颈道路集合”。Wardrop 均衡（交通分配模型）是网络流的推广——每个”流”（通勤者）会选择自己的最短路径，最终达到纳什均衡。

案例 8：社交网络分析

社交网络是”图”最直观的实例——用户是节点，关系是边。但社交网络分析中的算法问题比看起来复杂得多。

影响力最大化 → 中心性 + 社区

真实问题：一个新产品的营销预算只够邀请 50 个”种子用户”免费试用。如何选择这 50 个人，使得通过口碑传播最终影响的总人数最大？

建模：用户 = 节点，社交关系 = 有向边（权重 = 影响概率）。

对应图问题：这是 Kempe, Kleinberg & Tardos (2003) 定义的影响力最大化问题——NP-hard，但子模函数（submodular function）的贪心算法有 $(1 - 1/e)$ 近似比。种子选择的启发式方法：选 Art. 7 中高度中心性 / PageRank 的节点，并确保种子分布在不同 社区 中以最大化覆盖范围。

虚假账号检测 → 团/密子图

真实问题：社交平台上的虚假账号（bot/troll farm）通常批量创建，互相关注以伪装正常用户。如何检测？

建模：用户 = 节点，互相关注 = 边。

对应图问题：虚假账号集群在图中表现为近似团（near-clique）——内部边密度远高于与外部的连接。这是 Art. 10 的密子图检测问题。Facebook/Meta 的反作弊系统使用图聚类 + 密度异常检测来识别这些”太密了不正常”的子图。

信息传播 → 随机图模型

真实问题：一条假新闻在 Twitter 上发布后，会传播多广？传播速度有多快？

建模：传播过程可以用 SIR（Susceptible-Infected-Recovered）模型描述——每个节点处于”未感染/已感染/已恢复”三种状态之一，感染沿边以一定概率传播。

对应图问题：传播动力学的分析依赖于 Art. 16 的随机图模型——特别是网络的度分布（幂律 vs 均匀）决定了传播的阈值行为（epidemic threshold）。在 scale-free 网络中，由于 hub 节点的存在，传播阈值趋近于零——这就是为什么虚假信息在社交网络上传播如此容易。

建模方法论：如何识别”图问题”

看完 8 个领域、30+ 个案例，一个自然的问题是：面对一个新问题，如何判断它是不是图问题？如何建模？

三步识别法

第一步：识别实体和关系。 问自己：

• 这个问题中的”东西”是什么？（→ 节点）
• 这些”东西”之间有什么关系？（→ 边）
• 关系是双向的还是单向的？（→ 无向图 / 有向图）
• 关系有强弱之分吗？（→ 加权 / 无权）

第二步：映射到已知图类型。 常见的映射模式：

问题结构	图类型	典型工具
两类实体之间的配对	二部图	匹配 (Art. 13)
有先后顺序的依赖关系	DAG	拓扑排序 (Art. 3)
层级/从属关系	树	树算法 (Art. 5)
资源限制下的分配/流动	流网络	网络流 (Art. 12)
互斥约束	一般图	着色 (Art. 14)
相似性/距离	加权图	最短路径 (Art. 6)
群体结构	一般图	社区发现 (Art. 8)

第三步：选择算法并检查复杂度。 先查这个图问题是 P 还是 NP-hard（参考 Art. 15 的全景表）。如果是 NP-hard，考虑近似算法、FPT、启发式。

常见的建模陷阱

1. 过度建模：把不需要图结构的问题硬套成图。如果实体之间没有有意义的关系，纯表格/数组就够了。
2. 边的定义不清：边应该代表什么？“相似”还是”交互”？不同的边定义会导致完全不同的图结构和算法选择。
3. 忽略图的规模：同一个问题在 100 个节点和 1 亿个节点上需要完全不同的算法。检查你的图规模，选择合适复杂度的算法。
4. 静态 vs 动态：真实世界的图通常是动态的（边在增加/删除）。如果更新频率高，需要增量/在线算法而不是每次重建。

实现指引

应用场景	库	函数/方法
通用图算法	NetworkX	nx.shortest_path(), nx.connected_components(), …
图着色 (寄存器分配)	NetworkX	nx.coloring.greedy_color(G, strategy='DSATUR')
社区发现	NetworkX / cdlib	nx.community.louvain_communities(G)
中心性	NetworkX	nx.betweenness_centrality(G), nx.pagerank(G)
图划分 (VLSI)	METIS	metis.part_graph(G, nparts=k)
路径规划 (A*)	NetworkX	nx.astar_path(G, source, target, heuristic)
TSP / VRP	Google OR-Tools	ortools.constraint_solver.routing
网络流	NetworkX	nx.maximum_flow(G, s, t)
图嵌入 / GNN	PyG / DGL	torch_geometric.nn.GCNConv, dgl.nn.GraphConv
因果推断	pgmpy / DoWhy	pgmpy.models.BayesianNetwork, dowhy.CausalModel
知识图谱嵌入	PyKEEN	pykeen.pipeline.pipeline(model='TransE', ...)
DNA 组装	SPAdes / Velvet	基于 de Bruijn 图的基因组组装器

总结：从 Art. 0 到 Art. 19

本文是整条路径的终点。让我们回顾这段旅程。

Part 1”探”（Art. 1-5）建立了看清图结构的能力：BFS/DFS 是万事的起点，连通分量揭示图的宏观骨架，拓扑排序处理依赖关系，欧拉/哈密顿回路是”遍历”的两个极端（P vs NP-hard），树算法处理最简单也最重要的图结构。

Part 2”量”（Art. 6-10）加入了度量和排名：最短路径量化节点间的距离（Dijkstra/Bellman-Ford 的松弛范式贯穿全路径），中心性给节点打分，社区发现识别群体，相似度/同构比较两张图，团和密子图找到最密集的核心。

Part 3”优”（Art. 11-15）构建了组合优化工具箱：MST 用贪心达到全局最优，网络流用增广路实现对偶性，匹配在二部图和一般图上配对，着色与划分分配有限资源，NP-hard 近似算法用 Christofides 这样的”组合已有工具”思维面对不可解问题。

Part 4”建模”（Art. 16-19）完成了从理论到应用的闭环：随机图模型解释真实网络的统计规律，概率图模型处理不确定性推断，图嵌入/GNN 连接图论与深度学习，而本文——图建模案例集——展示了如何反过来，从真实问题中识别图结构。

整条路径的核心信息只有一句话：

图是”实体 + 关系”的通用建模语言。掌握了图的词汇表（节点、边、路径、连通性、流、匹配、着色、嵌入），你就拥有了一套跨越编译器、推荐系统、生物信息、因果推断、芯片设计、交通物流、社交网络的统一工具。

20 篇文章只是起点。图算法的前沿仍在快速发展——动态图算法、量子图算法、超大规模分布式图计算、几何图神经网络……但核心的思维方式不会变：识别实体和关系，建模为图，选择合适的算法。