一种平面图色数的计算方法 (1)

版权所有,转载必须取得作者书面授权。

一种平面图色数的计算方法（蒋友皎 广西玉林市 537000）0 引言任何一个连通平面图都是五色图。 但是后来在平面图上经过多次试验， 没有找到一种平 面图一定要用 5 种颜色的。在一百多年前，有人猜测只要用 4 种颜色就够了，这就是世界上 著名的 4 色猜测问题。这个猜测一经提出，迷住了许多数学家，但是谁都无法用数学的方法 证明它。直到 1976 年，Appel 和 Haken 两人宣布了四色理论的证明方法。他们用大型电子 计算机分析了 2000 多种图包括几百万种情况， 花了大量的机器时间， 终于证明了这个问题， 从而解决了一百多年来引人关注的难题[1]。 Since the proving of the theorem, efficient algorithms have been found for 4-coloring maps requiring only O(n2) time, where n is the number of vertices. In 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas created a quadratic time algorithm, improving on a quartic algorithm based on Appel and Haken’s proof[2] [3] [11]. This new proof is similar to Appel and Haken's but more efficient because it reduced the complexity of the problem and required checking only 633 reducible configurations. Both the unavoidability and reducibility parts of this new proof must be executed by computer and are impractical to check by hand[4] [11]. In 2001 the same authors announced an alternative proof, by proving the snark theorem[5] [11]. In 2005 Benjamin Werner and Georges Gonthier formalized a proof of the theorem inside the Coq proof assistant. This removed the need to trust the various computer programs used to verify particular cases; it is only necessary to trust the Coq kernel[6] [11]. 显然这不是纯理论上的严格证明， 在计算机的辅助工作下四色定理的证明完成了， 但是 是否存在不需要借助计算机的纯数学方法的证明呢？本文将运用方程组计算连通平面图的 色数，对连通平面图的色数作出判定。1 基本性质定义 1 （1）V≠ 一个无向图是一个有序的二元组<V，E>,记作 G，其中 称为顶点集，其元素称为顶点或结点。（2）E 称为边集，它是无序积 V&V 的多重子集，其元素称为无向边，简称边[7]。 定义 2 设 G=<V，E>为无向图，ek=(vi，vj)∈E，则称 vi，vj 为 ek 的端点，ek 与 vi 或 ek与 vj 是彼此相关联的。若 vi≠vj，则称 ek 与 vi 或 ek 与 vj 的关联次数为 1，若 vi=vj，则称 ek 与 vi 的关联次数为 2，并称 ek 为环。任意的 vl∈V，若 vl≠vi 且 vl≠vj，则称 ek 与 vl 的关联 次数为 0 [7]。

版权所有,转载必须取得作者书面授权。

在图的定义中， G 表示无向图， 表示有向图， 用 D 但有时用 G 泛指图(无向的或有向的)， 可是 D 只能表示有向图。另外，为方便起见，有时用 V(G)，E(G)分别表示 G 的顶点集和边 集，若|V(G)|=n,则称 G 为 n 阶图，对有向图可做类似规定[7]。 在图 G 中，若边集 E(G)= ,则称 G 为零图，此时，又若 G 为 n 阶图，则称 G 为 n阶零图，记作 Nn，特别地，称 N1 为平凡图[7]。 在图的定义中规定顶点集 V 为非空集， 但在图的运算中可能产生顶点集为空集的运算结 果，为此规定定点集为空集的图为空图，并将空图记为[7]。无论在无向图中还是在有向图中，无边关联的顶点均称孤立点[7]。 定义 3 在无向图中，关联一对顶点的无向边如果多于 1 条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于 1 条，并且这些边的始 点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图， 既不含平行边也不含环的图称为简单图 。 定义 4 设 G=<V，E>为一无向图， v∈V，称 v 作为边的端点次数之和为 v 的度数，[7]简称为度，记做 dG(v)，在不发生混淆时，简记为 d(v) [7]。 定义 5 设 G=<V，E>为一平面图，面 W 由 w 条边组成，称 w 作为边的面次数之和为W 的度数，简称为度，记做 dG(w)，在不发生混淆时，简记为 d(w)。 定义 6 且 E' 设 G=<V，E>，G'=<V'，E'>为两个图(同为无向图或同为有向图)，若 V' G. 又若 V' V 或 E' VE，则称 G'是 G 的子图，G 为 G'的母图，记作 G'E，则称G'为 G 的真子图。若 V'=V，则称 G'为 G 的生成子图[7]。 设 G=<V，E>为一图，V1 V 且 V1 ≠ ，称以 V1 为顶点集，以 G 中两个端点都 E 且 E1≠ ，在 V1 中的边组成边集 E1 的图为 G 的 V1 导出的子图，记作 G[V1]. 又设 E1称以 E1 为边集， E1 中边关联的顶点为顶点集 V1 的图为 G 的 E1 导出的子图， 以 记作 G[E1] [7].。 定义 7 到 设 G 为无向标定图， 中顶点与边的交替序列 Г= G ， 为 的端点，r=1，2，…，l， ， 称为 分别称为 Г 的始点与的通路，其中终点，Г 中边的条数称为它的长度。若 则称 Г 为简单通路，又若，则称通路为回路。 若 Г 的所有边各异， 与 可能，则称 Г 为简单回路。若 Г 的所有顶点(除相同外)各异，所有边也各异，则称 Г 为初级通路或路径，此时又若 级回路或圈。将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈[7]。，则称 Г 为初

