当前位置：文档之家 › 四色定理算法

四色定理算法

  • 格式：docx
  • 大小：15.20 KB
  • 文档页数：2

四色定理算法

四色定理（four color map theorem）是一个著名的数学定理[1]，即对任意的（平面上的）地图染色，要求相邻的国家颜色不同，四种颜色即可完成着色。

南非数学家法兰西斯·古德里在1852年提出“四色问题”或“四色猜想”。证明宽松一点的“五色定理”（即“只用五种颜色就能为所有地图染色”）很容易，但是四色定理证明持续了很长时间。

四色定理不是地图学的定理，四色定理是第一个由计算机证明的数学定理。1976年，哈肯及其学生在伊利诺伊大学（即现在UIUC）的IBM360电脑上编程，经过电脑1200小时的验证，他们终于在6月证明四色定理。1976年6月22日，哈肯和阿佩尔在于多伦多大学召开的美国数学学会（A.M.S.）夏季会议公布他们的结果。不久，伊利诺伊大学数学系的邮戳上加上了“四种颜色就够了”（FOUR COLORS SUFFICE）的一句话，以庆祝四色猜想得到解决。1977年，哈肯和阿佩尔将结果写成名为《任何平面地图都能用四种颜色染色》（Every planar map is four colorable）的论文，分成上下两部分，发表在《伊利诺伊数学杂志》（Illinois Journal of Mathematics）上[2][3].

这是现在伊利诺伊大学大学厄巴纳香槟分校数学系主楼（离我们CyberGIS办公楼大约2分钟步行距离）。我和同事曾在午饭后参观过UIUC数学楼，学术氛围非常浓厚。

四色定理被证明后，经历了十几年争议、修正和改进的过程。1986年，哈肯和阿佩尔应《数学情报》杂志的邀请，发表了1篇清晰易懂的证明总结文章，1989年的最终的定稿超过400页（貌似图论中的经典定理证明都比较长）。

四色定理不是地图学定理，但它是地图学的经典问题。地图设计的专著中对四色定理描述很少。四色定理在地图中的应用其实没有想象的那么广，其实原因比较多，第一个是地图着色中可能会有飞地，即两个不连通的区域属于同一个国家（例如美国的阿拉斯加州），而地图着色时仍需要这两个区域涂上同样颜色。即使很多情况下，有些地图可以用四色着色，但是实际成图中依然用多种颜色（大于等于5种）[5]。我认为还有个原因是四种颜色来着色上千个多边形，四种颜色交错、不够美观。5年前我看到有学者基于强化学习来计算平面点集的凸包时，曾想过基于强化学习求解地图着色问题，这或许可行？

关于四色定理算法的综述、算法和应用的文献资源比较多，我推荐两个参考资源。作为一个GISer，Marco关于图着色研究的算法进展[6]和Joe介绍的多种着色算法[7]（比如经典的DSATUR算法等）值得一看。 后记：大约十几年前，我曾在北京超图软件股份有限公司(SuperMap)的研究院（之前称为研发中心）完成四色算法的编码实现，针对全国2800多个县市级数据，当时的着色算法能在秒内时间完成5着色，4着色大概需要十几秒？SuperMap iDesktop新版本中的地图着色算法，想必已经被同事们提升了更高的计算效率。

合集下载

四色定理的数学证明

四色定理的数学证明

Pure Mathematics 理论数学, 2019, 9(3), 410-413

Published Online May 2019 in Hans. /journal/pm https:///10.12677/pm.2019.93054

文章引用: 邹山中. 四色定理的数学证明[J]. 理论数学, 2019, 9(3): 410-413.

DOI: 10.12677/pm.2019.93054

Mathematical Proof of Four-Color Theorem

Shanzhong Zou

Guangzhou Guangdong

Received: Apr. 26th, 2019; accepted: May 6th, 2019; published: May 22nd, 2019

Abstract The closed space is defined as an area, and then the background color of the map is defined. The section connecting more than three boundaries is regarded as the intersection point, and the line segment connecting two regions is defined as the boundary. After reducing or expanding the in-tersection points of the map, the complex area map with boundary and intersection points is sim-plified to a map with only boundary. The results show that four kinds of color can be used to dis-tinguish different areas in the map.

基于四色原理技术的伪四色算法研究

基于四色原理技术的伪四色算法研究

龙源期刊网

基于四色原理技术的伪四色算法研究

作者：郭林庚

来源：《数字技术与应用》2017年第03期

摘要：利用开放的电子地图手工绘制的非规范性地图信息，本文旨在针对这些错综复杂的不规范地理信息，提出一种伪四色原理算法，自动分析多边形相邻性，使用尽可能少的颜色进行地图着色，开发者无须了解地理信息系统原理，即可快速掌握，快速开发，节约公司成本。

关键词：数据可视化；四色原理；最小外接矩形；空间位置分析

中图分类号：P208 文献标识码：A 文章编号：1007-9416（2017）03-0159-02

1 前言

