首页 > 代码库 > 地图染色问题
地图染色问题
四色定理是一个著名的数学定理：如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样[2][3]；另一个通俗的说法是：每个（无飞地的）地图都可以用不多于四种颜色来染色，而且不会有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界，而不仅仅是一个公共的交点。例如右图左下角的圆形中，红色部分和绿色部分是邻接的区域，而黄色部分和红色部分则不是邻接区域。
“是否只用四种颜色就能为所有地图染色”的问题最早是由一位英国制图员在1852年提出的，被称为“四色问题”或“四色猜想”。人们发现，要证明宽松一点的“五色定理”（即“只用五种颜色就能为所有地图染色”）很容易，但四色问题却出人意料地异常困难。曾经有许多人发表四色问题的证明或反例，但都被证实是错误的。
1976年，数学家凯尼斯·阿佩尔和沃夫冈·哈肯借助电子计算机首次得到一个完全的证明，四色问题也终于成为四色定理。这是首个主要借助计算机证明的定理。这个证明一开始并不为许多数学家接受，因为不少人认为这个证明无法用人手直接验证。尽管随着计算机的普及，数学界对计算机辅助证明更能接受，但仍有数学家希望能够找到更简洁或不借助计算机的证明。
程序代码：
#include <stdio.h>#define N 6 /* N表示区域个数 */int s[N]; /* 栈s[i]来表示地图的区域的颜色序号 */void MapColor( int dist[N][N], int s[N] ){ int color, area, k, i; /* color代表颜色，area 表示当前要染色的是第几个区域，k表示已经染色区域的颜色 */ s[0] = 1; /* 第一个区域先着色为颜色1 */ area = 1; /* 从第二区域开始试探染色 */ color = 1; /* 从第一种颜色开始试探 */ while ( area < N ) /* 是否全部染色完毕 */ { while ( color <= 4 ) { k = 0; /* 对每一个区域，都从第一个区域的颜色开始比较。 */ while ( (k < area) && (s[k] * dist[area][k] != color) ) /* 判断是否重色 *//* 这个循环判定条件是整个算法的关键，理解了这个，整个算法就很easy了，所以小梦就啰嗦几句吧。 dist[area][k]表示当前即将染色区域和已经染色的第K个区域是否相邻。s[k]*dist[area][k] 若K区域和area区域相邻，则其表示当前第K个区域的颜色，若不相邻，则其值为0，则肯定不会重色，就可以将color复制给当前区域area的颜色s[k].解释的有些费劲，大家可以直接复制代码，运行一下，在对着图上的颜色跟着代码走几步就会理解了。 */ k++; if ( k < area ) color++; /* area 区域与K区域重色 */ else{ s[area] = color; /* 保存area区域的颜色 */ area++; /* 准备颜色下一个区域 */ if ( area >= N ) break; color = 1; /* 每次都从第一个颜色开始试探 */ } } if ( color > 4 ) /* area没有找到合适的颜色，需要进行回溯 */ { area = area - 1; /* 回溯并修改area-1域并用颜色 */ color = s[area] + 1; 将 预 备 要染色的颜色换 为 当前 栈 顶 区 域的 一 个 颜色 } } printf( “ 地 图 区 域 标 号 为 1 ~6的染色情况 为 ： \ n ” ); for ( i = 0; i < N; i++ ) { printf( “ NO.% d: ”, i + 1 ); switch ( s[i] ) { case 0: printf( “ WRONG MAP !\ n ” ); break; case 1: printf( “ RED \ n ” ); break; case 2: printf( “ BLUE \ n ” ); break; case 3: printf( “ GREEN \ n ” ); break; case 4: printf( “ YELLOW \ n ” ); break; default: printf( “ 什么的什么啊 ！ 1 ″ ); break; } }}int main(){ int dist[N][N] = { { 0, 1, 1, 1, 1, 1 }, /* 地图的邻接矩阵 */ { 1, 0, 1, 1, 0, 0 }, { 1, 1, 0, 1, 1, 1 }, { 1, 0, 1, 0, 0, 1 }, { 1, 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0 },}; int s[N] = { 0 }; MapColor( dist, s ); return(0);}
地图染色问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。