图论：修订间差异

2026年9月20日 (日) 00:33的版本

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

先说明使用哪一种图

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

五个顶点A到E构成带权图，边AB为二，AC为五，BD为二，CD为一，DE为三，路线ABDE被突出显示 — 从 A 到 E 的加权最短路线为 A—B—D—E，总权重 7；边权与图上画出的长度是两回事。

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

度数与握手定理

顶点的度数是与它相接的边数。每条无向边贡献两个端点，所以 $\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 的正确性结论；若存在可达且能通向目标的负权回路，甚至可能没有有限最短游走。现实建模还需判断边是否有方向、是否允许重复以及费用是否随时间改变。

延伸阅读

Oscar Levin，《Discrete Mathematics: An Open Introduction》第 4 章：图、树、欧拉迹。
组合数学 · 矩阵 · 优化

@@ 第1行： / 第1行： @@
-图论研究由顶点与边组成的结构。顶点可以表示对象，边可以表示对象之间的关系。
+图论研究对象之间的连接结构。图由顶点和边组成，通常写作 <math>G=(V,E)</math>：顶点表示对象，边表示关系。边在纸上画成直线还是曲线通常不改变图；交叉处也不自动成为顶点。
-== 核心表达 ==
+== 先说明使用哪一种图 ==
-{{定义|内容=<math display="block">\sum_{v\in V}\deg(v)=2|E|</math>}}
+简单无向图没有自环，也没有连接同一对顶点的重复边。有向图给边规定方向；加权图为边附上距离、耗时或费用等数值。不同定义会改变定理和算法的条件，例如本条的度数计数先采用简单无向图。
-== 直觉与例子 ==
+[[File:Gezhi-graph-path.svg|frame|center|alt=五个顶点A到E构成带权图，边AB为二，AC为五，BD为二，CD为一，DE为三，路线ABDE被突出显示|从 A 到 E 的加权最短路线为 A—B—D—E，总权重 7；边权与图上画出的长度是两回事。]]
-对有限无向图，每条边都贡献两个度，因此所有顶点的度数之和等于边数的两倍。这称为握手引理。
+图中的邻接关系可用邻接表或[[矩阵]]保存。无向图的邻接矩阵对称；如果边权为零是合法的，程序应区别“没有边”和“有一条零权边”。
-== 继续阅读 ==
+== 度数与握手定理 ==
-* [[组合数学]]
+顶点的度数是与它相接的边数。每条无向边贡献两个端点，所以
-* [[逻辑]]
+<math display="block">\sum_{v\in V}\deg(v)=2|E|.</math>
+上图的度数依次为 <math>2,2,2,3,1</math>，总和为 10，恰好是 5 条边的两倍。由总和为偶数还可推出：奇数度顶点的个数一定为偶数。
+== 路径、连通与树 ==
+路径通常指不重复顶点、沿边依次行走的序列；闭合且除起终点外不重复顶点的路径称为圈。若任意两顶点间都有路径，图称为连通图。
+有限无向图中的树是连通且无圈的图。含 <math>n</math> 个顶点的树有 <math>n-1</math> 条边，而且任意两点之间的路径唯一。上图删除边 <math>CD</math> 后就成为树；原图的 <math>A-B-D-C-A</math> 是一个圈。
+可用逐次删除叶子证明树的边数公式：非平凡有限树存在度为 1 的顶点，删去它及相接边仍是树；直到只剩一个顶点、零条边，得到边数始终比顶点数少 1。
+== 两种容易混淆的“走遍” ==
+欧拉迹要求每条边恰好经过一次，可以重复顶点；哈密顿路径要求每个顶点恰好经过一次，不要求走遍边。
+对所有非孤立顶点处于同一连通分量的有限无向图，存在欧拉迹当且仅当奇数度顶点为 0 个或 2 个。上图的奇数度顶点是 <math>D,E</math>，一条欧拉迹为 <math>D-B-A-C-D-E</math>。若全部度数为偶数，则可找到闭合的欧拉回路。
+== 最短路需要匹配算法条件 ==
+无权图可用广度优先搜索求最少边数路径；非负边权图可用 Dijkstra 算法求最小权重路径。上图两条简单的 <math>A</math> 到 <math>E</math> 路线分别重 <math>2+2+3=7</math> 和 <math>5+1+3=9</math>，所以选择前者。
+有负边权时不能直接照搬 Dijkstra 的正确性结论；若存在可达且能通向目标的负权回路，甚至可能没有有限最短游走。现实建模还需判断边是否有方向、是否允许重复以及费用是否随时间改变。
+== 延伸阅读 ==
+* [https://discrete.openmathbooks.org/dmoi3.html Oscar Levin，《Discrete Mathematics: An Open Introduction》第 4 章]：图、树、欧拉迹。
+* [[组合数学]] · [[矩阵]] · [[优化]]
 [[分类:离散数学]]