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

很多现实问题的核心不是单个对象，而是对象之间的连接：哪两座城市有直达道路，哪两门课不能同一时段考试，哪些网页互相链接，哪些人已经合作过。图论把这类问题压缩成一种很朴素的语言：点表示对象，边表示关系。

图论里的“图”不是函数图像，也不是统计图表。它是一种关系模型。我们画点和线，是为了保留问题中真正影响结论的连接结构，而不是为了画出对象的真实形状。

真实关系抽象成图的中文概念图，左侧展示城市道路、同学关系和网页链接，右侧抽象为由顶点和边组成的网络结构，并标注 G=(V,E) — 把真实关系建模成图时，顶点表示对象，边表示对象之间被保留下来的关系。

图论入门最重要的习惯，是先问“顶点是什么，边表示什么”。同一张图可以表示道路、合作、冲突或依赖；如果顶点和边的含义没有说清，后面的度数、路径和连通性都没有明确对象。

图的基本语言

一个无向图通常写作

G=(V,E)

其中 $V$ 是顶点集合， $E$ 是边集合。顶点也叫节点。边把顶点连接起来。在无向图中，边 $\{u,v\}$ 不区分方向；它只说明 $u$ 和 $v$ 之间有连接。在有向图中，边写作有序对 $(u,v)$ ，表示从 $u$ 指向 $v$ 的箭头。

例如，把几座城市看成顶点，把两城之间是否有直达航班看成边，就得到一个图。如果航班方向不重要，可以用无向图；如果只关心单向航线，就应使用有向图。

简单图、多重图与有向图

简单图是最常见的入门对象。它满足两条限制：没有自环，也没有平行边。自环是从一个顶点连回自己的边；平行边是同一对顶点之间出现多条边。

多重图允许平行边，有的定义也允许自环。它适合描述“同一对对象之间可能有多种连接”的场景。比如两座城市之间可能同时有铁路、公路和航线；若我们想把这些连接分开记录，多重图比简单图更合适。

有向图的边带方向。网页链接、关注关系、任务依赖、函数调用都常用有向图表示，因为 $u$ 指向 $v$ 与 $v$ 指向 $u$ 不是同一个事实。

三栏图示比较简单图、多重图和有向图：简单图无自环且任意两顶点最多一条边，多重图含平行边和自环，有向图的边带方向箭头 — 简单图排除自环和平行边；多重图允许更丰富的边；有向图记录方向。

不要把“图中两条线相交”误认为有一个顶点。只有被明确画成点、并被纳入顶点集合的对象才是顶点。画图时线段交叉只是排版现象，除非题目特别说明交点也是顶点。

用顶点和边建模

建模时通常有三步。

先选顶点。顶点应对应题目中要被区分的对象。排课问题里，顶点可以是课程；社交网络里，顶点可以是人；网页分析里，顶点可以是网页。

再选边。边应对应影响问题的关系。课程之间若不能同一时段考试，就连一条边；两个人若互为好友，就连一条边；一个网页链接到另一个网页，就画一条有向边。

最后说明图的类型。关系是否有方向，是否允许自环，是否可能有平行边，都要在模型里提前说清楚。

练习：某小组有 6 名成员。若两人曾经合作过同一个项目，就在他们之间连边。这个模型中，顶点和边分别是什么？它更自然地是无向图还是有向图？

顶点是 6 名成员，边表示“两人曾经合作过同一个项目”。如果合作关系只记录是否合作过，而不区分谁主动邀请谁，那么它更自然地是无向图。若题目改成“谁向谁发送过邀请”，才更适合用有向图。

度数与握手定理

在无向图中，一个顶点的度数是与它关联的边的条数。若一条边连接 $u$ 和 $v$ ，它会让 $u$ 的度数增加 $1$ ，也会让 $v$ 的度数增加 $1$ 。

在简单图中，度数很容易从图上数出来。若顶点 $v$ 有三条边接到其他顶点，就写作 $\deg(v)=3$ 。没有任何边相连的顶点叫孤立顶点，它的度数是 $0$ 。

无向图中六个顶点的度数示意，顶点甲及其关联边被高亮，右侧表格列出各顶点度数 — 顶点的度数来自与它相接的边数；孤立顶点的度数为 0。

如果允许自环，很多教材约定一个自环对该顶点的度数贡献 $2$ 。直观地说，自环的两端都落在同一个顶点上，所以要算两次。本章后面的基本结论主要在无向图中讨论；除非特别说明，可以先把图理解为简单无向图。

下面的交互可以添加或删除边，并实时查看每个顶点的度数。

度数和边数的关系

设 $G=(V,E)$ 是有限无向图。把所有顶点的度数加起来，会得到边数的两倍：

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

这个结论叫握手定理。名字来自一个很直观的情境：若每次握手都发生在两个人之间，那么从所有人那里数“我握了几次手”，每次握手会被数两次。

握手定理的视觉解释：左侧无向图显示每条边在两个端点各贡献一次，右侧用公式 Σ deg(v)=2|E| 表示度数总和等于边数的两倍 — 每条边有两个端点，所以在度数总和中贡献两次。

