图论语言：图、度数、路径与连通性

上一章把一整列计数装进生成函数，又把计数放进样本空间变成概率。现在我们换一个问题：对象之间怎样连接？

这一步看起来像换了学科，其实前面练过的工具都还在。集合用来装顶点和边，二元关系可以直接画成有向图，双计数会变成握手定理，等价关系会把图切成连通分量，归纳法则会在“删一条边，再把它加回来”时反复出现。图论不是把这些内容放下，而是给它们一个共同的活动场地。

图论最容易让人误会的地方，是图画得太直观。点摆在哪里、线画得长还是短，往往都不重要；真正被保留下来的，是“哪些对象被当成顶点，哪些顶点之间有边”。因此，学这章时别急着看图像不像地图，先把两个问题说清楚：

• 顶点代表什么？
• 边代表什么关系？

只要这两句话没有说清，后面的度数、路径和连通性都没有确定含义。

---

从现实关系得到 $G=(V,E)$

一个无向图通常写成

$$G=(V,E).$$

$V$ 是顶点集合，$E$ 是边集合。若 $u,v\in V$，无向边写成 $\{u,v\}$。它是一个二元集合，所以

$$\{u,v\}=\{v,u\}.$$

这正好表达“方向不重要”。城市 $u$ 与城市 $v$ 之间有双向道路，和城市 $v$ 与城市 $u$ 之间有双向道路，说的是同一条连接。

图的顶点数 $|V|$ 常叫图的阶，边数 $|E|$ 常叫图的大小。为了少写符号，也常记

$$n=|V|, \qquad m=|E|.$$

数学上，一张图的全部信息就在 $V$ 和 $E$ 里。把同一批顶点拖到别的位置，把直线画成曲线，甚至让两条边在纸面上交叉，都不会改变这两个集合。

一次建模要做四个决定

把现实问题翻成图时，可以按下面的顺序检查。

例如，把课程看成顶点，当两门课不能安排在同一考试时段时连边，就得到冲突图。这个模型里边是对称关系，所以用无向图。把课程先修要求建模时，若课程 $A$ 必须先于课程 $B$ 修读，就画箭头 $A\to B$；方向在这里是问题的一部分。

简单图、多重图和有向图的边界

简单无向图满足两条限制：

1. 不允许自环，也就是没有 $\{v,v\}$ 这样的边。
2. 同一对不同顶点之间至多有一条边。

因此，简单图的边集合可以写成

$$E\subseteq \bigl\{\{u,v\}\mid u,v\in V,\ u\ne v\bigr\}.$$

多重图允许同一对顶点之间有多条平行边。不同课程对“多重图”是否允许自环的约定并不完全一致，所以遇到多重图时，应把“能否有自环”单独说明。地铁站之间有两条不同线路、两台服务器之间有多条独立电缆，都适合用平行边保留连接的重数。

有向图的边是有序对。箭头

$$(u,v)$$

从 $u$ 出发，在 $v$ 结束。一般来说，

$$(u,v)\ne(v,u).$$

前面学过二元关系以后，有向图其实很熟悉：定义在 $V$ 上的二元关系就是 $V\times V$ 的一个子集，而这恰好可以看成一组从一个顶点指向另一个顶点的箭头。

有向图里的入度和出度

有向图中，一个顶点有两种度数：

• 入度 $\deg^-(v)$ 是指向 $v$ 的边数；
• 出度 $\deg^+(v)$ 是从 $v$ 发出的边数。

一条有向自环从 $v$ 发出又回到 $v$，所以它给 $\deg^-(v)$ 和 $\deg^+(v)$ 各贡献 $$。

把所有顶点的入度相加，每条箭头会在自己的箭头端被数一次；把所有顶点的出度相加，每条箭头会在自己的箭尾端被数一次。因此

$$\sum_{v\in V}\deg^-(v) = \sum_{v\in V}\deg^+(v) = |E|.$$

这和后面无向图的握手定理是同一个双计数思想，只是无向边有两个不分方向的端点，而有向边有一个箭尾和一个箭头。

先做一次模型翻译

某城市要研究地铁网络。若把车站当作顶点，应怎样定义边？

答案取决于问题。若只问“两个车站之间是否有一段直达区间”，可以在相邻车站之间连无向边。若上下行都存在但只关心可达性，仍可用无向图。若某些区间只能单向运行，就要用有向图。若两站之间有两条线路，而我们想分别记录每条线路，就要用多重图。

