Tao–Vu · 加性组合学 · 第 6 章图论方法

6.1　基本概念Basic Notions

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节目标本章要用图这个工具来研究加法问题。第一步，先把图论里最基本的语言全部立起来：什么是图、点的度、导出子图、独立集、路径、圈、三角形，以及最关键的二部图。这些词后面整章都要反复用到，所以本节虽然短，却是地基。读时只需抓一件事：图就是“一堆点 + 哪些点之间连了线”。

图、邻居与度

一个图（graph）\(G=G(V,E)\) 由一个有限的顶点集 \(V\)（顶点也称点 points、结点 nodes）和一个有限的边集 \(E\) 组成，其中每条边都是由两个不同顶点构成的一个无序对 \(\{a,b\}\)（因此我们不允许出现自环 loop）。

把定义拆开看

无序对：边 \(\{a,b\}\) 与 \(\{b,a\}\) 是同一条边——线没有方向。
两个不同顶点：边的两个端点必须是不一样的点，所以不会有一个点连到它自己（那种连法叫自环，本书禁止）。
有限：点和边的数量都是有限个，能一个一个数清楚。

一个图的例子：\(V=\{a,b,c,d,e\}\)，\(E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{d,e\}\}\)。每条边就是一段连两个点的线。

若 \(\{a,b\}\in E\)，我们就说两个顶点 \(a\) 与 \(b\) 是相邻的（adjacent）或互为邻居（neighbors）。\(a\) 的全体邻居所构成的集合记作 \(N(a)\)。集合 \(N(a)\) 的元素个数称为 \(a\) 的度（degree），记作 \(\deg(a)\)。

例（读上面那张图）

\(b\) 的邻居有谁？凡是与 \(b\) 连了线的点：\(a,c,d\)。所以 \(N(b)=\{a,c,d\}\)，\(\deg(b)=3\)。
\(N(a)=\{b,c\}\)，\(\deg(a)=2\)；\(N(e)=\{d\}\)，\(\deg(e)=1\)。
度就是“从这个点伸出几条线”。数线即可，不用别的技巧。

导出子图与独立集

考虑 \(V\) 的一个子集 \(V'\)。我们把图 \(G'=G'(V',E')\) 称为 \(G\) 中由 \(V'\) 张成的导出子图（induced subgraph spanned by \(V'\)），其中

\[E':=\{e\in E:\ e\subseteq V'\}.\]

一个集合 \(V'\subset V\) 称为独立的（independent），如果它张成的是一个空图，也就是说：不存在两个端点都落在 \(V'\) 里的边。

逐字解释 \(E'=\{e\in E:\ e\subseteq V'\}\)导出子图的做法是：先选定要保留的一批点 \(V'\)，然后只保留那些两个端点都在 \(V'\) 里的边。一条边只要有一个端点被丢在 \(V'\) 外面，这条边就跟着被删掉。换句话说：点你来挑，边则“自动跟随”——\(V'\) 内部原本怎么连，子图里就还怎么连，不多不少。

取 \(V'=\{a,b,c\}\)：边 \(\{b,d\}\) 因为端点 \(d\notin V'\) 被删去，只剩三个端点都在内部的边 \(\{a,b\},\{a,c\},\{b,c\}\)。

例（独立集）仍看本节第一张图。