从边的角度数。任意一条普通边都有两个端点，它会使这两个端点的度数各增加 $1$ 。

因此，每条边对全体顶点度数总和的贡献都是 $2$ 。

图中共有条边，所以所有贡献合起来是。

握手定理马上推出一个小结论：奇度数顶点的个数一定是偶数。因为度数总和是偶数，偶度数顶点的度数相加仍是偶数，所以奇度数顶点的度数相加也必须是偶数。若奇数个奇数相加，结果是奇数；因此奇度数顶点只能有偶数个。

练习：某个无向图有 6 个顶点，度数分别为

1,2,2,4,4,4

这样的图可能存在吗？只用握手定理判断即可。

不可能。度数总和是 $1+2+2+4+4+4=17$ ，但无向图中所有顶点度数之和必须等于 $2|E|$ ，一定是偶数。这个序列的总和是奇数，所以不可能来自任何无向图。

路径、回路与可达

图论关心的不只是两个顶点是否直接相连，还关心能不能沿着若干条边从一个顶点走到另一个顶点。

在无向图中，一个从 $v_0$ 到 $v_k$ 的道路可以写成顶点序列

v_0,v_1,\ldots,v_k

并要求每一对相邻顶点之间都有边。这里的长度是走过的边数，也就是 $k$ 。

道路、迹、路径、回路

不同教材对中文术语有时略有差异，本章采用下面这组区分。

道路允许重复顶点，也允许重复边。
迹不允许重复边，但可以重复顶点。
路径不允许重复顶点，因此也不会重复边。
回路从某个顶点出发，最后回到同一个顶点，并且中间按照规定走边。

四个并排小图用同一个图的不同高亮行走序列区分道路、迹、路径和回路 — 路径比道路更严格；回路强调首尾回到同一顶点。

例如，如果图中有边 $AB,BC,CD$ ，那么 $A,B,C,D$ 是从 $A$ 到 $D$ 的一条路径。若还有边 $DA$ ，那么是一个回路。

证明“两个顶点连通”时，只要给出一条路径即可。证明“两个顶点不连通”更难一些，因为要说明所有可能的走法都到不了，通常需要借助连通分量或割断结构。

路径的简化

如果从 $u$ 到 $v$ 存在一条道路，那么从 $u$ 到 $v$ 也存在一条路径。理由是：道路中若重复经过某个顶点，就把这次重复之间绕出的圈删掉。重复删下去，最终会留下不重复顶点的路径。

从一条连接 $u$ 到 $v$ 的道路开始。若它没有重复顶点，它已经是一条路径。

若道路中某个顶点 $x$ 出现了两次，就把第一次 $x$ 到第二次之间的那段删去。删去后，前后仍在处接上，所以仍是一条从到的道路。

下面的交互可以选择起点和终点，观察工具如何寻找路径；若找不到路径，它会显示两个顶点属于不同连通分量。

练习：若 $A,B,C,D,E$ 是图中的五个不同顶点，并且 $AB,BC,CD,DE,EA$ 都是边，写出一个回路和一条从 $A$ 到的路径。

一个回路是 $A,B,C,D,E,A$ 。一条从 $A$ 到 $D$ 的路径是 $A,B,C,D$ ，也可以是，前提是边已由题目给出。这里题目给的是，在无向图中它与是同一条边。

连通性与连通分量

在无向图中，如果任意两个顶点之间都有路径，就说这个图是连通的。若图不是连通的，它会分成若干块，每一块内部顶点彼此可达，而不同块之间没有路径。这些最大连通块叫连通分量。

“最大”这个词很重要。一个连通分量不是随便挑出几个互相连着的点，而是已经把所有能和它们连通的顶点都收进来了。

三个互不相连的无向图连通分量示意图，分别标出连通分量一、连通分量二和孤立顶点，并用高亮路径展示从 A 到 F 可达、从 A 到 D 不可达 — 同一连通分量内部任意两点可达；不同连通分量之间没有路径。

孤立顶点也是一个连通分量。它只包含自己。因为从一个顶点到它自己通常允许长度为 $0$ 的路径，所以单个顶点构成的图是连通的。

“图有很多边”不保证连通，“图看起来分散”也不一定不连通。连通性只看任意两点之间是否存在路径，不看图画得疏密或美观。

连通关系是等价关系

在同一个无向图里，定义 $u\sim v$ 当且仅当 $u$ 和 $v$ 之间存在路径。这个关系是等价关系。

自反性成立，因为每个顶点到自己有长度为 $0$ 的路径。

对称性成立，因为无向图中的路径可以反向走。如果 $u$ 能到 $v$ ，那么 $v$ 也能沿同一批边反向到。

这个观察把第 6 章的关系语言接到了图论语言上。连通分量不是凭直觉画圈，而是由“可达”这个等价关系产生的划分。

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

\{\{1,2\},\{2,3\},\{4,5\}\}

写出所有连通分量。

顶点 $1,2,3$ 彼此可达，形成连通分量 $\{1,2,3\}$ 。顶点 $4,5$ 通过边 $\{4,5\}$ 相连，形成连通分量 $\{4,5\}$ 。顶点没有任何边相接，所以它单独形成连通分量。