这里没有脱离问题的“唯一正确画法”。正确模型的标准，是它保留了回答目标问题所需的信息，又没有塞进无关细节。

---

邻接、关联与同构：画法不是结构

若简单图中有边 $\{u,v\}$，就说顶点 $u$ 与 $v$ 邻接。也说边 $\{u,v\}$ 与它的两个端点 $u,v$ 关联。

“邻接”描述顶点和顶点的关系，“关联”描述边和顶点的关系。这两个词很像，但对象不同：

• 可以说“顶点 $u$ 与顶点 $v$ 邻接”；
• 可以说“边 $\{u,v\}$ 与顶点 $u$ 关联”。

图画得再复杂，这两类关系仍由边集合准确决定。

同一张结构可以画得完全不像

设 $G$ 与 $H$ 是两个简单图。如果存在一个双射

$$f:V(G)\to V(H)$$

使任意 $u,v\in V(G)$ 都满足

$$\{u,v\}\in E(G) \quad\Longleftrightarrow\quad \{f(u),f(v)\}\in E(H),$$

就说 $G$ 与 $H$ 同构。

这一定义可以读成一句人话：把顶点重新命名以后，边与非边都完全对得上。图的几何外观可以改变，连接结构不能改变。

第一次判断同构时，很多人会盯着图旋转。更稳的思路是先找不变量，也就是同构后一定保持的性质：

• 顶点数相同；
• 边数相同；
• 各度数出现的次数相同；
• 连通分量个数相同；
• 是否有回路相同；
• 对应顶点之间的邻接关系相同。

例如，一个图的度数多重集是

$$\{1,1,2,2,2,2\},$$

另一个图的度数多重集是

$$\{1,1,1,3,3,3\}.$$

它们不可能同构。这个结论不需要尝试任何顶点配对，因为同构会保持每个顶点的度数。

反过来，度数序列相同还不能保证同构。度数只是结构的一张“摘要”，不同连接方式可能产生同一张摘要。要证明两个图同构，最终仍要给出一个保持邻接的双射；要证明不同构，只需找到一个被同构保持、但两图取值不同的性质。

几类常见图

有些连接结构会反复出现，所以有固定名字。

完全图 $K_n$ 有 $n$ 个顶点，每对不同顶点之间都有边。每个顶点的度数都是 $n-1$，边数是

$$|E(K_n)|=\binom{n}{2}=\frac{n(n-1)}{2}.$$

这个公式既可以用组合数理解：从 $n$ 个顶点中选两个作为边的端点；也可以等到握手定理后再算：度数总和是 $n(n-1)$，每条边被数两次。

空图有顶点而没有边，因此每个顶点的度数都是 $0$。不要把空图和空集混在一起：一个有 $n$ 个顶点的空图仍有 $n$ 个顶点，只是边集为空。

路径图 $P_n$ 把 $n$ 个顶点排成一条链。$n\ge2$ 时，两端顶点度数为 $1$，中间顶点度数为 $2$，边数为 $n-1$。

圈图 $C_n$ 把 $n$ 个顶点首尾接成一个圈，其中 $n\ge3$。每个顶点度数为 $2$，边数为 $n$。

这些名字说的是同构类型，不是在规定画法。$C_5$ 可以画成正五边形，也可以画成一条扭曲的闭合线；只要邻接关系相同，它们就是同一个结构意义下的圈图。

子图、生成子图与诱导子图

若

$$H=(V_H,E_H)$$

满足

$$V_H\subseteq V(G), \qquad E_H\subseteq E(G),$$

并且 $E_H$ 中每条边的端点都在 $V_H$ 中，就说 $H$ 是 $G$ 的子图。删掉顶点时，与它关联的边也必须删掉；不能留下没有端点的边。

若子图保留原图全部顶点，即

$$V_H=V(G),$$

就叫生成子图。它只从原图中删边。下一章的“生成树”正是这种对象：顶点一个不少，只挑出足以维持连通的一部分边。

还有一种常用选择叫诱导子图。给定顶点子集 $S\subseteq V(G)$，诱导子图 $G[S]$ 不但保留 $S$ 中的顶点，还要保留原图中两个端点都在 $S$ 内的所有边。普通子图可以少选边，诱导子图不能随意漏掉 $S$ 内部原本存在的边。

---

度数：从端点做一次双计数

