CHT11-平面图&图的着色

平面图

可平面的

[! 定义1]
如果一个图能画在平面上，使得它的边仅在端点相交，则称这个图为或说它是可平面嵌入的，平面图G的这样一种画法，称为G的一个平面嵌入

平面图的平面嵌入称为平图

eg：

Jordon约当定理

本节中我们会介绍Jordon约当定理来说明平面图的一个基本的相交判定，从而帮助理解什么样的图是可平面的

[! 定义2]
Jordon曲线:

一条连续的、自身不相交的封闭曲线称为Jordon曲线

外部闭包、内部闭包:

J的外部，extJ，外点，extJ与J之并称为extJ的闭包，记为ExtJ;另一部分(不含曲线J称为J的内部，记为intJ，intJ的点称为J的内点，intj与J之并称为intJ的闭包，记为IntJ

[! 引理(Jordon约当定理)]
设J是一条Jordon曲线，任何连接J的内点与外点的引理的曲线必与J相交

事实上，Jordan曲线定理（Jordan Curve Theorem）是拓扑学中的基础定理。设 JJ是一条Jordan曲线（即平面上的一条简单闭合曲线，无自交且连续）。它断言：

平面被分割：J 将平面分成两个不相交的区域——
- 一个有界的内部（Interior）
- 一个无界的外部（Exterior）
连通性隔离：
任何连接内部点 A 和外部点 B 的连续曲线 γ，必与 J相交

看起来似乎显然的事情还是蛮难证的，花费了10来年才被严格证明。

趣事

毕竟仔细想想这确实不是一个很平凡的事情，它还有高维度版本，也就是一个拓扑球，也划分了内部和外部。这其实就回答了我高中时对高斯定理的一个疑惑，所谓的闭合球面，到底如何界定内外呢（（

有这个疑惑还是因为中国古人的智慧（雾）

《庄子·列御寇》中，庄子临终前弟子想厚葬他，庄子却说：
“吾以天地为棺椁，以日月为连璧，星辰为珠玑，万物为赍送。”

竹林七贤之一的刘伶裸身屋中，人称其无礼，他却答：
“我以天地为栋宇，屋室为裈衣（裤子），诸君何为入我裈中？”
（出自《世说新语·任诞》）

即然如此，那又为什么不能以内为外，以外为内？为什么是天地在球的外部，而不是球裹住了天地呢？（滑稽）

总之，高中的时候我对这个看似显然的事情在1天的思考过后选择了认为这确实是对的，肯定了能划分这个事实。_{果然不如数学家们啊，不过让我证也无从下手就是了}

好了不扯了，这个定理保证了一切(包括不平凡的)连续闭合曲线也可以有这么好的性质。比如分形曲线（科赫雪花）无处可微

eg:

你已经学会了Jordon约当定理，来试试证明K5是非平面图吧！

例1: 证明 K5不是平面图.
证明: 要证明它不是平面图, 按定义可知它应该是不能平面化, 即除端点外有相交的边存在。
假设K5是平面图, 其顶点集合为 $\{v_1, v_2, v_3, v_4, v_5\}$ , 并且平面化的图为 $\tilde{K}_5$ , 在 $\tilde{K}_5$ 中必有回路存在 (因为任何一对顶点都相邻)
假设 $C_1: v_1v_2v_3v_4$ 为平面上的一条Jordon约当曲线, 则 $v_4, v_5$ 两点必在约当曲线 $C_1$ 的外部或内部, 可分三种情况:
(1) 若一个在 $C_1$ 的内部另一个在外部。又因为 $v_4, v_5$ 在 $K_5$ 中必邻接, 所以由约当定理可知, $v_4, v_5$ 这条边必与 $C_1$ 相交, 与 $\tilde{K}_5$ 是平面化的图相矛盾
(2) 若 $v_4, v_5$ 都在 $C_1$ 的内部, 由于 $v_5$ 必与 $v_1, v_2, v_3$ 邻接, 则 $v_4$ 必在 $v_1, v_2, v_5, v_1$ 、或者 $v_1, v_3, v_5, v_1$ 、或者 $v_2, v_3, v_5, v_2$ 中。不妨设 $v_4$ 在 $v_1, v_2, v_5, v_1$ 中, 而此时 $v_3$ 在该曲线的外部, 由于 $v_4, v_3$ 在 $K_5$ 中也是相邻的, 所以由约当定理可知 $(v_4, v_3)$ 与 $v_1, v_2, v_5, v_1$ 相交, 与 $\tilde{K}_5$ 是平面化的图相矛盾。
(3) 若 $v_4, v_5$ 都在 $C_1$ 的外部, 由于 $v_4$ 与 $v_1, v_2, v_3$ 邻接, 则 $v_1$ , $v_3$ 必存在于 $v_4, v_2, v_3, v_4$ 、或者 $v_4, v_1, v_2, v_4$ 内部。而 $v_5$ 则在它们的外部。约当定理, 与 $\tilde{K}_5$ 是平面化的图相矛盾。

综上, K5是非平面图。

可平面的判定

本节中我们会给出一些更加好用的条件来判定是否可平面，主要是点，边，和面之间的关系。

[! 定义3 ]
设G是一个平图，则G把平面划分成若干个连通区域，每个连通区域的闭包称为G的一个面，其中恰有一个无界的面，称为外部面

每个面所关联的边，称为面的次数，Deg®

[! ] 定理1
$G = (V, E)$ 是有 $m$ 条边的平面图，则
$\sum_{all\_regions} \deg(R) = 2m \qquad |E| = m$

[! ] $\star$ 定理2 (Euler 公式)
若 $G$ 是连通平面图，则 $v-\varepsilon+f=2$
其中， $f$ 是 $G$ 的面数. （这个公式称为Euler公式）

证明蛮多的，不多赘述。教材用的是归纳法

欧拉公式本身就是一个平面图的必要条件，而其也有很多推论

推论1 给定平面连通图G，则G的所有平面嵌入有相同的面数。

推论 2 （平面图的必要条件）若G是简单平面图， $n \geq 3$ ，则 $m \leq 3n - 6$ 。

证明：注意到每个面至少由3条边围成，$d(F_{i}) $

推论 3 若平图G的每个面由至少四条边围成，则

$\quad m \leq 2n - 4。$

推论 3 另一论述若n≥3, 且平图G没有长度为3的回路，则

$\quad m \leq 2n - 4。$

这些推论的证明都是较容易的，不多赘述。

图论中的同胚:
两个图G,H被称为是同胚的（homeomorphic）是指它们可以通过同一个图在其边上添加一些二度点得到。

解释：感觉像是两个图具有一个包含了最基本的连通性的“公约图”？可以对连通的边进行各种增加"关节"的操作，不过和拓扑意义上的同胚不太一样，至少没像研究拓扑问题时那么好,除非当我们并不关注边和度这类信息时（

引入图论中的同胚主要是为了介绍下面这个定理

[! 定理3（非平面图的充要条件）]
Kuratowski定理(1930)：一个图是非平面图当且仅当含有同胚于K3,3 或 K5的子图

这个定理的直接推论就是K3,3和K5是非平面图

[! ] 定理 4
在平面简单图G中，至少存在一个顶点 $v_0$ ，使 $d(v_0) \leq 5$ 。
(该定理是证明 “五色定理” 的基础。)

证明：因为G是简单平面图
当 n ≤6 时结论成立
当 n > 6 时不存在 “至少一个顶点 $v_0$ ，使 $d(v_0) \leq 5$ ”，所有顶点的度数都大于5
$\sum \text{deg}(v) = 2m \geq 6n$ 即 $m \geq 3n$
与推论1 $m \leq 3n - 6$ 矛盾
平面简单图中至少存在一个顶点的度数小于等于5

图的着色

这一节感觉自己几乎都是在抄书。。幸好有chatbox不用手动抄，以后有理解了可能会重置吧

点着色问题

[! 定义]
设G是一个图，对G的每个顶点着色，使得没有两个相邻的顶点着上相同的颜色，这种着色称为图的正常着色

若图G的顶点可用k种颜色正常着色，称G为k可着色的，使G是k可着色的数k的最小值称为G的色数，记为 $\chi(G)$ ，如果 $\chi(G)=k$ ，则称G是k色的

着色数记作： $\chi(G)$

[! 定理1]
(1)对于完全图Kn，有 $χ(Kn)=n$ ， $χ(\sim Kn)=1$ 。

(2)对于 $n$ 个顶点构成的圈Cn，当 $n$ 是偶数时， $χ(Cn)=2$ ，当 $n$ 是奇数时， $χ(Cn)=3$ 。

(3)对于非平凡树T，有 $χ(T)=2$ 。

(4)G是二分图，当且仅当 $χ(G)=2$ 。

四色猜想

五色定理（夕伍德定理）

这个定理的证明能看懂，但是没什么想说的，可能境界不够吧，所以暂时不写什么了。

面着色问题

为了讨论图的面着色问题，我门需要用到下面的定义

[! 定义2]
割边（CHT 9中已介绍）

地图：一个没有割边的连通平面图

实际上，我们不难联想到，面与顶点之间具有一定的结构相似性。比如任意两个面之间的相邻关系和点之间的相邻关系。

对于一些图，我们很想把面的着色转化为点来讨论，这样就省去了很多工夫。

下面定义的对偶图就做到了这一点。

[! 定义]
给定一个平面图 $G$ , 它的每个面的边界便得到确定。这样, 由图 $G$ 可以导出另一个图 $G^*$ , 称为图 $G$ 的对偶图。

对偶图：满足下列条件的图 $G^*$ 称为平面图 $G$ 的对偶图。

$G$ 中每个确定的面 $r_i$ 内设置一个顶点 $v_i^*$ 。

若面 $r_i$ 和 $r_j$ 的共同边界 $e_k$ , 则有一条边 $e_k^*=(v_i^*, v_j^*)\in E(G^*)$ , 并与 $e_k$ 相交一次。

若 $e_k$ 处于面 $r_i$ 之内, 则 $v_i^*$ 有一自环 $e_k^*$ 与 $e_k$ 相交一次。

很明显, 定义本身就是图 $G$ 的对偶图构造算法, 它也称为 $D$ (drawing)过程。

eg:

值得注意的是,同构的图的对偶图未必同构

这是因为对偶图在确定边的过程中依赖于原图中面的位置相邻关系,但同构的G不需要保持面的位置关系.

总体而言,从定义不难看出以下几点:

$G^*$ 为平面图。
若边 $e$ 为 $G$ 中的环, 则它对应的边 $e^*$ 为 $G^*$ 的割边; 若 $e$ 为 $G$ 中的割边, 则 $e^*$ 为 $G^*$ 的环;
同构的图的对偶图不一定是同构的。

我们可以注意到对偶图具有以下性质:

[! 性质]
性质1 若G是平面图，则G存在唯一的对偶图G*。

性质2 若G是平面连通图，则 $(G^*)^* = G$ 。

性质3 若G是平面图，则G*是连通图。

感兴趣的话读者自证，我懒了

[! ] 定理1
平面连通图G与其对偶图G的顶点、边和面之间存在如下对应关系:
(1) $m = m^*$ (边数不变),

(2) $r = n^*$ （对偶图的顶点数等于面数）,

(3) $n = r^*$ ,

证明 (1), (2)的成立由定义是显然的。(3)因为G和G* 都是连通的平面图, 都满足欧拉公式,所以也成立

[! ] 定理 2
G 有对偶图的充要条件是 G 为平面图。

证明：
充分性由对偶图构造算法 (D(drawing)过程）得证。
必要性即非平面图没有对偶图。由库拉托夫斯基定理, 非平面图一定含有与 K_5 或 K_{3,3} 同胚的子图。
因此如果 K_5 和 K_{3,3} 图没有对偶图, 那么含有 K_5 或 K_{3,3} 同胚子图的图也没有对偶图。
(1) 对 K_5 图, m = 10, n = 5, r ≥ 7。
假定 K_5 有对偶图, 由定理 1, m* = 10, n* ≥ 7。
由于 K_5 中没有自环和多重边, 故 deg(v_i*) ≥ 3，
$\Sigma deg(v_i*) \geq 3 \times 7 > 2m* = 20$ , (矛盾）因此 K_5 没有对偶图。
(2) 对 K_{3,3} 图, m = 9, n = 6, r ≥ 5。
假定 K_{3,3} 有对偶图, 由定理 1,
m* = 9, n* ≥ 5。
由于 K_{3,3} 中每个面的边界数至少为 4, 故 deg(v_i*) ≥ 4
$\Sigma (v_i*) \geq 4 \times 5 > 2m* = 18$ (矛盾)，因此 K_{3,3} 没有对偶图。
综上所述, 定理得证。

利用对偶原理, 对地图的着色研究就变成了点着色的研究。同时也可以使问题转化的十分简单

边着色

这里就几乎一笔带过了，不过我个人猜是因为边图不像对偶图那样性质良好，毕竟在转化为线图的过程中，似乎丢失了更多信息

[! ] 定义
边着色: 若图G的任何两条相邻的边着有不同的颜色，称G是可边着色或正常边着色。

图G的正常边着色所需的最少颜色数目称为G的边色数k，记作 $χ'(G) = k$ ，称G是可以k-边着色的。

[! ] 定义
线图: 若图L(G)中的顶点与G的边一一对应，L(G)中的两个顶点是邻接的当且仅当对应的边在G中是邻接的，则称L(G)是图G的线图(line graph)。

与点色数不同，边色数有着与图的最大点度相关的简明结论

[! ] 定理
设G是简单图, 则 $\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1$

第一个不等式由定义直接得到
定理说明, 对于简单图, $\chi'(G) = \Delta(G) \text{ 或 } \chi'(G) = \Delta(G) + 1,$

但究竟哪些图的 $\chi'$ 是 $\Delta(G)$ , 哪些是 $\Delta(G) + 1$ ,
至今还是一个没有解决的问题。
对于二分图和完全图已经得到解决。
如下：

[! ] 定理
若G(n, m)是二分图, 则 $χ'(G) = Δ(G)$ 。
证明 (略)

[! ] 定理
n>1，当n为奇数时， $χ'(K_n) = n$ ；而当n为偶数时， $χ'(K_n) = n - 1$ 。
证明 (略)