图论：修订间差异

2026年9月20日 (日) 07:16的最新版本

图论（graph theory）研究对象之间的连接关系。图中的点称为顶点，连接两个顶点的线称为边。例如把车站画成点、把相邻车站间的线路画成边，就可以研究能否到达、怎样经过所有线路以及如何选择路线。

图关注的是哪些点相连。把一条边画直或画弯，把两个相连顶点挪近或挪远，通常不会改变连接关系；若要表示路程或费用，则可以在边旁另标数值。

读懂一张五点图

下面的图有 A、B、C、D、E 五个顶点。先忽略边旁的数字，从 A 出发沿线观察：可以直接去 B 或 C；B、C 都能去 D；E 只与 D 相连。金色路线展示了从 A 经 B、D 到 E 的一种走法。

五点图有边AB、AC、BD、CD和DE，金色突出ABDE路线，五条边权依次为二五二一三 — 顶点表示位置，线表示连接；边旁数字给出另行指定的权重。

把顶点集合记为 V、边集合记为 E，就能将图写成 $G = (V, E)$ 。本例为 $V = {A, B, C, D, E}, E = {A B, A C, B D, C D, D E} .$ 这里 AB 与 BA 表示同一条边，它没有方向；同一对顶点间只画一条边，也没有顶点连回自身。这种图称为简单无向图。以下关于度数、树和二分图的讨论采用有限简单无向图。

如果道路只能单向通行，就在边上标箭头，得到有向图。如果两地之间的两座桥需要分别记录，就允许连接相同顶点的平行边，得到多重图。边旁有费用、长度等数值时，称为加权图，数值叫边权。道路在纸上交叉，只有明确标出连接顶点时才算路口。

度数：一共有多少个边端点

与顶点相接的边数，叫该顶点的度数，记作 $\deg (v)$ 。在图中，A 接 AB、AC，度数为 2；D 接 BD、CD、DE，度数为 3；E 的度数为 1。五个顶点的度数依次是 $2, 2, 2, 3, 1.$ 相加为 10，恰好是边数 5 的两倍。

这是握手定理： $\sum_{v \in V} \deg (v) = 2 | E | .$ 左侧按顶点数边的端点，右侧按边数端点。每条无向边都有两个端点，因此每条边在总和中恰好被数两次。用握手比喻，一次握手既记入一个人的握手次数，也记入另一个人的次数。

总和是偶数。偶数度顶点的贡献本身为偶数，要使剩下的奇数度之和仍为偶数，奇数度顶点就必须有偶数个。本例恰有 D、E 两个。这条结论稍后会决定哪些顶点能成为走遍全部边的路线端点。若允许自环，一条自环的两个端点都在同一顶点，度数需计两次，握手等式才保持原意。

路径与连通：怎样从一个点走到另一个点

沿着边行走得到游走，顶点和边都可以重复。如果不重复任何边，称为迹；如果不重复任何顶点，称为路径。例如 $A - B - D - C$ 是路径，而 $D - B - A - C - D - E$ 重复经过 D，是迹而不是路径。

起点与终点相同、其他顶点不重复的闭合走法称为圈。简单无向图中的圈至少有三条边；本例的 $A - B - D - C - A$ 是四条边组成的圈。

若任意两顶点之间都有路径，图就连通。本例连通，但删去 DE 后，E 与其余顶点分离。删掉这样的边会破坏连通性，称它为桥。相比之下，删去 CD 后仍可以沿 $C - A - B - D$ 到达 D，图仍连通。

逐层寻找最少步数

从 A 去 E 最少要走几条边？先把 A 标为第 0 层；它的邻点 B、C 是第 1 层；从 B、C 继续走，首次发现 D，放在第 2 层；再从 D 发现 E，放在第 3 层。于是最少需要 3 条边。

这种逐层搜索叫广度优先搜索。每当发现一个新顶点，就记录从哪个顶点来到它；反向跟随这些记录，可以恢复一条最短路径。例如 E 从 D 发现，D 从 B 发现，B 从 A 发现，得到 $A - B - D - E$ 。

逐层搜索之所以正确，是因为第 k 层的点已有长度 k 的路线。沿一条边首次到达的新点有长度 k+1 的路线；若它存在更短路线，那么在先前处理那条路线的前驱时就应已被发现。这样一层层推进，首次发现的层数恰好就是最少边数。

边权不同则是另一个问题。图中 $A - B - D - E$ 与 $A - C - D - E$ 都有三条边，但权重分别为 $2 + 2 + 3 = 7$ 与 $5 + 1 + 3 = 9$ 。金色路线的权重更小。处理不同边权的算法及负权情形见最短路径。

树：保留连接，去掉绕圈

删除图中的 CD 后，所有顶点仍能互相到达，却不再有圈。树就是非空、连通且无圈的无向图。

树中任意两点之间只有一条路径。连通性保证至少有一条；若有两条不同路径，从它们首次分开的位置出发，沿一条走到再次相遇处，再沿另一条返回，就会围成一个圈。因此路径不能有两条。