在简单无向图中，顶点 $v$ 的度数 $\deg(v)$ 是与 $v$ 关联的边数。因为简单图没有自环和平行边，它也等于与 $v$ 邻接的顶点数。

这两个说法在多重图中不能随便互换。若 $u$ 与 $v$ 之间有三条平行边，$v$ 只多了一个邻接顶点，却多了三条关联边。若允许自环，则一个无向自环在同一顶点上有两个端点，所以按标准约定对该顶点的度数贡献 $2$。

没有任何关联边的顶点叫孤立顶点，度数为 $0$。只有一条关联边的顶点常叫叶顶点，度数为 $1$；下一章研究树时，叶顶点会频繁出现。

下面的工具可以切换路径图、圈图、星图和完全图，也可以自己添加或删除边。每改一条边，先预测哪两个度数会变化，再看统计结果。

握手定理从哪里来

设 $G=(V,E)$ 是有限无向图。把所有顶点的度数相加，得到

$$\sum_{v\in V}\deg(v)=2|E|.$$

这叫握手定理。公式并不神秘，它只是在用两种方式数同一批“边端”。

握手定理也是一次典型的双计数。前面的组合计数中，我们常通过“先选谁、再选谁”数同一批对象；这里改成“从边看端点”和“从顶点看关联边”，方法没有变。

奇度顶点为什么成双出现

握手定理右边是偶数，所以度数总和必为偶数。偶度顶点的度数相加仍为偶数，于是奇度顶点的度数之和也必须是偶数。

奇数个奇数相加是奇数，偶数个奇数相加是偶数。因此：

$$\text{有限无向图中的奇度顶点个数一定是偶数。}$$

这个结论比公式本身更常被拿来快速排除不可能情况。比如有人声称一张图恰好有 $3$ 个奇度顶点，我们不用知道图怎样画，就能断定它不存在。

下面的验证器会逐条加入边。注意每次加边时，两个端点的奇偶性都会翻转：偶数变奇数，奇数变偶数。奇度顶点的个数可能增 $2$、减 $2$ 或不变，但不会从偶数变成奇数。

平均度与边数

若 $n=|V|>0$，图的平均度是

$$\frac{1}{n}\sum_{v\in V}\deg(v).$$

代入握手定理得到

$$\text{平均度}=\frac{2|E|}{|V|}=\frac{2m}{n}.$$

因此知道顶点数和平均度就能恢复边数。例如，某简单无向图有 $12$ 个顶点，平均度为 $3$，那么

$$|E|=\frac{12\cdot3}{2}=18.$$

平均度不必是整数，因为它是全体顶点度数的平均值，而不是某个实际顶点的度数。

必要条件不等于充分条件

考虑度数序列

$$1,2,2,4,4,4.$$

总和为 $17$，违反握手定理，所以它不可能来自任何无向图。

但“总和为偶数”只是一条必要条件，并不足以保证一个序列能画成简单图。例如，四个顶点的简单图里，任何顶点的度数都不超过 $3$，所以

$$4,2,1,1$$

虽然总和是 $8$，仍不可能成为四顶点简单图的度数序列。

练习：一个简单无向图有 $7$ 个顶点，其中六个顶点的度数分别是 $1,2,2,3,3,4$。最后一个顶点的度数可能是 $2$ 吗？

查看参考答案

不可能。已知六个度数之和为 $15$。若最后一个度数是 $2$，总和就是 $17$，与握手定理要求的偶数矛盾。最后一个顶点的度数必须为奇数，但这仍只是必要条件。

---

走法、迹、路与回路

一条边只告诉我们能不能直接走一步。要描述从一个顶点经过若干条边到另一个顶点，就需要一串顶点和边。

严格地说，一条长度为 $k$ 的走法，也常叫游走，是交替序列

$$v_0,e_1,v_1,e_2,\ldots,e_k,v_k,$$

其中每条 $e_i$ 都连接相邻的 $v_{i-1}$ 与 $v_i$。在简单图中，相邻顶点唯一确定边，所以常把它简写成

$$v_0,v_1,\ldots,v_k.$$

长度数的是走过的边，不是写出的顶点。因此这条走法的长度是 $k$，而顶点在序列中出现了 $k+1$ 次。

四个限制逐级加严

中文术语在不同课程中会有细微差异，本章固定采用下面的约定：

