细胞结构论文膜结构论文

357 医 药 与 卫 生 INTELLIGENCE······ ·················· 细胞形结构在四色定理证明中的作用 广西妇幼保健院 梁增勇 摘 要：四色猜想是已被美国数学家用计算机证明了的世界数学难题，但数学家 仍然在寻找一种简捷明快的书面证明方法，为此本文用图论的方法去研究找出了连 通图的细胞形结构的特点，并实现在任何平面图四色正常着色的方法，解决了四色 定理新的书面证明途径。 关键词：图 顶 连通图 圈 色数 细胞形结构模块图 著名的地图着色问题，在图论中可以化成图的色数问题。 在地图中，每个国家的区域是一个色块，事实上，令每个国 家的首都为顶（一个顶点对应一个色块），仅当两国有一段 公共国界线时，在两国首都相应的顶之间加一边，得到一个 图 G，x (G ) 即为地图染色问题所需的颜色数。证明四色猜 想问题，就是要证明任一平面图的色数≤４。如果使用 n 种 颜色把图 G 的每顶点分配一种颜色，且使得邻顶异色，则称 此为对 G 的顶的正常 n 着色。图 G 的顶的正常着色中所需要 的最小颜色种类数的最小值，称为 G的顶色数，简称色数 [1] . 图 1 各种图的表现形式 定理 1 任何多边形结构的连通图都可以在所有顶点间 增加邻接边使图结构变成三角形结构连通图，其图色数不会 减少 [2]。例如图 1中的 1和 2。 定义 1 任何复杂的三角形结构连通图可由以下结构组成 1、孤立的顶点简称孤顶；2、链：n 个顶点和 n-1 条边连接 组成的不闭合的路径；3、空圈：n 个顶点和 n 条边连接组成 的闭合的路径；4、细胞形结构：一个顶点邻接的所有顶点构 成圈的子图，我们称之为细胞形结构；同时把已经区分 好细胞形结构的连通图称为细胞形结构模块图（或细胞结构 模图），见图 1 中之 3、4。图 1 之 4 是已正常着色的细胞结 构模图，其中：中心顶点称细胞核顶点，简称核顶点；而其 它顶点称为细胞壁顶点，简称壁顶点。所有壁顶点与它们之 间的邻接边称为细胞壁边，简称壁边，同时以粗线条表示。 所有壁顶点和壁边构成细胞壁组织结构子图，见图 1中之 5。 定理 2 细胞壁组织子图的色数≤ 3 证 将规划好的细胞形结构模图，去掉核顶点，余下的 即为细胞壁组织结构子图，见图 2 之 5。假设将各顶点排序 编号，逐个完成每个顶点的着色直至完成整个细胞壁组织结 构子图的着色。那么：1、单壁结构：细胞壁组织仅由一层或 一条路径组成，每个顶点仅与另两个顶点邻接，新顶点可用 与另两个顶点不同的颜色。当壁组织构成外圈，色数=2（偶圈） 或 =3（奇圈）；2、双壁结构：细胞壁组织仅由三角形结构 子图组成（无核顶点，不构成完整的细胞形结构），在壁顶 点的着色顺序是每下一个三角形中新顶点与两个旧顶点邻接， 新顶点可用与另两个顶点不同的颜色，所以色数 =3。图 1 中 的 5 是单双壁结构结合的细胞壁组织子图。综上所述，整个 细胞壁组织结构子图可以在三色范围内完成正常着色。即细 胞壁组织结构子图色数≤ 3。 定理 3 细胞形结构子图的色数≤ 4，外圈色数≤ 3。 证 细胞形结构子图的顶点包括核顶点和细胞壁顶点， 由定理 2 可知细胞壁组织子图的色数≤ 3，可用黑和灰色。 而核顶点可用白色，则细胞形结构子图的色数≤ 4，外圈色 数≤ 3。 定理 4 无分支连通图图色数 =4，外圈色数 =3 证复杂的连通图可包含和导出多个无割点的分支（块）， 即无分支连通图。如图 2 中的 1 是一连通图，2 是由它导出 的三个分支（块）。无分支连通图可化作细胞形结构模图， 顶点和边的结构没有变化，因此它的色数和细胞形结构模图 完全一样。 图 2 连通图和它的分支（块） 定理 5 连通图的色数≤ 4。 证已知连通图可以导出的没有割点的分支子图（块）仅 可能是单顶、单路、空圈, 和无分支连通图。很明显，1、单顶、 单路、空圈的图色数≤ 3，分支的子图的色块可以使用与割 点不同的另三种颜色正常着色。2、而根据定理 4 无分支的连 通图也可转换为图色数≤４，外圈色数≤ 3 的细胞形结构模 图，与割点邻接并可正常着色（割点用不同于分支（块）的 外圈色块的颜色即第四色白色，因为约定外圈顶点不用白色。 另外，当连通图的割点就是无分支连通图外圈的顶点，割点 就用壁顶点的颜色，更不会增加图色数。因此在四色问题上， 分支（块）与主图没有颜色冲突；换句话说，它们可以看作 是独立的互相没有影响的。 定理 6 （四色定理）任何平面图的色数≤ 4。 证任何复杂的平面图可化作互相独立的子图，这些子图 包含孤顶、链、空圈和连通图。 由于这些互相独立的子图在四色关系上也是互不影响的。 同时，很明显孤顶、链、空圈的图色数≤ 2， 因此平面图的 色数主要由连通图子图的色数所决定。由定理 5 可知，连通 图的色数≤ 4，因此，任何平面图的色数≤ 4。 至此我们已经利用细胞形结构顺利地完成四色定理的证 明。 参考文献： [1] 殷剑宏、吴开亚：《图论及其算法》，中国科学技 术大学出版社，2003 年。 [2] 王树禾：《图论》，科学出版社，2004 年。