图论

图论研究对象之间的连接结构。图由顶点和边组成，通常写作 $G = (V, E)$ ：顶点表示对象，边表示关系。边在纸上画成直线还是曲线通常不改变图；交叉处也不自动成为顶点。

先说明使用哪一种图

简单无向图没有自环，也没有连接同一对顶点的重复边。有向图给边规定方向；加权图为边附上距离、耗时或费用等数值。不同定义会改变定理和算法的条件，例如本条的度数计数先采用简单无向图。

图中的邻接关系可用邻接表或矩阵保存。无向图的邻接矩阵对称；如果边权为零是合法的，程序应区别“没有边”和“有一条零权边”。

顶点的度数是与它相接的边数。每条无向边贡献两个端点，所以 $\sum_{v \in V} \deg (v) = 2 | E | .$ 上图的度数依次为 $2, 2, 2, 3, 1$ ，总和为 10，恰好是 5 条边的两倍。由总和为偶数还可推出：奇数度顶点的个数一定为偶数。

路径通常指不重复顶点、沿边依次行走的序列；闭合且除起终点外不重复顶点的路径称为圈。若任意两顶点间都有路径，图称为连通图。

有限无向图中的树是连通且无圈的图。含 $n$ 个顶点的树有 $n - 1$ 条边，而且任意两点之间的路径唯一。上图删除边 $C D$ 后就成为树；原图的 $A - B - D - C - A$ 是一个圈。

可用逐次删除叶子证明树的边数公式：非平凡有限树存在度为 1 的顶点，删去它及相接边仍是树；直到只剩一个顶点、零条边，得到边数始终比顶点数少 1。

欧拉迹要求每条边恰好经过一次，可以重复顶点；哈密顿路径要求每个顶点恰好经过一次，不要求走遍边。

对所有非孤立顶点处于同一连通分量的有限无向图，存在欧拉迹当且仅当奇数度顶点为 0 个或 2 个。上图的奇数度顶点是 $D, E$ ，一条欧拉迹为 $D - B - A - C - D - E$ 。若全部度数为偶数，则可找到闭合的欧拉回路。

无权图可用广度优先搜索求最少边数路径；非负边权图可用 Dijkstra 算法求最小权重路径。上图两条简单的 $A$ 到 $E$ 路线分别重 $2 + 2 + 3 = 7$ 和 $5 + 1 + 3 = 9$ ，所以选择前者。

有负边权时不能直接照搬 Dijkstra 的正确性结论；若存在可达且能通向目标的负权回路，甚至可能没有有限最短游走。现实建模还需判断边是否有方向、是否允许重复以及费用是否随时间改变。