四色图论
——四色问题解的存在性及求解方法

杨 名 生

( 大连理工大学 工程力学研究所, 辽宁 大连 116024 )



四色图论
——四色问题解的存在性及求解方法

杨 名 生*

( 大连理工大学 工程力学研究所, 辽宁 大连 116024 )

直接从四色问题出发，建立图论的另外一个新体系．在提出区域、边界线、结点等定义，对复杂地图进行分层简化后，得到体系的3个基本定理，又用链路这一工具，证明任意有限个区域地图的四色解存在并给出了求解方法．

图论；四色问题；区域；边界线；结点；链路

0 引 言

图论起源于Könisberg七桥问题和Guthrie的四色猜测．Euler图给出前者一个否定的结果，并推动图论的发展，建立了图论的传统体系．它从确定事物的点(称为顶点)出发，通过两点间连线(称为边)的集合构成线状图(有向图或无向图，平面图或非平面图)，并用矩阵工具对路径、回路、信号流图等规律进行研究．同时也推动了四色问题的研究[1-2]．20世纪70年代，Appel和Haken用当时的电子计算机经过近千小时的运算证明四色问题[3-4]，直到80年代才得到学者的首肯，原因是其几百页的逻辑推理公式太繁杂，数学界更期待有简捷的常规证明[4-5]．

四色问题可简述如下：任何平面地图都可用4种颜色着色，使其相邻区域着色不同[1]．

引导图论诞生的四色问题，具有不同于七桥问题的特点，它关心的是区域的相邻性．区域有很大的任意性，本文提出一系列简化处理方案并引入链路等新概念，将求解四色问题简化为求基础地图的四色解，并最终解决四色猜测问题．

1 预备知识[6]

1.1 约定和定义