子图

子图是从一个图里保留部分顶点和部分边得到的图。若 $H=(V_H,E_H)$ 是 $G=(V,E)$ 的子图，则

V_H\subseteq V

并且

E_H\subseteq E

同时， $E_H$ 中的每条边都必须连接 $V_H$ 中的顶点。也就是说，不能把某条边留下来，却删掉它的端点。

子图与生成子图示意：左侧为原图，右上为删除部分顶点及相关边得到的子图，右下为保留全部顶点但删除部分边得到的生成子图 — 子图可以删除顶点和相关边；生成子图保留所有顶点，只删除部分边。

若一个子图保留原图的全部顶点，只删去一些边，就叫生成子图。生成子图在后续学习树和生成树时会很常见：我们常想保留全部对象，但只选择一部分连接。

用子图表达局部结构

子图可以帮助我们把大图中的局部结构单独拿出来研究。比如在社交网络中，我们可能只研究某个班级内部的关系；在课程依赖图中，我们可能只研究数学课程构成的部分；在道路网络中，我们可能只看某个城区。

子图不是复制原图的一小块图像，而是对顶点集合和边集合做选择。只要集合选择说清楚，图画的位置、弯曲程度和边的长度都不影响子图关系。

练习：设 $G$ 的顶点集合是 $\{a,b,c,d\}$ ，边集合是

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

若 $H$ 的顶点集合是 $\{a,b,c\}$ ，边集合是 $\{\{a,b\},\{b,c\}\}$ ， $H$ 是 $G$ 的子图吗？它是生成子图吗？

$H$ 是 $G$ 的子图，因为它的顶点都来自 $G$ ，边也都来自 $G$ ，并且每条边的端点都在 $H$ 的顶点集合中。它不是生成子图，因为生成子图必须保留 $G$ 的全部顶点，而 $H$ 没有保留顶点 $d$ 。

把真实关系建模成图

图论模型的难点常常不在画图，而在选择合适的对象和关系。下面看三个常见模型。

冲突图

排课、考试安排、无线信道分配都可以产生冲突图。顶点表示任务或对象；若两个对象不能同时使用同一资源，就在它们之间连边。后续的图着色会把“分配资源”转化为“给顶点上色，使相邻顶点颜色不同”。

依赖图

若任务 $A$ 必须在任务 $B$ 之前完成，可以画有向边 $A\to B$ 。课程先修关系、软件包依赖、项目流程都可以用有向图表示。这里方向不能随便省略，因为“先修”和“被先修”不是同一个关系。

可达图

交通网络、通信网络和网页网络都关心可达性。顶点表示位置、设备或网页；边表示可以直接移动、通信或跳转。连通性告诉我们系统是否分裂成互不相通的部分，路径则给出具体连接方式。

先写出一句话模型：“顶点表示什么，边表示什么。”这句话越短，越能暴露模型是否清楚。

再判断边是否有方向。若关系本身可以反向成立，通常用无向图；若关系有发出者和接收者，就用有向图。

接着判断是否需要平行边或自环。若只关心“是否有关”，简单图通常够用；若要区分多种连接，就考虑多重图。

最后把问题翻译成图论问题。是问度数、路径、连通分量，还是后续会问树、匹配、着色？

练习：把“某城市地铁站之间的直达线路”建模成图。给出顶点、边和一个可以用连通性回答的问题。

顶点可以是地铁站，边可以表示两站之间存在直达区间。若暂时不区分上下行方向，可用无向图。一个连通性问题是：从任意一个站是否都能通过换乘到达任意另一个站？若答案是否定的，连通分量可以指出地铁网络被分成了哪些互不相通的部分。

章末自检

一个简单无向图有 5 个顶点和 6 条边。所有顶点度数之和是多少？

根据握手定理，所有顶点度数之和是 $2|E|=2\cdot6=12$ 。

是否存在一个无向图，它恰好有 3 个奇度数顶点？

不存在。无向图中奇度数顶点的个数一定是偶数，这是握手定理的直接推论。

若一个图有三个连通分量，能否说它“不含路径”？

不能。三个连通分量表示不同分量之间没有路径，但每个分量内部仍可能有很多路径。若某个分量只有一个孤立顶点，它至少还有从自己到自己的长度为 $0$ 的路径。

在有向图中，若从 $u$ 有路径到 $v$ ，是否一定从 $v$ 有路径到 $u$ ？

不一定。有向图中的边不能随便反向走。从 $u$ 到 $v$ 有有向路径，只说明可以沿箭头方向到达 $v$ ；除非另有边或路径返回，否则不能推出 $v$ 能到 $u$ 。

本章建立了图论最基础的语言：顶点、边、图的类型、度数、路径、连通性、连通分量和子图。下一章会在这个基础上研究树。树可以看成一种刚好连通、又没有多余回路的图，它会把图论和递归结构连接起来。

∣

E

∣

|E|

离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 15 章：图论语言：图、度数、路径与连通性 | 自在学