图论
tú lùn
图论是对图的数学研究,图是由顶点(点)通过边(线)连接而成的结构,用于建模网络和关系。
Definition
图论研究由点（顶点）通过线（边）连接而成的图形，这类图形能刻画各种网络：朋友关系、道路网络、互联网。严格地说，图 $G = (V, E)$ 由一个顶点集 $V$ 和一个由顶点对组成的边集 $E$ 组成，可以是有向的（边有方向）或无向的；关键概念包括顶点的度、连通分量、圈、路径和生成树。更严格地说，$E \subseteq V \times V$（有向）或 $E \subseteq \{\{u,v\}: u,v \in V\}$（无向）；图论与组合数学、代数（谱图理论使用邻接矩阵的特征值）、拓扑学（图在曲面上的嵌入）以及算法（图同构问题与 P 与 NP 问题有关）都有交集。
Example
想象一张城市（顶点）通过道路（边）连接的地图：图论回答诸如"从城市 A 到城市 B 的最短路线是什么"这样的问题。哥尼斯堡七桥问题问的是能否恰好走过全部 $7$ 座桥各一次；欧拉在1736年证明了这不可能，从而创立了图论，并证明一个图存在欧拉路径当且仅当恰好有 $0$ 个或 $2$ 个顶点度数为奇数。四色定理指出每个平面图都可以用 $4$ 种颜色染色，使相邻顶点颜色不同，由阿佩尔和哈肯于1976年通过计算机验证了 $1{,}936$ 种情形而证明。
Key Insight
只要事物之间存在连接，图论就适用：社交网络、电路板、航班路线和家谱都是图，而欧拉对七桥问题的解决方案引入了图的遍历，如今这已成为 GPS 导航、网络爬虫和网络路由的基础。谱图理论利用拉普拉斯矩阵的特征值来研究图上的连通性、扩散和随机游走，在机器学习（图神经网络）中有着广泛应用。