含 n 个顶点的有限树恰有 $n - 1$ 条边。证明可以从“叶子”入手：叶子是度数为 1 的顶点。一棵至少有两个顶点的有限树必有叶子，因为选一条最长路径，它的端点不能再接路径外的点，否则还能延长；也不能接路径中除相邻点外的点，否则产生圈。因此最长路径的两端都是叶子。

删去一个叶子及其唯一相接的边，其余部分仍连通且无圈。每次顶点和边都各少一个，反复删到只剩一个顶点、零条边，便得到原来边数始终比顶点数少 1。本例删去 CD 后有 5 个顶点、4 条边，正好符合公式。

反过来，有限 n 顶点图若连通且有 n−1 条边，也必为树。若它有圈，可以从圈上删一条边而保持连通；不断这样删，最终得到含全部顶点的一棵树，已经需要 n−1 条边。原来只有这么多边，就没有可删的多余边。只有边数而没有连通条件不够：三角形外加一个孤立点有 4 个顶点、3 条边，却不是树。

每条边恰走一次：欧拉迹

回到未删边的原图。现在不求最快到达，而要使五条边恰好各经过一次。路线 $D - B - A - C - D - E$ 正好依次经过 DB、BA、AC、CD、DE，每条一次。这样的迹称为欧拉迹；若最后回到起点，称为欧拉回路。

下面把这条走法按 1 到 5 标出。箭头只记录本次行走方向，原图的边仍是无向边；边旁数字现在是经过次序，不是前图的费用。沿箭头走完，D 虽被再次经过，每条边却都恰好使用一次。

五点图的五条边按D到B到A到C到D到E标出方向和一至五的次序，D和E以双圈突出 — 欧拉迹允许重复顶点；两个奇数度顶点 D、E 成为开放路线的端点。

起点为何选 D，终点为何选 E？沿路线经过一个中途顶点时，每次进入都要配一次离开，因此所用的边成对出现。走完全部边后，中途顶点的度数为偶数；开放路线的起点和终点各多一次离开或进入，度数为奇数。因此一条欧拉迹若不闭合，两个端点恰好就是两个奇数度顶点。

完整判据为：有限无向图至少有一条边，且所有非孤立顶点相互连通时，有欧拉迹当且仅当奇数度顶点有 0 个或 2 个。零个时可以闭合，两个时必须以这两点为端点。

为什么奇偶条件也足以构造路线

先设所有度数都为偶数。从一个有边的顶点出发，每次选择尚未使用的边，直到无法继续。若走到起点以外的某点，先前每次进入和离开都成对，当前这次进入又使用了一条边；既然总度数为偶数，就还会剩下一条未用边可以离开。因此走法不会停在其他点，只能回到起点，形成一条闭合迹。

若还有边没用，由连通性，当前闭合迹上必有某点与未用边相接。从这个点再次沿未用边行走：已用的闭合迹在每点消耗偶数条边，剩下的度数仍为偶数，故又能得到一条闭合迹。将它插入原迹，再继续处理剩余边。边数有限，这个过程最终用完全部边。

若只有两个奇数度顶点，先在它们之间加一条临时边，使度数都变偶数，构造欧拉回路后去掉临时边，即得到所需开放迹。原来已有连接边时，临时边与它平行，需要将两条边分别识别；上述配对论证同样适用于这种多重图。

若在配图中再加 BE，B 的度数从 2 变 3，E 从 1 变 2，D 仍为 3。新图仍有欧拉迹，但两个端点改成 B、D。A 为偶数度，不能作为这种开放迹的起点。

哈密顿路径则要求每个顶点恰好经过一次，不要求用完所有边。例如 $B - A - C - D - E$ 是本例的一条哈密顿路径。两种“走遍”分别约束边和顶点，问题不同。

把顶点分成两组：二分图

将配图顶点分为 ${A, D}$ 与 ${B, C, E}$ 。检查每条边，AB、AC、BD、CD、DE 都跨越两组，没有边连接同组内的两个点。能够这样分组的图叫二分图。

二分图中的圈只能有偶数条边：每走一步都会换到另一组，回到原来一组必须走偶数步。因此三角形无法二分。反过来，有限无向图只要没有奇数长度的圈，就能分成两组。

可以用广度优先搜索证明反向结论。对每个连通部分选一个起点，把距离为偶数的顶点放一组，奇数的放另一组。若有一条边连接同组两点，它们在搜索树中的深度同奇偶。从一端沿树走到两条根路径最后的共同点，再走到另一端，这条树路径长度为“两端深度之和减去共同深度的两倍”，所以为偶数。加上这条连接边，就围成奇圈，与假设矛盾。因此所有边都跨组。

本例从 A 搜索，偶数层为 A、D，奇数层为 B、C、E，正得到前面的划分。若图不连通，对每个尚未访问的部分分别开始搜索即可。

二分性看圈的长度，欧拉迹看顶点的度数，两者不同。三角形每点度数为 2，有欧拉回路，却不是二分图；一个中心连接三个叶子的星形树可以二分，却有四个奇数度顶点，没有欧拉迹。

怎样记录同一张图

