集合与图论学习笔记07

定义

定义 7.1 平面图

若一个图能画在平面上使得它的边互不相交（除了在顶点处外），则称该图为平面图，或称该图为能嵌入平面的。

本文中把图 \(G\) 的平面嵌入称为平图

给出有关 \(Jordan\) 曲线的一个定理但不加以证明（涉及到拓扑相关知识）：

定理 7.1.1 (Jordan 曲线定理)

设 \(J\) 是平面上的一条 \(Jordan\) 曲线，平面的剩下部分被分割为两个不相交的开集，称为 \(J\) 的内部和外部，分别记为 \(int(J)\) 和 \(ext(J)\)

分别记它们的闭包为 \(Int(J)\) 和 \(Ext(J)\)，显然 \(Int(J) \cap Ext(J) = J\)

则：链接 \(int(J)\) 和 \(ext(J)\) 的点的任何连线必在某个点和 \(J\) 相交

可以仿照平面图的定义来定义可嵌入曲面 \(S\) 的图

不加以证明的给出定理

定理 7.1.2

对于任意一个曲面 \(S\) ，总存在不可嵌入 \(S\) 的图

定理 7.1.3

每个图都可以嵌入三维空间 \(\mathbb{R}^3\)

定理 7.1.4

图 \(G\) 可嵌入平面当且仅当它可嵌入球面

根据 \(Jordan\) 曲线定理可以证明：\(K_5\) 和 \(K_{3,3}\) 不是平面图

定理 7.1.5 常见非平面图

图 \(K_5\) 和 \(K_{3,3}\) 不是平面图

证明： 点击查看证明

先证明 \(K_5\) 不是平面图

假设 \(K_{5}\) 是平面图。设顶点 \(v_1,v_2,v_3,v_4,v_5\)，圈 \(C=v_1v_2v_3v_1\) 是一条 \(Jordan\) 曲线，\(v_4\in int(C)\) 或 \(v_4\in ext(C)\)

不妨设 \(v_4\in int(C)\)，则 \(v_4v_1\) ，\(v_4v_2\)，\(v_4v_3\) 三条边均在 \(int(C)\) 中，分为三个区域 \(intC_1,intC_2,intC_3\)

此时 \(v_5\) 必定在 \(ext(C),intC_1,intC_2,intC_3\) 中，此时 \(v_5\) 与 \(v_1,v_2,v_3,v_4\) 之间的边必有一条与其他边相交，矛盾

证明 \(K_{3,3}\) 不是平面图

假设 \(K_{3,3}\) 是平面图。设顶点集为 \(u_1,u_2,u_3\) 和 \(v_1,v_2,v_3\)，圈 \(C=u_1v_1u_2v_2u_1\) 是一条 \(Jordan\) 曲线，\(v_3\in int(C)\) 或 \(v_3\in ext(C)\)

不妨设 \(v_3\in int(C)\)，则 \(v_3u_1\) 和 \(v_3u_2\) 两条边均在 \(int(C)\) 中，分为两个区域 \(intC_1,intC_2\)

此时 \(u_3\) 必定在 \(ext(C),intC_1,intC_2\) 中，此时 \(u_3\) 与 \(v_1,v_2,v_3\) 之间的边必有一条与其他边相交，矛盾

\(K_5\) 是可环面嵌入的，\(K_{3,3}\) 是可 \(Mobius\) 带嵌入的

定义 7.2 面、对偶图

一个图 \(G\) 把平面划分为若干个连通区域，这些区域的闭包称为 \(G\) 的面，其中恰有一个无界的面，称为外部面

平图 \(G\) 的几何对偶图 \(G^*\) 定义如下

• 在每个面内取一个点作为 \(G^*\) 的顶点
• 对于 \(G\) 的每一条边 \(e\) ，在 \(G^*\) 中连接 \(e\) 所在的两个面的对应顶点，并使该边与 \(e\) 相交于一点

显然， \(G^*\) 有多重边当且仅当\(G\) 中存在两个面至少有两条公共边

\(G^*\) 面数量 \(f^*=n\)，顶点数量 \(n^*=f\)，边数量 \(e^*=e\)

定理 7.2.0 欧拉公式

若 \(G\) 是连通平图，则 \(n-e+f=2\)

证明： 点击查看证明

对 \(f\) 使用数学归纳法：

\(f=1\) 时，\(G\) 是一棵树，\(e=n-1\)，所以 \(n-e+f=2\)

假设当 \(f\le k\) 时结论成立，现证明当 \(f=k+1\) 时结论也成立：

任选 \(G\) 的一条不是割的边 \(e\) ，则 \(G-e\) 时连通平图，根据归纳假设有 \(n-(e-1)+(f-1)=2\)