版权所有,转载必须取得作者书面授权。

定义 8 意的 E''设无向图 G=<V,E>，若存在 E'E，且 E'≠，使得 p(G-E')>p(G)，而对于任E'，均有 p(G-E'')=p(G)，则称 E'是 G 的边割集，或简称为割集。若 E'是单元集，即 E'={e}，则称 e 为割边或桥[7]。 定义 9 作 u～v. 设无向图 G=<V,E>, v∈V，规定 v～v. u,v∈V，若 u,v 之间存在通路，则称 u,v 是连通的，记由定义不难看出，无向图中顶点之间的连通关系 ～={（u,v）|u,v∈V 且 u 与 v 之间有通路} 是自反的，对称的，传递的，因而～是 V 上的等价关系[7]。 定义 10 设 G 为 n 阶无向简单图，若 G 中每个顶点均与其余的 n-1 个顶点相邻， 则称 G 为 n 阶无向完全图，简称 n 阶完全图，记做 Kn(n≥1) [7]。 定义 11 若无向图 G 是平凡图或 G 中任何两个顶点都是连通的，则称 G 为连通图，否 则称 G 是非连通图或分离图[7]。 易知，完全图 Kn(n≥1)都是连通图，而零图 Nn(n≥2)都是分离图[7]。 定义12 如果图 G 能以这样的方式画在曲面 S 上，即除顶点处外无边相交，则称 G 可 嵌入曲面 S.。若 G 可嵌入平面，则称 G 是可平面图或平面图。画出的无边相交的图称为 G 的平面嵌入。无平面嵌入的图称为非平面图[7]。 定义 13 设 G=<V，E>为无向图。 (1) 设 e∈E，从 G 中去掉边 e，称为删除 e，并用 G-e 表示从 G 中删除 e 所得子图。又 设 E' E，从 G 中删除 E'中所有的边，称为删除 E'，并用 G-E'表示删除 E'后所得子图。 V， 称从 G 中删除 V'中所有顶点为删除 V'， 并用 G-V'表示所得子图。 (2) 设 v∈V，从 G 中去掉 v 及所关联地一切边称为删除顶点 v，并用 G-v 表示删除 v 后所得子图。 又设 V' (3) 设边 e=(u， v)∈E， 先从 G 中删除 e， 然后将 e 的两个端点 u， 用一个新的顶点 w(或 v 用 u 或 v 充当 w)代替，使 w 关联除 e 外 u，v 关联的一切边，称为收缩边 e，并用 G\e 表示 所得新图。 (4) 设 u，v∈V(u，v 可能相邻，也可能不相邻，且 u≠v)，在 u，v 之间加新边(u，v)， 称为加新边，并用 G∪(u，v) (或 G＋(u，v))表示所得新图 。 定义 14 设无向图 G=<V,E>， 关于顶点之间的连通关系～的商集 V/～={V1,V2,…,Vk}， V Vi 为等价类，称导出子图 G[Vi](i=1,2,…,k)为 G 的连通分支，连通分支数 k 常记为 p(G) 定理1 (欧拉公式) 对于任意的连通的平面图 G 有[7] [7]。 n m r 2 其中，n，m，r 分别为 G 的顶点数，边数和面数[8]。 定理 2 设 G 是连通的平面图，且每个面的次数至少为 l(l≥3)，则 G 的边数 m 与顶点 数 n 有如下关系： m≤ 推论1 (n－2)[7]。K5与 K3,3都不是平面图。

版权所有,转载必须取得作者书面授权。

定义 15 设 e=(u，v)为图 G 的一条边，在 G 中删除 e，增加新的顶点 w，使 u，v 均与 w 相邻，称为在 G 中插入 2 度顶点 w。设 w 为 G 中一个 2 度顶点，w 与 u，v 相邻，删除 w，增 加新边(u，v)，称为在 G 中消去 2 度顶点 w[9]。 定义 16 若两个图 G1 与 G2 同构，或通过反复插入或消去 2 度顶点后是同构的，则称 G1 与 G2 是同胚的 。 定理 3 定理 4 定理 5 定理 6 也不 (库拉图斯基定理 1) 图 G 是平面图当且仅当 G 中既不含与 K5 同胚子图，[7] [7]含与 K3,3 同胚子图 。 (库拉图斯基定理 2) 图 G 是平面图当且仅当 G 中既没有可以收缩到 K5 的子图，[7]也没有可以收缩到 K3,3 的子图 。 若图 G 是平面图，则 G 的任何子图都是平面图 。[7] [7]由定理 5 立刻可知，Kn(n≤4)和 K1,n(n≥1)的所有子图都是平面图 。 若图 G 是非平面图，则 G 的任何母图也都是非平面图 。[7]定义 17 设 G 是某平面图的某个平面嵌入，构造 G 的对偶图 G*如下： 在 G 的面 Ri 中放置 G*的顶点 vi*.设 e 为 G 的任意一条边，若 e 在 G 的面 Ri 与 Rj 的公 共边界上， G*的边 e*与 e 相交， e*关联 G*的位于 Ri 和 Rj 中的顶点 vi*与 vj*， e*＝(vi*， 做 且 即 vj*)，e*不与其它任何边相交。若 e 为 G 中的桥且在面 Ri 的边界上，则 e*是以 Ri 中 G*的顶 点 vi*为端点的环，即 e*＝(vi*，vi*). 从定义不难看出 G 的对偶图 G*有以下性质： 1. G*是平面图，而且是平面嵌入。 2. G*是连通图。 3. 若边 e 为 G 中的环，则 G*与 e 对应的边 e*为桥，若 e 为桥，则 G*中与 e 对应的边 e*为环。 4. 在多数情况下，G*为多重图(含平行边的图)。 5. 同构的平面图(平面嵌入)的对偶图不一定是同构的[7]。 定义 18 对无环图 G 的每个顶点涂上一种颜色，使相邻的顶点涂不同的颜色，称为对图 G 的一种着色。若能用 k 种颜色给 G 的顶点着色，就称对 G 进行了 k 着色，也称 G 是 k-可着色的。若 G 是 k-可着色的，但不是(k-1)-可着色的，就称 G 是 k 色图，并称这样的 k 为 G 的色数，记作 χ(G)=k，不混淆时，色数 χ(G)也可简记作 χ 定理 7*[7]。[7]地图 G 是 k-面可着色的当且仅当它的对偶图 G 是 k-可着色的 。定义 19 连通无桥平面图的平面嵌入及其所有的面称为平面地图或地图， 地图的面称为 [7] “国家”。若两个国家的边界至少有一条公共边，则称这两个国家是相邻的 。 定义 20 对地图 G 的每个国家涂上一种颜色，使相邻的国家涂不同的颜色，称为对 G 的一种面着色，若能用 k 种颜色给 G 的面着色，就称对 G 的面进行了 k 着色，或称 G 是 k面可着色的。若 G 是 k-面可着色的，但不是(k-1)-面可着色的，就称 G 的面色数为 k，记作 χ*(G)=k 。 定义21 若图 G 有 χ*(G)=k，且对图 G 的面进行了 k 面着色，则称对图 G 正确面着色。 定义22 设已正确面着色的平面图 G 有 χ*(G)=k 且仅有 k 个色块，则称图 G 为基本 k面色图。易知，各色块两两相邻。 定义23 若图 G 有 χ(G)=k，且对图 G 的面进行了 k 着色，则称对图 G 正确点着色。[7]

版权所有,转载必须取得作者书面授权。

定义24 设已正确着色的图 G 有 χ(G)=k 且仅有 k 个色点，则称图 G 为基本 k-色图。易 知，各色点两两相邻。 引理 1 插入或消去 2 度顶点不影响图的面。 证 插入一个 2 度顶点时，图的顶点数和边数各增加 1，由欧拉公式知面数不变，显然 面和面的相互关系也没有改变；消去一个 2 度顶点时，图的顶点数和边数各减少 1，由欧拉 公式知面数不变，显然面和面的相互关系也没有改变。 引理2 对于基本 r-面色图 G，m，r (r 2) 分别为 G 的边数和面数，有m Cr2 。证 因为图 G 的每两个相邻的面都由一条边分隔且各个面两两相邻，所以由组合原理m Cr2引理3 对于基本 r-色图 G，m，n (n 2) 分别为 G 的边数和顶点数，有2 m Cn 。证 因为图 G 的每两个相邻的顶点都由一条边联结且各个顶点两两相邻，所以由组合原 理2 m Cn 。定理 8 (握手定理) 设 G=<V,E>为任意无向图，V={v1,v2,…,vn}，|E|=m，则 deg V 2mi i 1n[10]。设 G 是连通的平面图，且每个顶点的度数至少为 l ' l ' 3 ，则 G 的边数 m 与顶点数 n 有如下 关系：2m deg Vi l ' ni 1n2m l ' n定理 9r设 G=<V,E>为任意平面图，面 W={ w1, w2,…, wr}，|E|=m，则i deg W 2m 。i 1证 因为 G 是平面图，图中每条边至多为两个面的边界，所以总边数小于或等于 2m。 即k deg W 2m 。i i 1设 G 是连通的平面图， 且每个面的度数至少为 l l 3 ， G 的边数 m 与面数 r 有如下关系： 则

版权所有,转载必须取得作者书面授权。

n2m deg Wi l ri 12m l r2 色数计算重言式P Q Q P x ( P( x )) x( P( x))1 ○2 ○ x ( P( x)) Q x( P( x) Q ) x ( P( x)) P( x)4 ○3 ○Q x( P( x)) x(Q P( x )) ( P Q ) P Q6 ○5 ○[1]。引理 4 若图 G（χ(G)=k）是平面图，则存在基本 k-色图是平面图。 证 令命题 A（x）为“x 是 χ(G)=k” ；命题 B（x）为“x 是基本 k-色图” ；命题 C（x） 为“x 是平面图” ；则命题 A（x）为“x 非 χ(G)=k.” ；命题 B（x）为“x 非基本 k-色图” ；6 。令 P( x) A( x ) C ( x ) ， Q ( x) B( x ) C ( x ) ；则由○ ， C（x）为“x 非平面图” P( x ) A( x) C ( x) ， Q( x ) B( x) C ( x) 。 x ( Q( x)) x( P( x)) x ( P( x)) x( Q ( x )) x ( P( x)) x (Q ( x )) x ( P( x ) xQ( x )) x( P( x) Q ( x )) P( x) x(Q( x))命题 1：若存在非基本 k-色图或者非平面图，则存在图 G 非 χ(G)=k 或者非平面图。即 “ x ( Q( x)) x( P( x)) ” 。可推出命题 2：若图 G（χ(G)=k.）是平面图，则存在基本 k-色图是平面图。即“ P( x) x (Q ( x )) ” 。显然命题 1 有解为真，所以命题 2 亦真。又当3 由○ 1 由○2 由○4 由○5 由○

版权所有,转载必须取得作者书面授权。

命题 P 为“图 G（χ(G)=k）.是平面图”真时，命题 Q 为“存在基本 k-色图是平面图”亦真。 定理 10 设球面上任意的连通无桥平面图 G， 的色数为 χ(G)=n， 1、 G 有： 色数为 χ(G)=1； 2、色数为 χ(G)=2 或 3、 n m r 2 2 m Cn 2m l r l 3 ；其中 m，n，r 是基本 n-色图的边数、顶点数和面数， l 是面的度数。 证 由引理 4，有基本 n-色图。对基本 n-色图，可能存在 3 种情况：1、n=1 时，平凡 图，顶点数为 1，当然色数为 1；2、n=2 时，顶点数为 2，当然色数为 2；3、设面的度数为l l 3 ，由引理 2、定理 1、及定理 9，联立方程组，有 n m r 2 2 m Cn 2m l r 定理 11 l 3 ，毕。球面上任意的连通无桥平面图都有 χ(G) 4。证 设 χ(G)=n，由定理 10，有 n=1、n=2 或 n m r 2 2 m Cn 2m l r 2 Cn m l 3 ，得l n 2 ， l 2(1) l 2 n2 2 3l n 4l 02 2 3l 16l l 2 7l 2 20l 4 00 l 3 ，且 l 3 ，得 l 3 ，代人(1)，n 2 7n 12 03 n 4 χ(G) 4 毕。所以，对球面上任意的连通平面图各个顶点着色，使得相邻的顶点有不同的颜色，所用的颜 色可以不多于4种，即球面上的平面图都是4-可着色的。 定理12 环面上任意的连通无桥平面图有 χ(G) 7。 证 由欧拉公式有 n m r 0 ，代替原方程组的 n m r 2 ， 设 χ(G)=n，由定理10，有 n=1、n=2或 n m r 0 2 m Cn 2m l r l 3 ，得

版权所有,转载必须取得作者书面授权。

l 2 n 2 2 3l n 0 ，4 ， l 2 当 l 6时， 0 n 3 当 l =5、6时， 0 n 4 当 l 4 时， 0 n 5， 当 l 3 时， 0 n 7 χ(G) 7 毕。 0 n 3 所以，对环面上连通平面图的顶点着色，使得相邻的顶点有不同的颜色，所用的颜色可 以不多于7种，即环面上的平面图都是7-可着色的。 推 广 到 任 意 曲 面 上 连 通 平 面 图 的 色 数 χ(G) ， 若 图 G 的 欧 拉 示 性 数 d ，n m r d d 2 ，可以将其代入方程组来求解。推论 任意封闭曲面连通无桥平面图 G，若 n m r d d 2 且 χ(G)=n；有：1、 n＝1；2、n＝2；或3、基本 n-色图面的度数为 l l 3 ， n m r d 2 m Cn ， l 3 2m l r 整理后，， l 2 n 2 2 3l n 2dl 03 结论。本文就封闭曲面上平面图色数的计算运用拓扑变换的方法， 结合握手定理和欧拉公式给 出了一个平面图色数计算方法， 解决了对曲面上的平面图的色数的一个判断， 即什么样的曲 面上的平面图，它的最大色数是多少。且由定理 7 可同时得到平面图的最大面色数。 [参考文献] (References)[1] 徐洁磐，惠永涛. 离散数学及其在计算机中的应用[M]. 北京：人民邮电出版社, 1988. [2] Thomas, Robin. The Four Color Theorem[OL].[1995]. http://www.math.gatech.edu/~thomas/FC/fourcolor [3] Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin. "Efficiently four-coloring planar graphs"[A]. Efficiently four-coloring planar graphs, [A]. STOC'96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing[C]. ACM Press, pp. 571–575, doi:10.1145/237814.238005 [4] Thomas, Robin. "An Update on the Four-Color Theorem" [J]. Notices of the American Mathematical Society 45 (7): 848–859, [5] Thomas, Robin. Recent Excluded Minor Theorems for Graphs[OL].p. 14, http://people.math.gatech.edu/~thomas/PAP/bcc.pdf [6] Gonthier, Georges. "Formal Proof--The Four-Color Theorem"[J]. Notices of the American Mathematical Society 55 (11): 1382–1393, arXiv:math/0207061, Bibcode 2002math......7061A,

版权所有,转载必须取得作者书面授权。

[7] 北京大学计算机科学技术系理论研究室. 离散数学网络课件[OL]. [2002.1.5]. /courses/lssx/longtime/. [8] Kenneth H.Rosen. 离散数学及其应用[M]. 袁崇义 屈婉玲 王捍贫 刘田. 北京：机械工业出版社,2002. [9] 耿素云, 屈婉玲. 离散数学[M].北京：高等教育出版社. 2004. [10] 屈婉玲, 耿素云, 张立昂. 离散数学[M]. 北京: 清华大学出版社, 2005. [11] Wikimedia Foundation, Inc . Four color theorem[OL]. [2011.5.29]. /wiki/Four_color_theorem

本文来源：https://www.bwwdw.com/article/bvtq.html