按 A、B、C、D、E 排列顶点，用 1 表示相邻、0 表示不相邻，可以写出邻接矩阵： $M = (\begin{matrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{matrix}) .$ 例如第一行在 B、C 两列为 1，记录 A 的两个邻点。无向性使矩阵对称，没有自环使对角线为零。

矩阵乘法还可以数两步游走。 $(M^{2})_{i j} = \sum_{k} M_{i k} M_{k j}$ 中，每个中间顶点 k 对应一条“先从 i 到 k，再从 k 到 j”的可能走法。例如 A 到 D 可以经过 B 或 C，所以对应元素为 2。

也可以只给每个顶点列出邻点，称为邻接表。搜索时每个顶点只需首次发现时入队，每条无向边从两端各检查一次，因此广度优先搜索的时间量级为 $O (| V | + | E |)$ 。

若给顶点改名或重画位置，却能一一对应地保留相邻关系，两张图称为同构。相同度数序列还不足以证明同构：六边形圈与两个分开的三角形都有 6 个顶点、6 条边，每点度数均为 2，但前者连通，后者不连通。

历史

欧拉研究柯尼斯堡七桥问题时，以陆地区域和桥的连接替代具体的地理形状。能否每座桥恰过一次，取决于连接和度数，而不是桥的实际长度。原论文收录于 Euler Archive，E53，档案标示撰写时间为 1735 年、出版时间为 1741 年。

这一问题是图论早期发展的重要例子。此后，地图着色、化学分子结构、组合计数及计算机网络等问题不断扩展图论的研究范围。MacTutor 的历史综述介绍了七桥问题与拓扑观念发展的联系。

参考资料

Oscar Levin：图的定义与同构。
Oscar Levin，Discrete Mathematics: An Open Introduction，第 4 章：图、树和欧拉迹。
Euler Archive，E53。
MacTutor：拓扑观念发展的历史。
相关条目：最短路径、组合数学、矩阵、优化。

@@ 第1行： / 第1行： @@
-图论研究对象之间的连接结构。图由顶点和边组成，通常写作 <math>G=(V,E)</math>：顶点表示对象，边表示关系。边在纸上画成直线还是曲线通常不改变图；交叉处也不自动成为顶点。
+'''图论'''（graph theory）研究对象之间的连接关系。图中的点称为'''顶点'''，连接两个顶点的线称为'''边'''。例如把车站画成点、把相邻车站间的线路画成边，就可以研究能否到达、怎样经过所有线路以及如何选择路线。
-英文名称：Graph theory。
+图关注的是哪些点相连。把一条边画直或画弯，把两个相连顶点挪近或挪远，通常不会改变连接关系；若要表示路程或费用，则可以在边旁另标数值。
-== English overview ==
+== 读懂一张五点图 ==
-<div lang="en" class="math-english-summary">
+下面的图有 A、B、C、D、E 五个顶点。先忽略边旁的数字，从 A 出发沿线观察：可以直接去 B 或 C；B、C 都能去 D；E 只与 D 相连。金色路线展示了从 A 经 B、D 到 E 的一种走法。
-Graph theory studies relations through vertices and edges. A graph can represent roads, dependencies, friendships, or allowable moves, but the mathematical model must specify whether edges have directions, weights, or multiplicities. A drawing is only a representation: moving vertices or bending edges does not change adjacency. Graph isomorphism formalizes the idea of having the same structure after relabeling.
-This article introduces degrees, walks, paths, connectivity, trees, and Euler trails. The handshaking lemma follows by counting edge ends in two ways. Trees connect all their vertices without cycles; equivalent descriptions lead to proofs about their number of edges and their unique paths. Breadth-first search finds shortest paths in an unweighted graph because it explores vertices in increasing distance layers. Weighted shortest paths require additional assumptions and different algorithms. We work through adjacency data and a route example, distinguish traversing every edge from visiting every vertex, and explain why Euler's bridge problem represents an abstraction rather than a surveying problem. Applications also require attention to what an edge actually means: connectivity alone does not establish causation, reliability, or the feasibility of simultaneous routes.
+[[File:Gezhi-graph-path-theme.svg|frame|center|alt=五点图有边AB、AC、BD、CD和DE，金色突出ABDE路线，五条边权依次为二五二一三|顶点表示位置，线表示连接；边旁数字给出另行指定的权重。]]
-</div>
-== 先说明使用哪一种图 ==
+把顶点集合记为 V、边集合记为 E，就能将图写成 <math>G=(V,E)</math>。本例为
-简单无向图没有自环，也没有连接同一对顶点的重复边。有向图给边规定方向；加权图为边附上距离、耗时或费用等数值。不同定义会改变定理和算法的条件，例如本条的度数计数先采用简单无向图。
+<math display="block">V=\{A,B,C,D,E\},\qquad E=\{AB,AC,BD,CD,DE\}.</math>
+这里 AB 与 BA 表示同一条边，它没有方向；同一对顶点间只画一条边，也没有顶点连回自身。这种图称为'''简单无向图'''。以下关于度数、树和二分图的讨论采用有限简单无向图。
-[[File:Gezhi-graph-path.svg|frame|center|alt=五个顶点A到E构成带权图，边AB为二，AC为五，BD为二，CD为一，DE为三，路线ABDE被突出显示|从 A 到 E 的加权最短路线为 A—B—D—E，总权重 7；边权与图上画出的长度是两回事。]]
+如果道路只能单向通行，就在边上标箭头，得到'''有向图'''。如果两地之间的两座桥需要分别记录，就允许连接相同顶点的平行边，得到'''多重图'''。边旁有费用、长度等数值时，称为'''加权图'''，数值叫边权。道路在纸上交叉，只有明确标出连接顶点时才算路口。
-图中的邻接关系可用邻接表或[[矩阵]]保存。无向图的邻接矩阵对称；如果边权为零是合法的，程序应区别“没有边”和“有一条零权边”。
-== 度数与握手定理 ==
+== 度数：一共有多少个边端点 ==
-顶点的度数是与它相接的边数。每条无向边贡献两个端点，所以
+与顶点相接的边数，叫该顶点的'''度数'''，记作 <math>\deg(v)</math>。在图中，A 接 AB、AC，度数为 2；D 接 BD、CD、DE，度数为 3；E 的度数为 1。五个顶点的度数依次是
+<math display="block">2,\ 2,\ 2,\ 3,\ 1.</math>
+相加为 10，恰好是边数 5 的两倍。
+这是'''握手定理'''：
 <math display="block">\sum_{v\in V}\deg(v)=2|E|.</math>
-上图的度数依次为 <math>2,2,2,3,1</math>，总和为 10，恰好是 5 条边的两倍。由总和为偶数还可推出：奇数度顶点的个数一定为偶数。
+左侧按顶点数边的端点，右侧按边数端点。每条无向边都有两个端点，因此每条边在总和中恰好被数两次。用握手比喻，一次握手既记入一个人的握手次数，也记入另一个人的次数。
+总和是偶数。偶数度顶点的贡献本身为偶数，要使剩下的奇数度之和仍为偶数，奇数度顶点就必须有偶数个。本例恰有 D、E 两个。这条结论稍后会决定哪些顶点能成为走遍全部边的路线端点。若允许自环，一条自环的两个端点都在同一顶点，度数需计两次，握手等式才保持原意。
+== 路径与连通：怎样从一个点走到另一个点 ==
+沿着边行走得到'''游走'''，顶点和边都可以重复。如果不重复任何边，称为'''迹'''；如果不重复任何顶点，称为'''路径'''。例如 <math>A-B-D-C</math> 是路径，而 <math>D-B-A-C-D-E</math> 重复经过 D，是迹而不是路径。
+起点与终点相同、其他顶点不重复的闭合走法称为'''圈'''。简单无向图中的圈至少有三条边；本例的 <math>A-B-D-C-A</math> 是四条边组成的圈。
+若任意两顶点之间都有路径，图就'''连通'''。本例连通，但删去 DE 后，E 与其余顶点分离。删掉这样的边会破坏连通性，称它为桥。相比之下，删去 CD 后仍可以沿 <math>C-A-B-D</math> 到达 D，图仍连通。
+=== 逐层寻找最少步数 ===
+从 A 去 E 最少要走几条边？先把 A 标为第 0 层；它的邻点 B、C 是第 1 层；从 B、C 继续走，首次发现 D，放在第 2 层；再从 D 发现 E，放在第 3 层。于是最少需要 3 条边。
-== 路径、连通与树 ==
+这种逐层搜索叫'''广度优先搜索'''。每当发现一个新顶点，就记录从哪个顶点来到它；反向跟随这些记录，可以恢复一条最短路径。例如 E 从 D 发现，D 从 B 发现，B 从 A 发现，得到 <math>A-B-D-E</math>。
-游走是沿边依次行走的顶点与边序列，允许重复；迹不重复边，路径不重复顶点。圈是起终点相同、其余顶点不重复的闭合游走，在简单无向图中至少含三条边。若任意两顶点间都有路径，图称为连通图。
-有限无向图中的树是非空、连通且无圈的图。含 <math>n</math> 个顶点的树有 <math>n-1</math> 条边，而且任意两点之间的路径唯一。上图删除边 <math>CD</math> 后就成为树；原图的 <math>A-B-D-C-A</math> 是一个圈。
+逐层搜索之所以正确，是因为第 k 层的点已有长度 k 的路线。沿一条边首次到达的新点有长度 k+1 的路线；若它存在更短路线，那么在先前处理那条路线的前驱时就应已被发现。这样一层层推进，首次发现的层数恰好就是最少边数。
-可用逐次删除叶子证明树的边数公式：非平凡有限树存在度为 1 的顶点，删去它及相接边仍是树；直到只剩一个顶点、零条边，得到边数始终比顶点数少 1。
+边权不同则是另一个问题。图中 <math>A-B-D-E</math> 与 <math>A-C-D-E</math> 都有三条边，但权重分别为 <math>2+2+3=7</math> 与 <math>5+1+3=9</math>。金色路线的权重更小。处理不同边权的算法及负权情形见[[最短路径]]。
-== 两种容易混淆的“走遍” ==
+== 树：保留连接，去掉绕圈 ==
-欧拉迹要求每条边恰好经过一次，可以重复顶点；哈密顿路径要求每个顶点恰好经过一次，不要求走遍边。
+删除图中的 CD 后，所有顶点仍能互相到达，却不再有圈。'''树'''就是非空、连通且无圈的无向图。
-对至少有一条边、且所有非孤立顶点处于同一连通分量的有限无向图，存在欧拉迹当且仅当奇数度顶点为 0 个或 2 个。上图的奇数度顶点是 <math>D,E</math>，一条欧拉迹为 <math>D-B-A-C-D-E</math>。若全部度数为偶数，则可找到闭合的欧拉回路。
+树中任意两点之间只有一条路径。连通性保证至少有一条；若有两条不同路径，从它们首次分开的位置出发，沿一条走到再次相遇处，再沿另一条返回，就会围成一个圈。因此路径不能有两条。
-== 最短路需要匹配算法条件 ==
+含 n 个顶点的有限树恰有 <math>n-1</math> 条边。证明可以从“叶子”入手：叶子是度数为 1 的顶点。一棵至少有两个顶点的有限树必有叶子，因为选一条最长路径，它的端点不能再接路径外的点，否则还能延长；也不能接路径中除相邻点外的点，否则产生圈。因此最长路径的两端都是叶子。
-无权图可用广度优先搜索求最少边数路径；非负边权图可用 Dijkstra 算法求最小权重路径。上图两条简单的 <math>A</math> 到 <math>E</math> 路线分别重 <math>2+2+3=7</math> 和 <math>5+1+3=9</math>，所以选择前者。
-有负边权时不能直接照搬 Dijkstra 的正确性结论；若存在可达且能通向目标的负权回路，甚至可能没有有限最短游走。现实建模还需判断边是否有方向、是否允许重复以及费用是否随时间改变。
+删去一个叶子及其唯一相接的边，其余部分仍连通且无圈。每次顶点和边都各少一个，反复删到只剩一个顶点、零条边，便得到原来边数始终比顶点数少 1。本例删去 CD 后有 5 个顶点、4 条边，正好符合公式。
-== 读图之前：哪些信息被保留 ==
+反过来，有限 n 顶点图若连通且有 n−1 条边，也必为树。若它有圈，可以从圈上删一条边而保持连通；不断这样删，最终得到含全部顶点的一棵树，已经需要 n−1 条边。原来只有这么多边，就没有可删的多余边。只有边数而没有连通条件不够：三角形外加一个孤立点有 4 个顶点、3 条边，却不是树。
-一张公交地图会刻意改变地理距离，使线路更清楚。如果问题只是“能否换乘到达”，这种改变通常不影响答案；如果问题是“最少几分钟到达”，就必须保留边权，甚至另加换乘代价。图模型的价值来自有选择地保留关系，而不是把现实画得越像越好。把两个地点用线连接之前，应先问这条线表示道路存在、单向可走，还是在某个时间段能够通行。
-本条采用有限且非空的顶点集合。有限简单无向图可严格定义为一对集合 <math>G=(V,E)</math>，其中 <math>E\subseteq\{\{u,v\}:u,v\in V,u\ne v\}</math>。每条边是一个无序二元集合，因此没有方向、没有自环，重复列出的同一对顶点也不会形成两条边。若要研究两地之间不同的桥，就需要多重图。定义不同不是谁对谁错，而是定理中计数约定也必须一起改变；在允许自环的无向图里，自环对度数贡献二。
+== 每条边恰走一次：欧拉迹 ==
+回到未删边的原图。现在不求最快到达，而要使五条边恰好各经过一次。路线
+<math display="block">D-B-A-C-D-E</math>
+正好依次经过 DB、BA、AC、CD、DE，每条一次。这样的迹称为'''欧拉迹'''；若最后回到起点，称为'''欧拉回路'''。
-两个图同构，是存在顶点间的双射，恰好保持相邻与不相邻的关系。同构图必有相同顶点数、边数和度数序列，但反过来不成立。例如六边形圈与两个互不相连的三角形都有六个顶点、六条边，每点度数都是二；前者连通，后者不连通，所以不可能同构。这是“不变量可以排除同构，却未必足以证明同构”的具体例子。
+下面把这条走法按 1 到 5 标出。箭头只记录本次行走方向，原图的边仍是无向边；边旁数字现在是经过次序，不是前图的费用。沿箭头走完，D 虽被再次经过，每条边却都恰好使用一次。
-== 邻接表、矩阵和一次可核对的搜索 ==
+[[File:Gezhi-teaching-foundation-graph-euler.svg|frame|center|alt=五点图的五条边按D到B到A到C到D到E标出方向和一至五的次序，D和E以双圈突出|欧拉迹允许重复顶点；两个奇数度顶点 D、E 成为开放路线的端点。]]
-以配图为例，忽略边权时邻接表为：A 接 B、C；B 接 A、D；C 接 A、D；D 接 B、C、E；E 只接 D。按 A、B、C、D、E 排列，邻接矩阵是
-<math display="block">M=\begin{pmatrix}0&1&1&0&0\\1&0&0&1&0\\1&0&0&1&0\\0&1&1&0&1\\0&0&0&1&0\end{pmatrix}.</math>
-矩阵对称来自边无方向，零对角来自没有自环。矩阵平方的 <math>(i,j)</math> 元素计算从 i 到 j 的长度二游走数，因为 <math>(M^2)_{ij}=\sum_kM_{ik}M_{kj}</math>，每个中间顶点 k 对应一种两步走法。例如从 A 到 D 可经 B 或 C，共有两种；这不是说有两条直接连接 A、D 的边。
-从 A 开始做广度优先搜索，先标记 A 的距离为零；下一层发现 B、C，距离为一；再从它们的邻居发现 D，距离为二；最后发现 E，距离为三。已发现的顶点不重复入队。正确性的理由是：所有距离至多 k 的顶点处理完以后，下一批新发现点都有一条长度 k+1 的路径；若其中某点另有更短路径，它应在前面的层中被发现，构成矛盾。这一论证依赖每条边成本都按一步计算。
+起点为何选 D，终点为何选 E？沿路线经过一个中途顶点时，每次进入都要配一次离开，因此所用的边成对出现。走完全部边后，中途顶点的度数为偶数；开放路线的起点和终点各多一次离开或进入，度数为奇数。因此一条欧拉迹若不闭合，两个端点恰好就是两个奇数度顶点。
-用邻接表实现时，每个顶点入队至多一次，每条无向边检查两端各一次，时间量级为 <math>O(|V|+|E|)</math>。邻接矩阵便于常数时间查询两点是否相邻，却可能需要扫描大量零元素。选择数据结构也要与问题规模相配。若边有不同耗时，搜索得到的最少换乘站数不一定是最少耗时，详细算法见[[最短路径]]。
+完整判据为：有限无向图至少有一条边，且所有非孤立顶点相互连通时，有欧拉迹当且仅当奇数度顶点有 0 个或 2 个。零个时可以闭合，两个时必须以这两点为端点。
-== 为什么树只有一条连接路径 ==
+=== 为什么奇偶条件也足以构造路线 ===
-树的两个条件分别排除两类问题：“连通”排除无法到达，“无圈”排除多余绕行。若同两点之间有两条不同的简单路径，从它们首次分开的位置沿一条走到再次相遇处，再沿另一条返回，就组成一个圈，与定义矛盾。因此路径唯一。反过来，若任意两点间有且仅有一条简单路径，就既连通又不可能有圈，因而是树。
+先设所有度数都为偶数。从一个有边的顶点出发，每次选择尚未使用的边，直到无法继续。若走到起点以外的某点，先前每次进入和离开都成对，当前这次进入又使用了一条边；既然总度数为偶数，就还会剩下一条未用边可以离开。因此走法不会停在其他点，只能回到起点，形成一条闭合迹。
-前述删叶证明还需要解释叶子为什么存在。取有限树中一条最长简单路径。如果它的一个端点还接着路径外顶点，就能把路径延长；如果接着路径中除相邻点外的顶点，就产生圈。因此非平凡树的两个端点都是叶子。这里“有限”保证可以选到最长路径，不能不加说明地把论证套到无限图。
+若还有边没用，由连通性，当前闭合迹上必有某点与未用边相接。从这个点再次沿未用边行走：已用的闭合迹在每点消耗偶数条边，剩下的度数仍为偶数，故又能得到一条闭合迹。将它插入原迹，再继续处理剩余边。边数有限，这个过程最终用完全部边。
-树还有实用的等价判据：有限 n 顶点无向图若连通且有 n−1 条边，就是树。证明可从任意连通图逐条删去圈上的边：删这种边不破坏连通性，最终得到一棵含全部顶点的树，已有 n−1 条边。因此原图若恰好这么多边，就无边可删。注意只有边数条件不够：一个三角形再加一个孤立顶点，有四点三边，却不是树。
+若只有两个奇数度顶点，先在它们之间加一条临时边，使度数都变偶数，构造欧拉回路后去掉临时边，即得到所需开放迹。原来已有连接边时，临时边与它平行，需要将两条边分别识别；上述配对论证同样适用于这种多重图。
-== 欧拉迹判据背后的配对思想 ==
+若在配图中再加 BE，B 的度数从 2 变 3，E 从 1 变 2，D 仍为 3。新图仍有欧拉迹，但两个端点改成 B、D。A 为偶数度，不能作为这种开放迹的起点。
-一条遍历每条边一次的行走，在不是起点、终点的顶点处，每次进入都必须配一次离开，因此相关边成对出现，度数为偶数。若起点与终点不同，它们各留下一个未配对的进入或离开，度数为奇数。这证明了奇数度顶点只能有零个或两个的必要性，却还没有证明这样的路线一定能构造出来。
-对所有非孤立顶点连通、全部度数为偶数的图，从有边的顶点出发沿尚未使用的边走，直到不能继续。除起点外，某点一旦被进入而用边总数尚为奇数，就还有一条边可离开，所以最后只能回到起点。若还有未用边，连通性保证当前闭合路线上的某点与未用部分相接，从那里另走一个闭合路线，把它插入原路线。边数有限，重复后用完所有边。若恰有两个奇数度顶点，先在两者间临时增加一条可单独识别的边；若已有连接边，临时允许平行边。上述配对与拼接证明同样适用于这种多重图。按偶数情形构造回路，再去掉临时边即可得到所需迹。这补上了充分性的构造理由。
+'''哈密顿路径'''则要求每个顶点恰好经过一次，不要求用完所有边。例如 <math>B-A-C-D-E</math> 是本例的一条哈密顿路径。两种“走遍”分别约束边和顶点，问题不同。
-== 二分图把奇圈变成可检查的障碍 ==
+== 把顶点分成两组：二分图 ==
-如果顶点能分成两个互不相交的集合，且每条边都连接两个不同集合中的顶点，图称为二分图。两组可以代表任务与执行者、学生与课程等不同类型对象；同组内部没有边。配图就是二分图，一种划分为 <math>\{A,D\}</math> 与 <math>\{B,C,E\}</math>。逐条检查五条边，都跨越这两组。
+将配图顶点分为 <math>\{A,D\}</math> 与 <math>\{B,C,E\}</math>。检查每条边，AB、AC、BD、CD、DE 都跨越两组，没有边连接同组内的两个点。能够这样分组的图叫'''二分图'''。
-有限无向图是二分图，当且仅当它没有奇数长度的圈。必要性来自沿边交替换组：每走一步都会从一组换到另一组，要回到起点就必须走偶数步。三角形因此不可能二分，不论怎样重新画或给顶点改名都无法解决这一障碍。
+二分图中的圈只能有偶数条边：每走一步都会换到另一组，回到原来一组必须走偶数步。因此三角形无法二分。反过来，有限无向图只要没有奇数长度的圈，就能分成两组。
-充分性可对每个连通分量做广度优先搜索，按从起点出发的最短距离奇偶性分组。假设有一条边连接同奇偶层的两个顶点，把它与搜索树中连接这两点的唯一路径合起来，就形成奇圈：树中路径长度为两端深度之和减去公共祖先深度的两倍，是偶数，再加这条边成为奇数。不存在奇圈便排除了这种冲突，所有边都跨组，从而完成构造。
+可以用广度优先搜索证明反向结论。对每个连通部分选一个起点，把距离为偶数的顶点放一组，奇数的放另一组。若有一条边连接同组两点，它们在搜索树中的深度同奇偶。从一端沿树走到两条根路径最后的共同点，再走到另一端，这条树路径长度为“两端深度之和减去共同深度的两倍”，所以为偶数。加上这条连接边，就围成奇圈，与假设矛盾。因此所有边都跨组。
-这个证明给出一个实际判定方法：搜索时交替染两种颜色，若发现相邻顶点已被染成同色，就能沿搜索树追出一个奇圈作为失败证据；若没有冲突，则所得分组本身就是成功证据。连通分量不止一个时，应在每个尚未访问的分量重新开始，而不能只检查从一个起点能到达的部分。
+本例从 A 搜索，偶数层为 A、D，奇数层为 B、C、E，正得到前面的划分。若图不连通，对每个尚未访问的部分分别开始搜索即可。
-二分性与欧拉迹不是同一条件。一个四边形圈既二分又有欧拉回路；一个三角形有欧拉回路却不是二分图；一棵有三个叶子的星形树是二分图，却有四个奇数度顶点，因此没有遍历全部边一次的迹。把这些小例子并列，可以看出“每点度数奇偶”与“圈长奇偶”在检查不同的结构。
+二分性看圈的长度，欧拉迹看顶点的度数，两者不同。三角形每点度数为 2，有欧拉回路，却不是二分图；一个中心连接三个叶子的星形树可以二分，却有四个奇数度顶点，没有欧拉迹。
-== 历史：从桥的长度转向连接关系 ==
+== 怎样记录同一张图 ==
-欧拉在十八世纪研究柯尼斯堡七桥问题，把陆地看作顶点、桥看作边，关键不在每座桥有多长，而在各块陆地连接着多少座桥。相关论文现存于 [https://scholarlycommons.pacific.edu/euler-works/53/ Euler Archive，E53]，档案标示撰写时间为 1735 年、出版时间为 1741 年。这个例子通常被用作图论早期发展的标志，不能据此说所有关于网络的思想由某一个人同时发明。[https://mathshistory.st-andrews.ac.uk/HistTopics/Topology_in_mathematics/ 圣安德鲁斯大学的历史综述]把这一问题放在后来拓扑观念发展的背景中。
+按 A、B、C、D、E 排列顶点，用 1 表示相邻、0 表示不相邻，可以写出邻接[[矩阵]]：
+<math display="block">M=\begin{pmatrix}
+&1&1&0&0\\1&0&0&1&0\\1&0&0&1&0\\0&1&1&0&1\\0&0&0&1&0
+\end{pmatrix}.</math>
+例如第一行在 B、C 两列为 1，记录 A 的两个邻点。无向性使矩阵对称，没有自环使对角线为零。
-图论在后续发展中与地图着色、化学结构、组合计数和计算机算法相互促进。现代“图”这个术语包含一大批不同结构，图算法也不等于早期七桥问题的直接重述。阅读历史时应区分：一项著名问题、某个定理的证明、学科术语的形成，以及算法作为可执行步骤的提出，往往不是同一时刻发生。
+矩阵乘法还可以数两步游走。<math>(M^2)_{ij}=\sum_kM_{ik}M_{kj}</math> 中，每个中间顶点 k 对应一条“先从 i 到 k，再从 k 到 j”的可能走法。例如 A 到 D 可以经过 B 或 C，所以对应元素为 2。
-== 应用中的边界与误解 ==
+也可以只给每个顶点列出邻点，称为邻接表。搜索时每个顶点只需首次发现时入队，每条无向边从两端各检查一次，因此广度优先搜索的时间量级为 <math>O(|V|+|E|)</math>。
-道路图可问最短路，施工依赖图可问先后顺序，任务分配图可问配对；同一网络并不总能用同一指标评价。“平均度数大”不保证每个点都有替代路线，一座桥边仍可能把全图分成两部分。单独求每辆车的最短路线也不能保证总交通最优，因为拥堵使边权依赖其他车辆选择。
-图上的交叉不自动是路口，平面性要求存在一种没有边内部交叉的画法，而不是当前草图恰好没有交叉。欧拉迹与哈密顿路径的相似名称也不能掩盖问题差异：前者限制边，后者限制顶点，奇偶度判据不能直接拿来判断后者。社交图中的相关连接更不能单凭结构推断因果机制。
+若给顶点改名或重画位置，却能一一对应地保留相邻关系，两张图称为'''同构'''。相同度数序列还不足以证明同构：六边形圈与两个分开的三角形都有 6 个顶点、6 条边，每点度数均为 2，但前者连通，后者不连通。
-== 改变一条边后的端点核验 ==
+== 历史 ==
-给上图再加边 BE，可以重新计算奇数度顶点并检查欧拉迹的端点。B 从二变三，E 从一变二，D 仍为三，因而奇数度顶点变成 B、D，仍存在以它们为端点的欧拉迹。若问“还能否从 A 出发用完每条边一次”，答案却是否，因为 A 不是允许的开放迹端点。这说明存在性与指定端点存在性是两个问题。
+欧拉研究柯尼斯堡七桥问题时，以陆地区域和桥的连接替代具体的地理形状。能否每座桥恰过一次，取决于连接和度数，而不是桥的实际长度。原论文收录于 [https://scholarlycommons.pacific.edu/euler-works/53/ Euler Archive，E53]，档案标示撰写时间为 1735 年、出版时间为 1741 年。
-== 编者评注（AI 辅助） ==
+这一问题是图论早期发展的重要例子。此后，地图着色、化学分子结构、组合计数及计算机网络等问题不断扩展图论的研究范围。[https://mathshistory.st-andrews.ac.uk/HistTopics/Topology_in_mathematics/ MacTutor 的历史综述]介绍了七桥问题与拓扑观念发展的联系。
-<div class="math-editorial-note"> 学图论容易把注意力全放在画线技巧上。更有用的训练是把同一个例子依次改写为边集合、邻接表和搜索过程，并说明每次改写保留了什么信息。建议先掌握双重计数与树的等价条件，再读复杂算法；它们把看似直观的图形判断转化成可以逐步检查的论证，也能及时发现现实模型中漏掉的方向、容量和时间条件。</div>
-== 参考来源与延伸阅读 ==
+== 参考资料 ==
-* [https://discrete.openmathbooks.org/dmoi3/sec_gt-intro.html Oscar Levin：图的定义与同构]，作者开放教材。
+* [https://discrete.openmathbooks.org/dmoi3/sec_gt-intro.html Oscar Levin：图的定义与同构]。
-* [https://mathshistory.st-andrews.ac.uk/HistTopics/Topology_in_mathematics/ MacTutor：拓扑观念发展的历史]，用于七桥问题的历史背景。
+* [https://discrete.openmathbooks.org/dmoi3.html Oscar Levin，Discrete Mathematics: An Open Introduction，第 4 章]：图、树和欧拉迹。
-* [https://discrete.openmathbooks.org/dmoi3.html Oscar Levin，《Discrete Mathematics: An Open Introduction》第 4 章]：图、树、欧拉迹。
+* [https://scholarlycommons.pacific.edu/euler-works/53/ Euler Archive，E53]。
-* [[组合数学]] · [[矩阵]] · [[优化]]
+* [https://mathshistory.st-andrews.ac.uk/HistTopics/Topology_in_mathematics/ MacTutor：拓扑观念发展的历史]。
+* 相关条目：[[最短路径]]、[[组合数学]]、[[矩阵]]、[[优化]]。
 [[分类:离散数学]]