• 走法或游走允许重复顶点，也允许重复边。
• 迹不允许重复边，但可以重复顶点。
• 路或简单路径不允许重复顶点，因此也不会重复边。
• 闭走法的起点和终点相同。
• 闭迹是起点和终点相同、且不重复边的迹，也常叫回路。
• 圈或简单回路的首尾相同，除首尾是同一个顶点外，其余顶点互不重复。

简单无向图中的圈长度至少为 $3$。沿同一条无向边走过去再走回来，虽然得到长度为 $2$ 的闭走法，却把同一条边用了两次，不是闭迹，也不算圈。

为什么要把术语分这么细？因为不同问题禁止的重复不同。送货员可以再次经过同一个路口，却可能要求每段道路只检查一次；这要找的是迹。若要求途中不回到任何旧地点，才是在找简单路径。

用同一张小图分类

设简单图的边集是

$$E=\{\{a,b\},\{b,c\},\{c,a\},\{c,d\}\}.$$

逐个看下面的序列。

1. $a,b,c,a,b$ 是走法，但不是迹，因为边 $\{a,b\}$ 被用了两次。
2. $d,c,a,b,c$ 是迹，但不是路，因为顶点 $c$ 重复出现，四条边却互不重复。

判断时不要靠“看起来绕不绕”。直接写出边序列，检查边有没有重复；再写出顶点序列，检查顶点有没有重复。

有向图不能逆着箭头走

有向图中的走法必须沿箭头方向。若有

$$u\to v$$

却没有

$$v\to u,$$

那么这条边允许从 $u$ 走到 $v$，不允许从 $v$ 走回 $u$。所以有向图里“从 $u$ 能到 $v$”一般不能推出“从 $v$ 能到 $u$”。

这也是有向路径和无向路径最根本的区别。网页链接、任务依赖和单向交通都不能随意把边反过来用。

为什么有走法就有简单路径

如果从 $u$ 到 $v$ 存在一条走法，那么从 $u$ 到 $v$ 一定存在一条简单路径。

第一次看到这句话，容易觉得它只是“把多余绕路删掉”。这个直觉是对的，但我们把删法说严密一点。

这段证明值得记住的不是结论本身，而是“取最短对象，再说明它不可能含有冗余”。以后证明最短路、最小反例和极小结构时，这个套路会反复出现。

---

可达、连通分量与距离

在无向图中，如果从 $u$ 到 $v$ 存在一条路径，就说 $u$ 与 $v$ 连通。每个顶点都通过长度为 $0$ 的路径与自己连通。

如果图中任意两个顶点都连通，就说整张图连通。注意，“连通”不要求两点之间直接有边，只要求经过若干条边能到达。

一张图可以边很多却不连通。例如，两个互不相连的完全图各自都很稠密，合在一起仍有两个分开的部分。反过来，一条很稀疏的长链只有 $n-1$ 条边，却是连通图。

连通分量不是随便圈出的一小块

连通分量是极大的连通子图。“极大”不是说它的顶点数比别的分量都多，而是说它已经无法再从原图加入一个新顶点而保持连通。

更自然的理解来自前面学过的等价关系。在无向图的顶点集合上定义

$$u\sim v \quad\Longleftrightarrow\quad \text{从 }u\text{ 到 }v\text{ 存在路径}.$$

这个关系满足：

因此，$\sim$ 是等价关系。它的等价类正是连通分量。前面“等价关系会把集合划分成互不重叠的块”，到了这里就变成“可达性把顶点集合划分成连通分量”。

孤立顶点也单独形成一个连通分量。它和自己连通，却与任何其他顶点都不连通。

下面的工具可以切换连通图、两个分量以及含孤立顶点的图。选择起点和终点时，先判断它们是否在同一分量，再看工具给出的路径。

有向图里的强连通与弱连通

有向图中，“从 $u$ 可达 $v$”仍有自反性和传递性，却通常没有对称性，所以单向可达本身不是等价关系。

若有向图中任意两个顶点 $u,v$ 都同时满足

$$u\leadsto v \qquad\text{和}\qquad v\leadsto u,$$

就说有向图强连通。也就是从任一点都能沿箭头到达任意另一点，并且还能沿某条有向路径回来。

若先把所有箭头方向擦掉，得到的无向图连通，就说原有向图弱连通。弱连通只保证忽略方向以后不分裂，并不保证实际能顺着箭头往返。

把“互相可达”定义成关系：

$$u\approx v \quad\Longleftrightarrow\quad u\leadsto v\text{ 且 }v\leadsto u,$$