即 \(n-e+f=2\) 成立

定理 7.2.1

两个同构的平图的对偶图不一定同构

给出图示

由于一个平面图可以存在不同的平面嵌入，因此它的对偶图也可能不唯一，所以不把对偶图的概念扩展到平面图上

定理 7.2.2

\(G\) 是平图，则 \(\sum_{f\in F}d(f)=2e\)

证明： 点击查看证明

考虑对偶图 \(G^*\) ，则 \(\sum_{f\in F}d(f)=\sum_{v\in V(G^*)}d(v)=2e^*=2e\)

定理 7.2.3

平图 \(G\) 的对偶图 \(G^*\) 的对偶图同构于 \(G\)

证明： 点击查看证明

只需要证明 \(G\) 和 \(G^{**}\) 之间存在同构映射 \(\phi\) ：\(V(G)\rightarrow V(G^{**})\)

对于 \(G\) 的每个顶点 \(v\) ，考虑 \(G\) 中以 \(v\) 为端点的所有边，这些边在 \(G^*\) 中对应于若干条边，这些边将 \(G^*\) 分成若干个面，这些面的对应顶点构成 \(G^{**}\) 中的一个顶点，定义 \(\phi(v)\) 为该顶点

下面证明 \(\phi\) 是同构映射

设 \(u,v\in V(G)\) ，\(uv\in E(G)\) ，则 \(uv\) 在 \(G^*\) 中对应于一条边 \(e^*\) ，该边将 \(G^*\) 分成两个面，这两个面的对应顶点分别为 \(\phi(u)\) 和 \(\phi(v)\) ，因此 \(\phi(u)\phi(v)\in E(G^{**})\)

反之，设 \(\phi(u),\phi(v)\in V(G^{**})\) ，\(\phi(u)\phi(v)\in E(G^{**})\) ，则 \(G^*\) 中存在一条边 \(e^*\) ，该边将 \(G^*\) 分成两个面，这两个面的对应顶点分别为 \(u\) 和 \(v\) ，因此 \(uv\in E(G)\)

若一个平图和它的对偶图同构，则称该平图为自对偶图

定理 7.2.4

若 \(G\) 是自对偶平图，则 \(2n=e+2\)

证明： 点击查看证明

由于 \(G\) 是自对偶平图，则 \(n=f\) 且 \(e=e^*\)

由欧拉公式 \(n-e+f=2\) 可得 \(2n=e+2\)

定理 7.2.5

欧拉平图的对偶图是二分图（偶图）

证明： 点击查看证明

设 \(G\) 是欧拉平图，\(G^*\) 是 \(G\) 的对偶图

由于 \(G\) 是欧拉图，则 \(G\) 的每个顶点的度数均为偶数

\(G\) 的每一个顶点对应 \(G^*\) 的一个面，则面度数（即围成面的边数）也为偶数

定理 7.2.6

\(G\) 是平图，\(G^{**}\) 和 \(G\) 同构当且仅当 \(G\) 连通

证明： 点击查看证明

设 \(G\) 是平图，\(G^{**}\) 是 \(G\) 的对偶图的对偶图

必要性：

设 \(G\) 不连通，则 \(G\) 有两个连通分支 \(G_1\) 和 \(G_2\)

则 \(G^*\) 有一个面 \(f\) ，该面对应于 \(G^{**}\) 中的一个顶点 \(v\) ，且 \(v\) 与 \(G^{**}\) 中的其他顶点均不相连

因此 \(G^{**}\) 不连通，矛盾

充分性：

设 \(G\) 连通，则对于 \(G\) 的任意一条边 \(e\) ，\(e\) 不是割边

则 \(G^*\) 中与 \(e\) 对应的边 \(e^*\) 连接 \(G^*\) 中的两个不同顶点

因此 \(G^{**}\) 中与 \(e^*\) 对应的边 \(e^{**}\) 连接 \(G^{**}\) 中的两个不同顶点

定义映射 \(\phi:V(G)\rightarrow V(G^{**})\) ，对于 \(G\) 的每个顶点 \(v\) ，\(\phi(v)\) 是 \(G^{**}\) 中与 \(v\) 对应的顶点

下面证明 \(\phi\) 是同构映射

设 \(u,v\in V(G)\) ，\(uv\in E(G)\) ，则 \(uv\) 在 \(G^*\) 中对应于一条边 \(e^*\) ，该边将 \(G^*\) 分成两个面，这两个面的对应顶点分别为 \(\phi(u)\) 和 \(\phi(v)\) ，因此 \(\phi(u)\phi(v)\in E(G^{**})\)

