图论——枢纽页

2026/05/28 16:16:30·2026/06/03 12:00:30

数学图论·14 min read

Introduction · 图论导引

图：关系的数学语言

图论研究的是「节点」与「边」构成的离散结构。听起来简单，但它几乎是所有关系建模的数学基础：社交网络里的人际连接、交通网络里的路径规划、电路板上的布线、分子结构中的化学键、甚至深度学习里的消息传递——背后都是图。

本枢纽页按主题组织图论方向的 5 篇专题笔记，涵盖从经典问题（图着色、网络流）到现代应用（谱图论、随机图、拓扑图论）的核心内容。

📖 核心专题

排序：

经典问题

从四色定理到 NP-完全性——图着色问题是组合优化的入口，也是理解计算复杂性的经典案例。

网络优化

最大流最小割定理是网络优化的基石——它将流量问题转化为割的对偶问题，也是线性规划对偶理论的图论实例。

随机结构

从 Erdős–Rényi 模型到无标度网络——随机图论揭示了大规模网络的统计规律，是网络科学的理论基础。

代数方法

谱图论用线性代数的语言描述图的结构——图拉普拉斯矩阵的特征值编码了连通性、划分、扩散等深层性质。

拓扑视角

拓扑图论研究图在曲面上的嵌入——平面性判定、Kuratowski 定理、图的亏格，是组合与拓扑的交叉领域。

6 篇文章 · 5 条连接

🗺️ 建议学习路径

路径一：从经典到现代

图着色 → 网络流 → 随机图 → 谱图论 → 拓扑图论。从组合优化的直觉出发，逐步引入代数和概率工具。

路径二：面向应用

网络流（优化） → 随机图（网络科学） → 谱图论（图神经网络）。侧重工程和机器学习中的图方法。

📋 待完成专题