它是等价关系，对应的等价类叫强连通分量。

距离来自最短路径

若 $u$ 与 $v$ 连通，定义它们的距离为所有 $u$ 到 $v$ 路径中最短的长度：

$$d(u,v)=\min\{\text{从 }u\text{ 到 }v\text{ 的路径长度}\}.$$

在无向图中，距离满足三个熟悉性质：

$$d(u,v)\ge0, \qquad d(u,v)=0\Longleftrightarrow u=v,$$ $$d(u,v)=d(v,u),$$

以及三角不等式

$$d(u,v)\le d(u,x)+d(x,v).$$

三角不等式的想法很直接：先走一条从 $u$ 到 $x$ 的最短路，再走一条从 $x$ 到 $v$ 的最短路，拼起来得到一条从 $u$ 到 $v$ 的走法。真正的最短路不会比这条指定走法更长。

若 $u,v$ 不在同一连通分量，最短路径不存在。有的课程把 $d(u,v)$ 留作未定义，有的把它记成 $\infty$；使用前要说明约定。

有向图的距离按有向路径定义，因此可能

$$d(u,v)\ne d(v,u),$$

甚至一个方向有有限距离，反方向完全不可达。

连通图至少需要多少条边

一个有 $n\ge 1$ 个顶点的连通图至少有 $n-1$ 条边。我们可以把证明看成一次“逐步扩张”。

从任意一个顶点开始，把它放入集合 $S$。只要 $S$ 还没有包含全部顶点，由于图连通，必有一条边从 $S$ 内连向 $S$ 外；否则 $S$ 内的顶点永远走不到外面。选这样一条边，把它的外部端点加入 $S$。

每加入一个新顶点，至少要选一条新边。最初已有 $1$ 个顶点，要扩张到 $n$ 个顶点，一共要加入 $n-1$ 次，所以至少需要 $n-1$ 条边。

这个证明还悄悄留下了一组特殊的边：它们连起全部顶点，而且每一步只接入一个新顶点，没有制造多余绕路。下一章会把这种“刚好够连通”的结构正式叫作生成树。

练习：一个无向图的顶点集是 $\{1,2,3,4,5,6,7\}$，边集是

$$\{\{1,2\},\{2,3\},\{1,3\},\{4,5\},\{5,6\}\}.$$

写出所有连通分量，并求 $d(1,3)$ 与 $d(4,6)$。

查看参考答案

连通分量是 $\{1,2,3\}$、$\{4,5,6\}$ 和 $\{7\}$。因为 $1$ 与 $3$ 直接邻接，所以 $$。从 到 的最短路径是 ，所以 。

---

欧拉路径：奇度条件是怎样想到的

图论早期最有名的问题来自一座被河流分割的城市：能不能找一条路线，把七座桥每座恰好走一次？

真正的突破不是更耐心地试路线，而是把陆地缩成顶点，把桥缩成边。这样一来，问题中道路的弯曲、桥的长度和城市的实际比例都被删掉，只剩下“每座桥连接哪两块陆地”。这正是图模型擅长保留的信息。

把图中每条边恰好使用一次的迹叫欧拉迹，也常叫欧拉路径。若起点和终点相同，就叫欧拉回路。

这里的“恰好一次”针对边，不是顶点。欧拉迹可以多次经过同一个顶点，只要不重复边。另一个容易混淆的问题是“每个顶点恰好经过一次”，那是哈密顿路径问题，限制对象完全不同。

先别背结论，数一数进和出

假设一条欧拉迹经过某个既不是起点也不是终点的顶点 $v$。每次沿一条边进入 $v$，都必须再沿另一条还没用过的边离开。于是，迹在 $v$ 使用的边会自然地两两配对：

$$\text{进入一条}+\text{离开一条}.$$

欧拉迹使用了图中每一条边，所以 $v$ 的全部关联边都要配完。能完全配对意味着

$$\deg(v)\text{ 是偶数}.$$

起点和终点稍有不同。若起点与终点不同，起点会多一次“离开而没有对应进入”，终点会多一次“进入而没有对应离开”。它们各留下一个不能配对的边端，所以这两个顶点的度数是奇数。

这就解释了奇度条件的来源：

• 欧拉回路的每个顶点度数都为偶数；
• 开放的欧拉迹恰好有两个奇度顶点，它们必须是起点和终点；
• 若奇度顶点超过两个，就没有足够的“起点、终点名额”安放这些未配对边端。