反之，设 \(\phi(u),\phi(v)\in V(G^{**})\) ，\(\phi(u)\phi(v)\in E(G^{**})\) ，则 \(G^*\) 中存在一条边 \(e^*\) ，该边将 \(G^*\) 分成两个面，这两个面的对应顶点分别为 \(u\) 和 \(v\) ，因此 \(uv\in E(G)\)

定理 7.2.7

\(G\) 是一个平图，每个面至少由 \(k(k\ge 3)\) 条边围成，则 \(e\le \max \{\frac{k(n-2)}{k-2},3n-6\}\)

证明： 点击查看证明

首先证明 \(e \le 3n-6\)

由于每个面至少由 \(3\) 条边围成，则由定理 7.2.2 有 \(\sum_{f\in F}d(f)=2e\ge 3f\)

即 \(f\le \frac{2e}{3}\)

由欧拉公式 \(n-e+f=2\) 可得 \(n-e+\frac{2e}{3}\ge 2\)

即 \(e\le 3n-6\)

其次证明 \(e \le \frac{k(n-2)}{k-2}\)

由于每个面至少由 \(k\) 条边围成，则由定理 7.2.2 有 \(\sum_{f\in F}d(f)=2e\ge kf\)

即 \(f\le \frac{2e}{k}\)

由欧拉公式 \(n-e+f=2\) 可得 \(n-e+\frac{2e}{k}\ge 2\)

即 \(e\le \frac{k(n-2)}{k-2}\)

综上所述，\(e\le \max \{\frac{k(n-2)}{k-2},3n-6\}\)

定理 7.2.8 \(Kuratowski\) 定理

图 \(G\) 是平图当且仅当 \(G\) 不包含 \(K_5\) 或 \(K_{3,3}\) 的剖分

证明待补充

引理 7.2.8.1

若 \(G\) 是非平面图，则 \(G\) 的每个剖分图也是非平面图

引理 7.2.8.2

若 \(G\) 是平面图，则 \(G\) 的每一个子图都是平面图

设 \(G\) 是有两顶点割的图。则存在不重子图 \(G_1\) 和 \(G_2\) 使得 \(V(G_1)\cap V(G_2)=\{u,v\}\) 以及 \(G_1\cup G_2= G\)，把 \(G\) 分成这样的两个子图，在 \(G_1\) 和 \(G_2\) 中用一条新边 \(e\) 链接 \(u\) 和 \(v\) ，得到图 \(H_1\) 和 \(H_2\) ，显然 \(G=(H_1\cup H_2)-e\)

引理 7.2.8.3

若 \(G\) 是非平面图。则 \(H_1\) 和 \(H_2\) 中至少有一个是非平面图

引理 7.2.8.4

设 \(G\) 是非平面的连通图，它不包含 \(K_5\) 和 \(K_{3,3}\) 的剖分图，且有尽可能少的边数，则 \(G\) 是 3-连通的简单图

定义 7.3 平面三角剖分图

每个面的度为 \(3\) 的平图称为平面三角剖分图

定理 7.3.1

每个简单平图都是某个简单平面三角剖分图的生成子图

证明： 点击查看证明

设 \(G\) 是简单平图，若 \(G\) 不是三角剖分图，则存在一个面的度 \(d(f)\ge 4\)

任选该面 \(f\) 的两条不相邻的边 \(uv\) 和 \(wx\) ，在 \(f\) 内部加入一条边 \(uw\) ，则得到一个新的简单平图 \(G'\) ，且 \(G\) 是 \(G'\) 的生成子图

重复上述过程，直到得到一个平面三角剖分图 \(G''\) ，则 \(G\) 是 \(G''\) 的生成子图

定理 7.3.2

任何平面三角剖分图 \(G\) ，都包含一个有 \(\frac{2e}{3}\) 条边的偶子图

为了方便考虑，下面的图都没有自环和多重边

定义 7.4 顶点着色

把 \(k\) 中颜色对图 \(G\) 的任意相邻两个顶点着不同颜色，则称为 \(G\) 的一个 \(k\)-着色，着色数 \(\chi(G)\) 是能给 \(G\) 着色的最小颜色数，若 \(\chi(G)=k\) 则称 \(G\) 是 \(k\) 色的

若对 \(k\) 色的图 \(G\) 的每个真子图 \(H\) ，都有 \(\chi(H)<\chi(G)\) ，则称 \(G\) 是 \(k\)-临界图

定理 7.4.1

若 \(G\) 是 \(k\) 临界图，则 \(\delta \ge k-1\)

证明： 点击查看证明

反证法：

设顶点 \(v\) 为 \(G\) 中度数最小的顶点，且 \(d(v)<k-1\)

由于 \(G\) 是 \(k\) 临界的，则 \(G-v\) 是 \((k-1)\) 色的

