查看“︁图论”︁的源代码

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

英文名称：Graph theory。

== English overview ==
<div lang="en" class="math-english-summary">
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.
</div>

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

[[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 的正确性结论；若存在可达且能通向目标的负权回路，甚至可能没有有限最短游走。现实建模还需判断边是否有方向、是否允许重复以及费用是否随时间改变。

== 读图之前：哪些信息被保留 ==
一张公交地图会刻意改变地理距离，使线路更清楚。如果问题只是“能否换乘到达”，这种改变通常不影响答案；如果问题是“最少几分钟到达”，就必须保留边权，甚至另加换乘代价。图模型的价值来自有选择地保留关系，而不是把现实画得越像越好。把两个地点用线连接之前，应先问这条线表示道路存在、单向可走，还是在某个时间段能够通行。

本条采用有限且非空的顶点集合。有限简单无向图可严格定义为一对集合 <math>G=(V,E)</math>，其中 <math>E\subseteq\{\{u,v\}:u,v\in V,u\ne v\}</math>。每条边是一个无序二元集合，因此没有方向、没有自环，重复列出的同一对顶点也不会形成两条边。若要研究两地之间不同的桥，就需要多重图。定义不同不是谁对谁错，而是定理中计数约定也必须一起改变；在允许自环的无向图里，自环对度数贡献二。

两个图同构，是存在顶点间的双射，恰好保持相邻与不相邻的关系。同构图必有相同顶点数、边数和度数序列，但反过来不成立。例如六边形圈与两个互不相连的三角形都有六个顶点、六条边，每点度数都是二；前者连通，后者不连通，所以不可能同构。这是“不变量可以排除同构，却未必足以证明同构”的具体例子。

== 邻接表、矩阵和一次可核对的搜索 ==
以配图为例，忽略边权时邻接表为：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 的路径；若其中某点另有更短路径，它应在前面的层中被发现，构成矛盾。这一论证依赖每条边成本都按一步计算。

用邻接表实现时，每个顶点入队至多一次，每条无向边检查两端各一次，时间量级为 <math>O(|V|+|E|)</math>。邻接矩阵便于常数时间查询两点是否相邻，却可能需要扫描大量零元素。选择数据结构也要与问题规模相配。若边有不同耗时，搜索得到的最少换乘站数不一定是最少耗时，详细算法见[[最短路径]]。

== 为什么树只有一条连接路径 ==
树的两个条件分别排除两类问题：“连通”排除无法到达，“无圈”排除多余绕行。若同两点之间有两条不同的简单路径，从它们首次分开的位置沿一条走到再次相遇处，再沿另一条返回，就组成一个圈，与定义矛盾。因此路径唯一。反过来，若任意两点间有且仅有一条简单路径，就既连通又不可能有圈，因而是树。

前述删叶证明还需要解释叶子为什么存在。取有限树中一条最长简单路径。如果它的一个端点还接着路径外顶点，就能把路径延长；如果接着路径中除相邻点外的顶点，就产生圈。因此非平凡树的两个端点都是叶子。这里“有限”保证可以选到最长路径，不能不加说明地把论证套到无限图。

树还有实用的等价判据：有限 n 顶点无向图若连通且有 n−1 条边，就是树。证明可从任意连通图逐条删去圈上的边：删这种边不破坏连通性，最终得到一棵含全部顶点的树，已有 n−1 条边。因此原图若恰好这么多边，就无边可删。注意只有边数条件不够：一个三角形再加一个孤立顶点，有四点三边，却不是树。

== 欧拉迹判据背后的配对思想 ==
一条遍历每条边一次的行走，在不是起点、终点的顶点处，每次进入都必须配一次离开，因此相关边成对出现，度数为偶数。若起点与终点不同，它们各留下一个未配对的进入或离开，度数为奇数。这证明了奇数度顶点只能有零个或两个的必要性，却还没有证明这样的路线一定能构造出来。

对所有非孤立顶点连通、全部度数为偶数的图，从有边的顶点出发沿尚未使用的边走，直到不能继续。除起点外，某点一旦被进入而用边总数尚为奇数，就还有一条边可离开，所以最后只能回到起点。若还有未用边，连通性保证当前闭合路线上的某点与未用部分相接，从那里另走一个闭合路线，把它插入原路线。边数有限，重复后用完所有边。若恰有两个奇数度顶点，先在两者间临时增加一条可单独识别的边；若已有连接边，临时允许平行边。上述配对与拼接证明同样适用于这种多重图。按偶数情形构造回路，再去掉临时边即可得到所需迹。这补上了充分性的构造理由。

== 二分图把奇圈变成可检查的障碍 ==
如果顶点能分成两个互不相交的集合，且每条边都连接两个不同集合中的顶点，图称为二分图。两组可以代表任务与执行者、学生与课程等不同类型对象；同组内部没有边。配图就是二分图，一种划分为 <math>\{A,D\}</math> 与 <math>\{B,C,E\}</math>。逐条检查五条边，都跨越这两组。

有限无向图是二分图，当且仅当它没有奇数长度的圈。必要性来自沿边交替换组：每走一步都会从一组换到另一组，要回到起点就必须走偶数步。三角形因此不可能二分，不论怎样重新画或给顶点改名都无法解决这一障碍。

充分性可对每个连通分量做广度优先搜索，按从起点出发的最短距离奇偶性分组。假设有一条边连接同奇偶层的两个顶点，把它与搜索树中连接这两点的唯一路径合起来，就形成奇圈：树中路径长度为两端深度之和减去公共祖先深度的两倍，是偶数，再加这条边成为奇数。不存在奇圈便排除了这种冲突，所有边都跨组，从而完成构造。

这个证明给出一个实际判定方法：搜索时交替染两种颜色，若发现相邻顶点已被染成同色，就能沿搜索树追出一个奇圈作为失败证据；若没有冲突，则所得分组本身就是成功证据。连通分量不止一个时，应在每个尚未访问的分量重新开始，而不能只检查从一个起点能到达的部分。

二分性与欧拉迹不是同一条件。一个四边形圈既二分又有欧拉回路；一个三角形有欧拉回路却不是二分图；一棵有三个叶子的星形树是二分图，却有四个奇数度顶点，因此没有遍历全部边一次的迹。把这些小例子并列，可以看出“每点度数奇偶”与“圈长奇偶”在检查不同的结构。

== 历史：从桥的长度转向连接关系 ==
欧拉在十八世纪研究柯尼斯堡七桥问题，把陆地看作顶点、桥看作边，关键不在每座桥有多长，而在各块陆地连接着多少座桥。相关论文现存于 [https://scholarlycommons.pacific.edu/euler-works/53/ Euler Archive，E53]，档案标示撰写时间为 1735 年、出版时间为 1741 年。这个例子通常被用作图论早期发展的标志，不能据此说所有关于网络的思想由某一个人同时发明。[https://mathshistory.st-andrews.ac.uk/HistTopics/Topology_in_mathematics/ 圣安德鲁斯大学的历史综述]把这一问题放在后来拓扑观念发展的背景中。

图论在后续发展中与地图着色、化学结构、组合计数和计算机算法相互促进。现代“图”这个术语包含一大批不同结构，图算法也不等于早期七桥问题的直接重述。阅读历史时应区分：一项著名问题、某个定理的证明、学科术语的形成，以及算法作为可执行步骤的提出，往往不是同一时刻发生。

== 应用中的边界与误解 ==
道路图可问最短路，施工依赖图可问先后顺序，任务分配图可问配对；同一网络并不总能用同一指标评价。“平均度数大”不保证每个点都有替代路线，一座桥边仍可能把全图分成两部分。单独求每辆车的最短路线也不能保证总交通最优，因为拥堵使边权依赖其他车辆选择。

图上的交叉不自动是路口，平面性要求存在一种没有边内部交叉的画法，而不是当前草图恰好没有交叉。欧拉迹与哈密顿路径的相似名称也不能掩盖问题差异：前者限制边，后者限制顶点，奇偶度判据不能直接拿来判断后者。社交图中的相关连接更不能单凭结构推断因果机制。

== 改变一条边后的端点核验 ==
给上图再加边 BE，可以重新计算奇数度顶点并检查欧拉迹的端点。B 从二变三，E 从一变二，D 仍为三，因而奇数度顶点变成 B、D，仍存在以它们为端点的欧拉迹。若问“还能否从 A 出发用完每条边一次”，答案却是否，因为 A 不是允许的开放迹端点。这说明存在性与指定端点存在性是两个问题。

== 编者评注（AI 辅助） ==
<div class="math-editorial-note"> 学图论容易把注意力全放在画线技巧上。更有用的训练是把同一个例子依次改写为边集合、邻接表和搜索过程，并说明每次改写保留了什么信息。建议先掌握双重计数与树的等价条件，再读复杂算法；它们把看似直观的图形判断转化成可以逐步检查的论证，也能及时发现现实模型中漏掉的方向、容量和时间条件。</div>

== 参考来源与延伸阅读 ==
* [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 章]：图、树、欧拉迹。
* [[组合数学]] · [[矩阵]] · [[优化]]
[[分类:离散数学]]