握手定理早已告诉我们奇度顶点总成偶数个；欧拉迹的进出配对又把可能性进一步压到 $0$ 个或 $2$ 个。

还不能忘记连通

只看度数不够。两个互不相连的圈中，每个顶点度数都是 $2$，却不可能用一条连续路线走完两个分量的全部边。

精确条件要忽略没有边的孤立顶点，因为欧拉迹的任务是覆盖边。对一个至少有一条边的有限无向图：

把两种情况合起来说：边所在的部分必须连通，奇度顶点个数必须是 $0$ 或 $2$。

偶度条件为什么也足够

“有欧拉回路，所以每个度数为偶数”只证明了必要性。要得到完整定理，还要说明：边所在的部分连通、所有顶点度数为偶数时，确实总能走出欧拉回路。

思路可以分成“先走一个圈，再把漏掉的圈接进去”。

若恰有两个奇度顶点 $s,t$，可以临时加一条连接 $s$ 与 $t$ 的辅助边。即使它们原本相邻，也把辅助边看成一条新的平行边。两点度数各加 $1$ 后全部变成偶数，于是新图有欧拉回路。再从回路中删掉这条辅助边，闭合路线就在断口处变成一条从 $s$ 到 $t$ 的欧拉迹。

这段充分性证明暴露了定理背后的构造过程：不是先猜一条完美路线，而是不断形成闭迹，再把它们拼接起来。

一个完整判断

设图的边集是

$$E=\{\{A,B\},\{B,C\},\{C,D\},\{D,A\},\{A,C\}\}.$$

各顶点度数为

$$\deg(A)=3,\quad \deg(B)=2,\quad \deg(C)=3,\quad \deg(D)=2.$$

图连通，奇度顶点恰好是 $A,C$，所以存在从 $A$ 到 $C$ 或从 $C$ 到 $A$ 的开放欧拉迹。一条具体路线是

$$A,B,C,D,A,C.$$

它依次使用 $AB,BC,CD,DA,AC$，每条边恰好一次。注意顶点 $A$ 和 $C$ 都重复出现，这不影响它成为欧拉迹，因为欧拉条件禁止的是重复边。

如果再添加一条边 $\{B,D\}$，那么四个顶点的度数都会变成奇数。此时图仍连通，却不再存在欧拉迹；问题不在于我们还没试到正确路线，而在于四个奇度顶点无法只由一个起点和一个终点吸收。

哥尼斯堡为什么走不通

七座桥抽象出的图有四个顶点，而且四个顶点的度数都是奇数。开放欧拉迹最多允许两个奇度顶点，欧拉回路则一个都不允许，所以答案在尝试路线之前就已经确定：不可能把七条边各走一次。

这也是图论证明很有吸引力的地方。我们不是列出所有路线再逐一失败，而是找到一个每条合法路线都必须满足的结构条件，再看原图直接违反它。

练习：判断下列说法。

1. 一个连通图有 $0$ 个奇度顶点，所以一定有欧拉回路。
2. 一个连通图有 $2$ 个奇度顶点，所以欧拉迹可以从任意顶点开始。
3. 一个图有 $4$ 个奇度顶点，所以不存在欧拉迹。

查看参考答案

第 1 条在有限无向图中成立；连通已经保证所有有边顶点在同一分量，全部偶度便保证欧拉回路存在。第 2 条错误，开放欧拉迹必须从一个奇度顶点开始，在另一个奇度顶点结束。第 3 条成立，欧拉迹只有起点和终点两个位置能留下未配对的边端，容纳不了四个奇度顶点。

---

把问题翻译成图论问题

学完定义以后，真正要练的是翻译。面对一个新情境，可以先写出模型，再判断题目究竟在问哪种结构。

冲突模型

顶点表示任务、课程或无线电台；两个对象不能共享同一资源时连无向边。问题可能进一步问：至少需要多少个时间段或频道，才能让相邻顶点不冲突？这会引向图着色。

依赖模型

顶点表示课程、任务或软件包；若 $A$ 必须先于 $B$，画有向边 $A\to B$。问题可能问某个任务是否间接依赖另一个任务，这就是有向可达性；若依赖图出现有向圈，则说明一组任务互相等待。

路网模型