由于 \(\delta<k-1\) 则 \(v\) 的邻接顶点中最多有 \(k-2\) 种颜色，因此可以给 \(v\) 着上剩下的一种颜色，从而得到 \(G\) 的一个 \((k-1)\)-着色，矛盾

根据定理 7.4.1 可得：每个 \(k\) 色图至少有 \(k\) 个度不小于 \(k-1\) 的顶点

定理 7.4.2

对任意图 \(G\) 有 \(\chi \le \Delta+1\)

证明： 点击查看证明

\(G\) 是 \(k\) 色的，由于每个 \(k\) 色图，至少有 \(k\) 个度不小于 \(k-1\) 的顶点，则 \(\Delta \ge k-1\)，即 \(k \le \Delta+1\)

定理 7.4.3

临界图的顶点割不是团

证明： 点击查看证明

反证法：

设 \(G\) 是临界图，且 \(S\) 是 \(G\) 的一个顶点割，\(S\) 是一个团

记 \(G\) 的连通分支为 \(G_1,G_2,\ldots,G_k\) ，则 \(G-S\) 有 \(k\) 个连通分支

由于 \(G\) 是 \(k\) 临界的，则每个 \(G_i\) 都是 \((k-1)\) 色的

由于 \(S\) 是团，则 \(S\) 中的每个顶点都与 \(G_i\) 中的每个顶点相连，因此 \(G_i\cup S\) 是 \(k\) 色的

则 \(G\) 是 \(k\) 色的，矛盾

定理 7.4.4

每个临界图都是块

证明： 点击查看证明

若 \(v\) 是割点，则 \(\{v\}\) 是一个顶点割，由定理 7.4.3 可知 \(\{v\}\) 不是团，矛盾

定理 7.4.5

设 \(G\) 具有 \(2\) 顶点割 \(\{u,v\}\) ，则 \(d(u)+d(v)\ge 3k-5\)

证明： 点击查看证明

设 \(H_1=G_1+uv\)，\(H_2=G_2 \cdot uv\)

则 \(d_{H_1}(u)+d_{H_1}(v)\ge 2k-2\)

且 \(d_{H_2}(w)\ge k-1\)

这里 \(w\) 是将 \(u\) 和 \(v\) 合并后的新顶点

则 \(d_G(u)+d_G(v)=d_{H_1}(u)+d_{H_1}(v)+d_{H_2}(w)\ge 3k-5\)

定理 7.4.6 Brooks 定理

若 \(G\) 是连通图，且既不是完全图也不是奇环，则 \(\chi(G)\le \Delta\)

证明： 点击查看证明

设 \(G\) 是满足定理的 \(k\) 色图

不妨假定 \(G\) 是 \(k\) 临界的，则 \(G\) 是一个块，由于 \(1、2\) 临界图都是完全图， \(3\) 临界图是奇环，则 \(k\ge 4\)

若 \(G\) 有 \(2\) 顶点割

由上面可知 \(d(u)+d(v)\ge 3k-5\) ，则 \(\Delta \ge \frac{3k-5}{2}>k-1\)

设 \(G\) 是 \(3\) 连通的

（待补充）

色多项式待补充

定义 7.5 边着色

把 \(k\) 中颜色对图 \(G\) 的任意相邻两条边着不同颜色，则称为 \(G\) 的一个 \(k\)-边着色，着色数 \(\chi'(G)\) 是能给 \(G\) 着色的最小颜色数，若 \(\chi'(G)=k\) 则称 \(G\) 是 \(k\) 边色的

很显然，有 \(\chi' \ge \Delta\)

定理 7.5.1

若 \(G\) 是二分图则 \(\chi'=\Delta\)

定理 7.5.2 Vizing 定理

对任意简单图 \(G\) 有 \(\Delta \le \chi' \le \Delta+1\) 即 \(\chi'=\Delta\) 或 \(\chi'=\Delta+1\)

定义 7.6 面着色

把 \(k\) 中颜色对图 \(G\) 的任意相邻两个面着不同颜色，则称为 \(G\) 的一个 \(k\)-着色，着色数 \(\chi^*(G)\) 是能给 \(G\) 着色的最小颜色数，若 \(\chi^*(G)=k\) 则称 \(G\) 是 \(k\) 面色的

根据对偶图的定义可知，面着色问题等价于对偶图的顶点着色问题，因此有 \(\chi^*(G)=\chi(G^*)\)

定理 7.6.1

下面三个叙述等价

• 每个平面图都是 \(4\) 顶点可着色的
• 每个平图都是 \(4\) 面可着色的
• 每个简单 \(2\) 边连通 \(3\) 正则平面图都是 \(3\) 边可着色的

定理 7.6.2

任何图都是 \(5\) 可着色的