我给出了一个四色定理的证明

落日映苍穹つ 2021-10-19 03:14 241阅读 0赞

四色定理， 实际上是 看 平面图形 的 “共聚” 行为 最多可以 发生 在 几个 图形 上  。

我们先来看看 什么 是 地图 ：

地图 就是 平面 上  n 个 图形  。

图形 之间 会 “接壤” ，        接壤 就是 指 2 个 图形 有  公共边 ，   这个 公共边 可以是 直线线段， 也可以是 曲线线段，

但是 公共点 不算 接壤，     就是说  2 个 图形 之间 没有 公共边，  只有 公共点，   这样 是 不算 接壤 的 。

因为 如果 公共点 算 接壤 的 话，   如下图，    从 o 点 发出 n 条 射线，  可以 把 o 点 周围 的 区域 分为 n 个 区域，

如果 公共点 算 接壤 的 话，   那么， o 点 周围 的 n 个 区域 都是 接壤 的，  需要 用  n 种 颜色 来 把 它们 区分 开 。

![1388256-20190704163308336-588900903.png][]

接下来 我们 就来 看看 最大 共聚 会 发生在 几个 图形 ：

共聚 ，   就是 有 n 个 图形，  每一个 图形 都 和 其它 所有 图形 接壤，  这样 就称为 这 n 个 图形 共聚  。

显然，    对于 共聚 的  n 个 图形， 需要有   n 种 颜色 来 区分 它们  。

那么，   在 二维平面 上，  最多 能有 多少个 图形 发生 共聚  ？

最多 能有 多少个 图形 发生 共聚，    就是 一张 地图 最少 需要 多少种 颜色  。

最多 能有 多少个 图形 共聚 称为  “最大共聚”   。

显然 ，     四色定理  就是 要   求取    最大共聚  。

我们 来 看看 最简单 的 共聚 情形， 就是 2 个 图形 的 共聚 ，    这其实就是 2 个 图形 挨 在一起 ：

![1388256-20190704204001807-1632211326.png][]

再看看 3 个 图形 共聚 的 情形 ：

![1388256-20190704204434769-1468152700.png][]

再看看 4 个 图形 共聚 的 情形 ：

![1388256-20190704205807459-1597165335.png][]

可以看到，  A 和 B C D 接壤，  B 和 A C D 接壤，  C 和 A B D 接壤，  D 和 A B C 接壤 。

接下来 我们 再加入 第 5 个 图形 ，     但是 我们 发现 ， 在 ABCD 共聚 的 这个 组合图形 里，  B 已经被 包住了，   “裸露” 在 外面 的 图形 只有   A C D ，

这样，    加入 第 5 个 图形 也  只能  最多 和  A C D  接壤，   即 形成 的 共聚 最多 还是 4 共聚 （4 个 图形 的 共聚）：

![1388256-20190704211543595-95899189.png][]

如图，   E 和 A C D  组成了  ACDE  4 共聚   。

当然，   E 也可以 不和 A C D 组成  4 共聚，  比如 ：

![1388256-20190704234221631-1039677456.png][]

这是  E 和 A D  组成了  ADE  3 共聚，       ABCD  仍然是  4 共聚  。

我们可以 观察 到 一个 现象 或者说 规律，    A B C D  形成  4 共聚 时，    形成了 一个  “封闭体” ，  把  B 包在了 里面，

![1388256-20190704205807459-1597165335.png][]

D   要 和 A 接壤 必须 要  绕过  B  C  ，    绕过 B C  后  一旦 和 A 接壤 就会把  B 或 C 封闭 起来 ：

如果 D 绕过 B 和 A 接壤，   就会 把 B 封闭 起来，  即   A C D   形成 封闭体 把  B  封闭 起来，

如果 D 绕过 C 和 A 接壤，   就会 把 C 封闭 起来，  即   A B D   形成 封闭体 把  C  封闭 起来，

我们 根据 这个  现象 / 规律   来 证明   二维平面 上 图形 的 共聚 最大 是  4 共聚 ，  证明如下 ：

不过 在 证明 之前，   我们 还可以来看看 几种 情况，  比如  4 共聚 的 内部 包含了 其它 图形：

![1388256-20190704235822419-1902824646.png][]

如图，    ABCD  的 内部 包含了  x （在   B 的 右上角） ，   但是这并不影响 ABCD  4 共聚，   ABCD  4 共聚 仍然 成立 。

4 共聚  内部 包含了 空白，  空白 就是 地图 的 空白：

![1388256-20190705000510286-470884662.png][]

如图，    ABCD  内部 包含了 空白 （在   B 的 右上角）  ，      这也 不影响 ABCD  4 共聚，   ABCD  4 共聚 仍然 成立 。

4 共聚 内部 包含了 4 共聚：

![1388256-20190705000739982-1184906736.png][]

这里 有       BDxy   4 共聚  和    ABCD   4 共聚，

好，   现在 我们  就开始 证明 ：

假设 有  A B C D E   5 个 图形 形成了    5 共聚  ，    那么 根据 共聚 的 定义，   共聚 的 每一个 图形 和 其它 的 所有图形 都有 接壤，

所以，   5 共聚 中 任意 的 4 个 图形 都是 4 共聚，

所以，   对于  ABCD   4 共聚 ，   会 形成 一个 封闭体，   设 A C D 形成 封闭体，  将 B 封闭 在 里面，