电信经营数据可视化系统使用百度地图，手工绘制各管辖区域，地图手工着色变得不可行。四色原理[1]，“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”将四色算法应用到系统中，进行自动着色，能解决手工无法着色的问题，提升系统展示感知。但不规范的多边形覆盖物空间位置相邻性分析是四色算法应用的难点。本文阐述了一些简单易懂图形基本处理算法和过程，面对错综复杂的非规范性地图信息，提出着色的伪四色算法，使得没有地理信息相关专业知识的内部开发人员能快速掌握，迅速开发，减少开发投资成本。

2 空间位置相邻性分析

2.1 射线法判断多边形覆盖物相邻（算法1）

分析实际绘图情况，一线人员绘制的多边形都出现相交的情况，因此可采用判断多边形上的每个点是否有在另一个多边形内，来判断两多边形是否相邻。几何上判断某个点是否在多边形内，可以采用射线法[2]进行计算。射线法原理：从目标点出发引一条射线，看这条射线和多边形的多有边的交点数目，如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。本算法内容涉及到地理信息信息的基础算法及图形学的内容，非本文介绍的重点，只做算法比较参考。

地图染色-四色定理

地图染色-四色定理

地图染⾊-四⾊定理

四⾊定理指出每个可以画出来的地图都可以⾄多⽤4种颜⾊来上⾊，⽽且没有两个相接的区域会是相同的颜⾊。被称为相接的两个区域是指

他们共有⼀段边界，⽽不是⼀个点。

主要原理：从第⼀个区域开始染⾊，到每⼀个区域依次遍历相邻的区域，若未出现重⾊则将该⾊⼊栈，遍历下⼀个区域。若出现重⾊，进⾏

换⾊直⾄四种颜⾊都出现重复，就回溯到上⼀个区域，更换颜⾊。

#include

using namespace std;

#define NUM 100

//⽤图存储

typedef struct graph

{

int edges[NUM][NUM];

int v[NUM];

int vnum, edgenum;

} Graph;

//⾸先⽤邻接矩阵作图 v[i][j]=1表⽰俩个国家相邻,v[i][j]=0表⽰不相邻

void Coloring(Graph G)

{

int area = 1; //代表当前染⾊数量 给第⼀个点染⾊ 颜⾊为1 国家序号为0——NUM-1

int nowcolor = 1; //当前颜⾊最⼤为4

//第⼀个地⽅染⾊为1 如果当前区域染⾊不冲突则上⾊后将顶点⼊栈，否则出栈进⾏再次染⾊

G.v[0] = 1;

while (area < G.vnum)

{

while (nowcolor <= 4 && area < G.vnum)

{

int k = 1;

//判断是否重⾊

while (k < area && G.edges[area][k] * G.v[k] != nowcolor)

{

k++;

}

if (k == area)

{

//说明没有重复则

G.v[area] = nowcolor;

area++;

nowcolor = 1;

}

else

{

nowcolor++;

}

}

//回溯到上⼀个位置 换⼀个颜⾊继续染

if (nowcolor > 4)

{

area--;

nowcolor = G.v[area] + 1;

用假设推理法证明“四色定理”

用假设推理法证明“四色定理”

用假设推理法证明“四色定理”

在我2010年初自学网站制作的过程中，无意认识的这个久违的问题，我马上花了3个小时思考与想象出适合的模型并证明，再花了2小时把这篇文章写完，最后又花了2个小时对本文进行简化修正。证明的思想是从更简单的数学逻辑模型进化而来，当逻辑模型出现无法表达时，就采用了更适合模型来表达思想，同时也确定了用边界线对这个猜想进行说明。我从一开始并没有采用编程的思维进行证明，只是在反复使用“返回假设”时，才发现这有点像编程语句了。

标签：四色猜想、国家、边界线、涂色

四色猜想：“任何一张地图只用四种颜色就能使具有共同边界的国家涂上不同的颜色。”

证明过程：

首先分析四色猜想的隐藏条件或对涂色过程设定：

1.采用顺序涂色的方法，即先选定一个国家进行涂色，再选定第二个国家进行涂色，依此类推。（为涂色过程设定1）

2.对第三个以后的国家进行涂色的时候，首先采用不接壤的国家的相同涂色。（例如假设4，为涂色过程设定2）

3.国界线为两个国家产生的唯一线段（可以是直线段也可以是曲线段）。地图上没有空中界線，也没有地下界线，因此已有的国界线不能再被穿越。（例如假设5，为隐藏条件1）

4.对国家和颜色进行编号，实行先入为主策略，后续的国家编号或者涂色的编号跟进先涂颜色的国家编号或者颜色（为涂色过程设定，见设定2与假设1）。

建立数学模型：

证明转化：假设需要5种颜色才可以把无限的国家画在一个地图中，五种颜色分别为A.B.C.D.E. 先用A颜色画，再用B颜色画，再用C颜色画，再用D颜色画，再用E颜色画chX3d2UKpUfzEWDOAEXCvQ==。只需证明与在A.B.C.D四个相互接壤国家的情况下，第五个国家的涂色肯定可以用其中一个国家的涂色来代替。即为只需证明相互都有接壤的国家数量最多为4个，就可保证任何一张地图只需四种颜色就能使具有共同边界的国家涂上不同的颜色。

运用假设推理法，提出以下8点假设：