顶点表示位置，边表示可以直接移动的一段路线。连通分量回答“哪些位置彼此可达”，距离回答“最少要走几段”，欧拉迹回答“能否把每段路线恰好检查一次”。

合作网络

顶点表示人，两人合作过就连边。度数回答“某人有多少位直接合作者”，路径回答“合作关系最少隔几层”，连通分量则找出互不相连的合作群体。

同一份现实数据也可以产生不同图。若边只记录“是否合作过”，得到简单图；若每次合作项目都单独保留，得到多重图；若记录“谁邀请了谁”，则得到有向图。模型改变以后，度数和路径的含义也随之改变。

四类证明分别怎样下手

---

章末自检

图的类型

某社交平台记录“用户甲关注用户乙”。应使用无向图还是有向图？若用户可以关注自己，自环是否需要允许？

查看参考答案

关注关系有发出者和接收者，甲关注乙不保证乙关注甲，所以应使用有向图。若平台规则允许用户关注自己，模型就应允许自环；若平台禁止，则排除自环。图的规则应跟实际关系一致。

握手定理

一个无向图有 $10$ 个顶点、$17$ 条边。所有顶点度数之和是多少？奇度顶点能恰好有 $5$ 个吗？

查看参考答案

由握手定理，

$$\sum_{v\in V}\deg(v)=2|E|=34.$$

奇度顶点个数必须是偶数，所以不能恰好有 $5$ 个。

走法分类

在边集

$$\{\{a,b\},\{b,c\},\{c,d\},\{d,b\}\}$$

中，序列 $a,b,c,d,b$ 是路、迹还是普通走法？

查看参考答案

它依次使用边 $ab,bc,cd,db$，没有重复边，所以是迹。顶点 $b$ 出现两次，所以不是简单路径。它当然也是走法，因为迹是加了限制的走法。

连通与距离

如果无向图中 $d(u,v)=4$，能否断定存在一条长度为 $6$ 的从 $u$ 到 $v$ 的走法？能否断定存在一条长度为 $6$ 的简单路径？

查看参考答案

存在长度为 $4$ 的最短路径。若这条路径上至少有一条边，可以沿其中一条边来回一次，再继续走，得到长度为 $6$ 的走法，所以第一问可以。第二问不能；最短距离为 $4$ 并不保证图中还有更长的简单路径，额外绕行往往会重复顶点或边。

有向可达

若有向图中从 $u$ 能到 $v$，从 $v$ 能到 $w$，可以推出什么？还能推出从 $w$ 能到 $u$ 吗？

查看参考答案

把两段有向路径接起来，可以得到从 $u$ 到 $w$ 的有向走法，再删去重复顶点可得有向路径，所以 $u$ 能到 $w$。不能据此推出 $w$ 能到 $u$，因为有向可达一般不具对称性。

欧拉判断

某个有边的有限无向图只有一个连通分量包含边，各顶点度数为

$$2,2,2,4,4,6.$$

它有欧拉回路吗？若把其中一个度数 $2$ 改成 $3$，其余不变，这个新度数表可能来自无向图吗？

查看参考答案

第一张图的边所在部分连通，而且所有顶点度数为偶数，所以有欧拉回路。把一个 $2$ 改成 $3$ 后，度数总和从偶数变成奇数，违反握手定理，因此新的度数表不可能来自任何有限无向图。

同构判断

两个简单图都有 $6$ 个顶点和 $6$ 条边，第一个图连通，第二个图有两个连通分量。它们可能同构吗？

查看参考答案

不可能。同构保持路径与连通性，因此也保持连通分量个数。顶点数和边数相同只是必要条件，不能抵消连通性上的差异。

---

从一般连通图走向树

这一章建立了读图和证明所需的基本语言：顶点与边决定模型，邻接和同构描述结构，度数把局部连接汇总成全局等式，走法与路径刻画可达，连通分量把顶点集合分块，距离挑出最短路线，欧拉迹则展示了局部奇偶性怎样决定整条路线能否存在。

我们还证明了一个连通图有 $n$ 个顶点时至少需要 $n-1$ 条边。现在自然会问：如果它恰好只有 $n-1$ 条边，会发生什么？这时每条边都不能再删，两个顶点之间也不该有多余绕路；一旦出现回路，其中总有一条边可以去掉而不破坏连通。

下一章研究的树，正是这种“连通但没有多余边”的图。今天学过的路径、回路、连通分量、度数和生成子图，会在那里合成一组彼此等价的刻画。