若 E 在 ACD 封闭体 外部，    则 E 与 B 无法 接壤 ，      这表示 ABCDE 无法形成   5 共聚，   与  题设 ABCDE 形成 5 共聚 矛盾，

故 E 在 ACD 封闭体 外部 的 情形 下， 题设 ABCDE 形成 5 共聚   不成立，  由此 证明  4 共聚 和 外部 的 图形 不能 形成   5 共聚  。

同样的道理，  可以 证明   4 共聚 和 外部 的 图形 不能 形成 大于 4 的 共聚  。

这个 证明 称为 证明(1)  ，     后面 还会用到  。

接下来 来 看  E 在 ACD 封闭体 内部 的 情形，

因为 ABCDE 是 5 共聚，   所以  E 在 ACD 内部，   会和  A B C D  形成 4 个 4 共聚，  ABCE,  BCDE,  ACDE,   ABDE ，

这就是 4 共聚 内部 包含 4 共聚 的 情形，  这样就 寻找 最内层 的 4 共聚，

设 ABCE 是 最内层 4 共聚，    ACE  形成 封闭体，  将 B 封闭 在 里面，    则  D 和 B 不能 接壤，  这表示 ABCDE 无法形成   5 共聚，   与  题设 ABCDE 形成 5 共聚 矛盾，

故 E 在 ACD 封闭体 内部 的 情形 下， 题设 ABCDE 形成 5 共聚   不成立，    由此 证明  4 共聚 和 内部 的 图形 不能 形成   5 共聚  。

此为 证明(2)  。

结合 证明(1) 和 证明(2) ，    可以证明，      4 共聚 不能 和 外部 图形 组成  5 共聚，   也不能 和 内部 图形 组成  5 共聚  。

所以，    二维平面 上 的  5 共聚 是 不成立 的  。

但是，  要让 这个 证明 成立，   还要 证明 一点，  即 “最内层的  4 共聚”  是 存在的，

什么情况下， 最内层 的 4 共聚 不存在？   循环 的 情况下  。

比如，    有    m, n, p, q     4 个 4 共聚，    m 是 n 的 外层， n 是 p 的 外层， p 是 q 的 外层， q 是 m 的 外层，

注意，     最后的 q 是 m 的 外层  就 导致了 循环，     这样 m n p q   循环相套，   就 不存在 最内层 的 4 共聚 了  。

接下来 我们 要 证明 循环 是 不存在 的：

因为 4 共聚 形成了 封闭体，    所以 4 共聚 内部 的 图形 不可能 和  封闭体 外部 的 图形 接壤，   所以 不可能 和 封闭体 外面 的 图形 形成 共聚，

所以 4 共聚 内部 的 4 共聚  不可能 成为 外层 4 共聚 的 外层， 更不可能 成为 外层 的 外层 。

所以 循环 是 不存在 的，   最内层  4 共聚 是 存在 的 。

这样 就 证明完成 了 。

所以，    二维平面 上 的  5 共聚 是 不成立 的  。

同样的道理 ，    可以 证明 二维平面 上 其它 大于 4 的 共聚 （6 共聚 、 7 共聚 、 ……）    也是 不成立 的  。

所以，    二维平面 上 的 共聚 不会 超过 4 共聚 ，    4 共聚 是 二维平面 上 的 最大 共聚  。

上述 证明 是 用 矩形 和 多边方形 举例，  但是 可以 推广到 任意 多边形 和 曲线图形  。

由以上  ，          可以证明  二维平面  的  图形  的 最大共聚 是  4 共聚 ，    4 共聚 需要  4 种 颜色 来 区分 4 个 图形，

所以  一张 地图 最少 需要 的 颜色 是 4 种 。

证明完成  。

这个 证明 用到 了 2 个 核心 的 直观，   一个是 封闭体，  一个是 封闭体 的 “外部” 和 “内部” ，  其它部分 基本上 算是 逻辑  。

四色定理  反映 的 是  二维平面 上的  图形 可以 通过 延伸 生长 来 和 尽量多 的 其它 图形 接壤，  但是 在这个 过程 中，  也会 阻断 其它 图形 之间的 接壤  。

这里面 有一个 平衡关系 ，    这个 平衡关系 就是 二维平面 上 图形 的 最大共聚 是  4 共聚 ，     即  四色定理  。

转载于:https://www.cnblogs.com/KSongKing/p/11133193.html

[1388256-20190704163308336-588900903.png]: /images/20211018/f0032ffc2b7e47ad99d7fcc12db26555.png
[1388256-20190704204001807-1632211326.png]: /images/20211018/4bcc386e125d48e28287d597e14f4273.png
[1388256-20190704204434769-1468152700.png]: /images/20211018/36050674f0be4a2d8274e63ad10ad1b0.png
[1388256-20190704205807459-1597165335.png]: /images/20211018/fd7d4b2234ce4b59a4c26a688d61ea2b.png
[1388256-20190704211543595-95899189.png]: /images/20211018/d30c5365f4ac449187ea88a9e2a4b7ab.png
[1388256-20190704234221631-1039677456.png]: /images/20211018/6f8d1d8f79b648c5a592198c6764314b.png
[1388256-20190704235822419-1902824646.png]: /images/20211018/257ac90a02ab462abca3c78ba214c666.png
[1388256-20190705000510286-470884662.png]: /images/20211018/9717794f29cc45fcbe9ade55b873b3b4.png
[1388256-20190705000739982-1184906736.png]: /images/20211018/c73a4243200a48f6b5dc039b72626fc6.png