试 \(V'=\{a,e\}\)：\(a\) 与 \(e\) 之间有没有边？没有。所以 \(\{a,e\}\) 张成空图，是独立集。
试 \(V'=\{a,b\}\)：\(\{a,b\}\) 是一条边，端点都在 \(V'\) 里。张成的图非空，所以不是独立集。
记忆要点：独立集就是“内部互不相连的一堆点”——任意两点之间都没有边。

路径、圈与三角形

我们说顶点 \(a_0,\dots,a_k\) 构成一条长度为 \(k\) 的路径（path of length \(k\)），如果对所有 \(0\le i\le k-1\)，\(\{a_i,a_{i+1}\}\) 都是一条边。若 \(a_k=a_0\)，我们就把这条路径称为一个圈（cycle）。三个顶点 \(a,b,c\) 构成一个三角形（triangle），如果它们构成一个长度为 \(3\) 的圈，也就是说 \(\{a,b\}\)、\(\{b,c\}\) 和 \(\{c,a\}\) 都是边。

为什么“长度”数的是边，不是点路径 \(a_0,a_1,\dots,a_k\) 一共写了 \(k+1\) 个点，但相邻两点之间的“步”有 \(k\) 段——每一步就是一条边。长度 = 走过的边数 = 步数。比如 \(a_0,a_1,a_2\) 是长度为 \(2\) 的路径（走了两步）。圈则是“走回起点”：终点和起点是同一个，绕成一个环。

左：\(a_0\to a_1\to a_2\to a_3\)，走 3 条边，长度为 \(3\)。右：\(a\to b\to c\to a\) 走 3 条边又回到起点，是长度 \(3\) 的圈，即三角形。

二部图

一个图称为二部的（bipartite），如果可以把它的顶点集划分成两个不相交的集合 \(A\) 与 \(B\)，使得每一条边都有一个端点在 \(A\) 中、另一个端点在 \(B\) 中；\(A\) 与 \(B\) 称为 \(G\) 的颜色类（color classes）。二部图在后续内容中扮演重要角色，处理它们时，我们更愿意采用记号 \(G(A,B,E)\) 而不是 \(G(V,E)\)。

注意，在一个二部图 \(G=G(A,B,E)\) 中，同一颜色类里的两个顶点只能由偶数长度的路径相连，而不同颜色类里的顶点只能由奇数长度的路径相连。特别地，所有的圈都必定是偶数长度。

二部图：每条边都“跨边”——一头在蓝色类 \(A\)，一头在红色类 \(B\)。同色之间从不直接连线。

为什么同色相连必为偶数步、异色必为奇数步沿着路径每走一步，必然从一个颜色类跳到另一个颜色类（因为每条边都跨边）。于是颜色像开关一样逐步翻转：

从 \(A\) 出发。走 1 步到 \(B\)，走 2 步回 \(A\)，走 3 步到 \(B\)，走 4 步回 \(A\)……
规律：走偶数步后仍在出发的那一类（同色），走奇数步后在另一类（异色）。
所以：同色两点之间的路径长度必为偶数；异色两点之间必为奇数。
圈是“回到起点”，起点终点同色，由上一条，圈长必为偶数。♦

颜色随步数翻转：偶数步回到原色（同色），奇数步落在异色。这正是“二部图所有圈都是偶长”的原因。

习题

习题 6.1.1证明：图 \(G\) 是二部图，当且仅当它的所有圈都是偶数长度。

习题 6.1.2（Cayley 图）设 \(A\) 是有限加法群 \(Z\) 中的一个对称加法集（即 \(A=-A\)）。\(A\) 的 Cayley 图定义为：以 \(Z\) 为顶点集，两个顶点 \(x,y\) 之间连一条边当且仅当 \(x-y\in A\)。

证明对所有 \(v\in Z\) 都有 \(\deg(v)=|A|\)；
证明两点 \(v,w\in Z\) 由一条长度为 \(n\) 的路径相连，当且仅当 \(v-w\in n(A)\)（这里 \(n(A)\) 指 \(A\) 的 \(n\) 重和集）；
证明 \(G\) 是连通的，当且仅当 \(A\) 张成 \(Z\)（即 \(A\) 的各重和集最终覆盖整个 \(Z\)）。

习题 6.1.3（二部图的流行度原理 Popularity principle）设 \(G(V_1,V_2,E)\) 是一个二部图，且 \(V_2\) 非空。证明：存在一个二部子图 \(G'(V_1,V_2,E')\)，满足 \(|E'|\ge |E|/2\)，并且对所有 \(v_2\in V_2\) 都有 \(\deg_{G'}(v_2)\ge |E|/2|V_2|\)。

习题 6.1.4（二部图的 Cauchy–Schwarz）设 \(G(V_1,V_2,E)\) 是一个二部图，且 \(V_1,V_2\) 都非空。证明 \(G\) 中至少含有 \(|E|^2/|V_2|\) 条长度为 \(2\) 的路径。

（原文 PDF 在此句末截断，"\(|E|^2/|V_2|\)" 之后的"条长度为 2 的路径"按本习题标题"Cauchy–Schwarz"的标准结论补全：以 \(V_2\) 中的点为中点统计两端在 \(V_1\) 的路径，由 Cauchy–Schwarz 不等式 \(\sum_{v_2}\deg(v_2)^2\ge\big(\sum_{v_2}\deg(v_2)\big)^2/|V_2|=|E|^2/|V_2|\) 即得。）

返回全书目录