图论与网络模型

把对象看成顶点，把关系或通道看成边，就可以用图论语言研究连通、路径、流量、匹配与结构位置。边可以有方向、容量、费用与长度；顶点可以有权重与类型。图一旦建错（方向、权的含义、是否允许重边/自环），后面的“最优”都只是错误模型上的精确解。

可以把它想成“在约束下的结构上做可检验的计算”。例如：

交通/管网中从 A 到 B 的最短或最快路径；
最小成本把居民点连成通信/供电网络；
物流网络的最大通过能力与瓶颈割；
人员与任务的最优匹配、车辆巡回配送；
社交或引用网络中谁处在结构关键位置、社区如何划分。

建模竞赛里，图论题的得分点往往在：图是否与题意同构、约束是否写全、小例子能否手算验证、启发式是否有基线与多种子。

一、这一门类解决什么问题

问题类型	典型问法	代表方法	所在位置
路径	从 A 到 B 怎么走最近/最快	Dijkstra / Floyd / Bellman–Ford / A*	最短路径
连通造价	如何用最小成本连成一体	最小生成树 Prim / Kruskal	最小生成树
运输极限	网络最多能送多少，瓶颈在哪	最大流 / 最小割	最大流最小割
带成本流	完成规定流量且费用最小	最小费用流；有上下界可行流	网络流扩展
巡回与配送	走完所有点/客户，车容量与时间窗	TSP / VRP 与启发式	TSP与VRP…
配对	一人一任务、最大权匹配	匈牙利、KM	二分图匹配
结构位置	谁重要、是否抱团	度、中心性、聚类系数、PageRank	复杂网络度量
社区	网络自然分成哪些模块	Louvain 等	社区发现

本门类方法大致沿四条主线展开：

经典组合优化：最短路、最小生成树、匹配；
网络流：最大流最小割、费用流、上下界流；
硬组合与启发式：TSP/VRP；
复杂网络描述：度量、中心性、社区发现。

二、如何选择方法

先问清五件事，再进算法：

图对不对：有向还是无向？权是长度、时间、可靠度、费用还是容量？能否取负？
目标是什么：最优值、一条可行方案、还是结构描述（中心性/社区）？
约束有哪些：容量、预算、车载、时间窗、禁止弧、度约束、上下界；
规模多大：小图应精确可复现；TSP/VRP 大实例需启发式，并给下界/朴素基线；
如何验证：手算小例、割容量、生成树边数 $n-1$ 、流守恒、匹配饱和性。

问题信号	优先考虑
非负权单源最短路	Dijkstra；网格/启发信息可用 A*
可能有负权边（无负环）	Bellman–Ford；全源用 Floyd
连通且总造价最小	MST（注意：MST 不是最短路树）
源汇最大输送、找瓶颈	最大流；用最小割解释瓶颈
流量达标且总费用最小	最小费用流
边/顶点有下界	先可行流（上下界）再优化
二分图分配、最大权	匈牙利 / KM
巡回访问、多车配送	TSP/VRP 模型 + 精确小例/启发式
谁处于结构关键位置	中心性、PageRank（解释保持结构意义）
自然分组模块	社区发现（Louvain 等）

三、方法选择的决策逻辑

边权/容量的含义是什么？目标是路径、树、流、匹配还是结构？
 ├─ 路径最优 → 最短路（看权是否非负、单源/全源）
 ├─ 连通代价最小 → MST
 ├─ 输送量/瓶颈 → 最大流最小割
 │    └─ 还要费用/上下界 → 费用流、可行流改造
 ├─ 一对一分配 → 二分图匹配
 ├─ 巡回/多车 → TSP/VRP（先写清约束，再求精确或启发式）
 └─ 无“最优运送”，要描述网络形态
      ├─ 点的重要性 → 中心性 / PageRank
      └─ 模块划分 → 社区发现

与 02 优化问题的关系：许多图问题可写成 IP/LP；图论算法往往更直接、也更易给出组合证明（如最小割）。大尺度 VRP 也可“图论建模 + 优化求解器/启发式”混合。

四、统一的建模工作流

抽象：列出顶点集、边集、方向、权与容量的单位；说明多重边与自环是否允许；
画小图：用题面可核对的小例子展示符号；
选型：按上表选择问题类型（不要用最短路去“近似”最大流）；
求解：
- 精确算法：写清复杂度与适用条件（负权、负环）；
- 启发式：多随机种子，报告最好/平均/方差，并与下界或小规模精确解对照；
验证：
- 最短路：三角不等式抽查、与 Floyd 小图对照；
- MST：边数 $n-1$ 、连通、权之和；
- 流：守恒、容量限制、最大流=最小割；
- 匹配：无共用顶点、权之和；
解释：路径/割/中心性的业务含义；瓶颈边、关键节点、社区画像；
灵敏度：删边、扩容、权扰动后方案如何变（呼应全局方法论）。

五、MATLAB 与实现提示

任务	常用入口
建图	`graph`, `digraph`
最短路	`shortestpath`, `distances`
最小生成树	`minspantree`
最大流	`maxflow`
中心性等	`centrality`
可视化	`plot`

竞赛论文中，鼓励对核心算法做小规模手写推演（Dijkstra 标号过程、增广路、匈牙利矩阵），再给出程序结果；只贴工具箱调用难以体现理解。TSP/VRP 启发式需固定随机种子以便复现。

六、与各子目录/篇章的对应关系

子目录或篇章	核心任务	典型出口
最短路径	点到点（或全源）最优走法	路径与距离
最小生成树	最小代价连通子图	树边集合
最大流最小割	输送上界与瓶颈证明	流量与割
网络流扩展	费用与上下界	最优流/可行流
二分图匹配	一对一最优分配	匹配与总权
TSP与VRP…	巡回与车辆路径	路线与目标值
复杂网络度量	结构位置与局部密集程度	指标表与分布
社区发现	模块划分	社区标签与模块度

图论与 11 模拟与仿真的衔接：网络上的随机游走、故障级联、排队可在仿真中展开。与 07 评价的衔接：中心性可作为评价指标之一，但“结构重要”≠“因果重要”。

七、使用提醒与常见陷阱

建图错误：把双向道建成无向、权用错单位、把容量写在点上却当边容量用；
算法前提忽视：负权仍用 Dijkstra；有负环却谈最短路；
MST 与最短路混淆：生成树总长最小，不保证某两点距离最短；
最大流不会解释：只给一个流量数，不给最小割/瓶颈边，难以写讨论；
启发式只报一次结果：无种子、无基线、无与下界差距；
中心性滥用：度高/PageRank 高就被写成“最重要决策者”或因果核心；
社区强行业务命名：模块度最优切割未必对应行政部门或自然地理边界；
VRP 约束漏写：容量、时间窗、车数在文中与代码不一致。

八、推荐学习顺序

先读本导读，练习把题面翻译成 $(V,E)$ 与权的含义；
最短路径与最小生成树（手算小图）；
最大流最小割，建立“流—割对偶”直觉；
网络流扩展（最小费用流、上下界）；
二分图匹配（匈牙利、KM）；
TSP/VRP 的建模与启发式，强调基线与复现；
复杂网络度量与社区发现，解释保持克制。

进入具体方法页后，按「直观理解 → 适用场景 → 原理 → 关键决策 → MATLAB/步骤 → 解释 → 误区 → 小结」阅读，并在小图上逐步推演。最终写进论文的，应是正确的图 + 可验证的算法过程 + 可解释的结构结论，而不是一张无单位、无约束核对的“最优路线截图”。

一、这一门类解决什么问题​

二、如何选择方法​

三、方法选择的决策逻辑​

四、统一的建模工作流​

五、MATLAB 与实现提示​

六、与各子目录/篇章的对应关系​

七、使用提醒与常见陷阱​

八、推荐学习顺序​