地图染色算法

⑴ c# 给中国黑白地图进行染色，给个思路好吗

你的问题可否抽象成类似Windows画图里的对封闭区域填充颜色？

⑵ 为什么地图只需四色即可染完

地图只使用四种颜色，是因为四色定理的存在。

四色定理是一个着名的数学定理，通俗的说法是：每个平面地图都可以只用四种颜色来染色，而且没有两个邻接的区域颜色相同。四色定理的本质就是在平面或者球面无法构造五个或者五个以上两两相连的区域。这一定理最初是由Francis Guthrie在1853年提出的猜想。1976年借助电子计算机证明了四色问题，问题也终于成为定理，这是第一个借助计算机证明的定理。

⑶ 图着色问题的路线着色问题

道路着色问题（Road Coloring Problem）是图论中最着名的猜想之一。通俗的说，这个猜想认为，可以绘制一张“万能地图”，指导人们到达某一目的地，不管他们原来在什么位置。这个猜想最近被以色列数学家艾夫拉汉· 特雷特曼(Avraham Trahtman)在2007年9月证明。
举个例子。在维基网给出的图例中，如果按图中所示方式将16条边着色，那么不管你从哪里出发，按照“蓝红红蓝红红蓝红红”的路线走9步，你最后一定达到黄色顶点。路线着色定理就是说在满足一定条件的有向图中，这样的着色方式一定存在。严格的数学描述如下。我们首先来定义同步着色。G是一个有限有向图并且G的每个顶点的出度都是k。G的一个同步着色满足以下两个条件：1)G的每个顶点有且只有一条出边被染成了1到k之间的某种颜色；2)G的每个顶点都对应一种走法，不管你从哪里出发，按该走法走，最后都结束在该顶点。有向图G存在同步着色的必要条件是G是强连通而且是非周期的。一个有向图是非周期的是指该图中包含的所有环的长度没有大于1的公约数。路线着色定理这两个条件(强连通和是非周期)也是充分的。也就是说,有向图G存在同步着色当且仅当G是强连通而且是非周期的。
特雷特曼在数学上的这一成果极为令人瞩目，英国《独立报》为此事专门发表了一篇题为“身无分文的移民成了数学超级明星”的文章，给予了高度的评价。
以色列人也为特雷特曼取得的成就感到无比的骄傲。特拉维夫电视台中断了正常的节目播放，以第一时间发布了这一重大消息，连中东其他国家的主流媒体也作了大篇幅的相关报道。
得知特雷特曼解决这一难题的消息后，多年从事路线着色问题研究的加拿大数学家乔尔·弗里德曼说，“路线着色问题的解决令数学共同体非常兴奋。”读过特雷特曼论文的中国数学家和语言学家周海中教授认为，特雷特曼的数学知识非常渊博，解题方法十分巧妙，这一谜题得到破解，无疑是数学史上的一个华彩乐章。 算法描述：color[n]存储n个顶点的着色方案，可以选择的颜色为1到m。
当t=1时，对当前第t个顶点开始着色：若t>n，则已求得一个解，输出着色方案即可。否则，依次对顶点t着色1-m， 若t与所有其它相邻顶点无颜色冲突，则继续为下一顶点着色；否则，回溯，测试下一颜色。 #include<stdio.h>intcolor[100];boolok(intk,intc[][100])//判断顶点k的着色是否发生冲突{inti,j;for(i=1;i<k;i++){if(c[k][i]==1&&color[i]==color[k])returnfalse;}returntrue;}voidgraphcolor(intn,intm,intc[][100]){inti,k;for(i=1;i<=n;i++)color[i]=0;k=1;while(k>=1){color[k]=color[k]+1;while(color[k]<=m)if(ok(k,c))break;elsecolor[k]=color[k]+1;//搜索下一个颜色if(color[k]<=m&&k==n){for(i=1;i<=n;i++)printf(%d,color[i]);printf( );}elseif(color[k]<=m&&k<n)k=k+1;//处理下一个顶点else{color[k]=0;k=k-1;//回溯}}}voidmain(){inti,j,n,m;intc[100][100];//存储n个顶点的无向图的数组printf(输入顶点数n和着色数m: );scanf(%d%d,&n,&m);printf(输入无向图的邻接矩阵: );for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf(%d,&c[i][j]);printf(着色所有可能的解: );graphcolor(n,m,c);} 利用相交图（interference graph）来表示程序变量的生命期是否相交，将寄存器分配给变量的问题，可以近似地看成是给相交图着色：相交图中，相交的节点不能着同一颜色；每一种颜色对应一个寄存器。Chaitin等人最早提出了基于图着色的寄存器分配方法其着色思路采用了Kempe的着色方法，即，任意一个邻居节点数目少于k的节点，都能够被k着色。判断一个图是否能够被k(k>=3)种颜色着色，即k着色问题，被Karp证明是一个NP-complete问题。
但是，寄存器分配不仅仅是图着色的问题。当寄存器数目不足以分配某些变量时，就必须将这些变量溢出到内存中，该过程成为spill。最小化溢出代价的问题，也是一个NP-complete问题。如果简化该问题——假设所有溢出代价相等，那么最小化溢出代价的问题，等价于k着色问题，仍然是NP-complete问题。
此外，如果两个变量的生命期仅仅因为出现在同一个拷贝指令中而相邻，那么，通过将这两个变量分配到同一个寄存器，就可以消除该拷贝指令，成为coalescing。这个方向的努力在Chaitin的文章以后的1/4个世纪，成为推动寄存器分配的主要动力之一，涌现出了包括aggressive coalescing,conservative coalescing和optimistic coalescing。但是，将两个变量分配到同一个寄存器，等价于将这两个变量合并成同一个变量，生命期合并，因而会加剧相交图的聚簇现象，降低相交图的可着色性。Bouchez等人证明了目前的coalescing问题都是NP-complete的。
为了降低相交图的聚簇现象，提高相交图的可着色性，可以通过将变量拷贝给一个临时变量，并将以后对该变量的使用替换成对该临时变量的使用，从而将一个变量的生命期分解成两个变量的生命期，称为live range splitting。显然，这是一个与coalescing的作用相反的过程。Bouchez等人考虑了该方法的复杂度。
此外，寄存器分配还需要考虑寄存器别名(aliasing)和预着色(pre-coloring)的问题。寄存器别名是指，在某些体系结构中，一个寄存器的赋值可能会影响到另外一个寄存器。比如，在x86中，对AX寄存器的赋值，会影响AL和AH寄存器。预着色是指，某些变量必须被分配到特定的寄存器。比如，许多体系结构会采用特定寄存器来传递函数参数。
George和Appel发展了Chaitin的算法，更好地考虑了coalescing过程和赋值过程，以及各过程之间的迭代，在基于图着色的寄存器分配方法中具有广泛的影响。

⑷ C++给中国地图着色，用四种颜色时如何采用不同的方案怎样计算地图着色效率

这是图的遍历，可以先把各省抽象为N个结点，制作为无向图数据结构，采用广度遍历，考虑从最边缘的省份起着色。使用递归算法。
你学过数据结构吗？不学过也不好说。

⑸ 求证 每幅地图都可以用四种颜色着色

这就是着名的四色猜想，现在已经被证明，改称为四色定理：

四色定理指出每个可以画出来的地图都可以至多用4种颜色来上色，而且没有两个相接的区域会是相同的颜色。被称为相接的两个区域是指他们共有一段边界，而不是一个点。

这一定理最初是由Francis Guthrie在1853年提出的猜想。很明显，3种颜色不会满足条件，而且也不难证明5种颜色满足条件且绰绰有余。但是，直到1977年四色猜想才最终由Kenneth Appel 和Wolfgang Haken证明。他们得到了J. Koch在算法工作上的支持。

证明方法将地图上的无限种可能情况减少为1,936种状态（稍后减少为1,476种），这些状态由计算机一个挨一个的进行检查。这一工作由不同的程序和计算机独立的进行了复检。在1996年，Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas使用了一种类似的证明方法，检查了633种特殊的情况。这一新证明也使用了计算机，如果由人工来检查的话是不切实际的。

⑹ 地图着色算法，该算法中，要能证明四色定理，而不是运用

起码需要10种颜色。

⑺ c# 地图四染色

很麻烦的算法题，分有点少........

啧，分还是少........算了，给你写个简单的把

using System;
using System.Collections.Generic;

namespace 四色猜想
{
public class FourColor
{
public static void Run(int aeraNumeric)
{
//为了偷懒，没有使用二维矩阵而是直接用了栈，即X的最大相邻数为2即X-1和X+1，实际上2个颜色就够用了....
//实例化栈
Stack<Aera> AeraStack = new Stack<Aera>(aeraNumeric);
//演示算法，使用随机颜色
Random RandomColor = new System.Random();

for (int i = 0; i < aeraNumeric; i++)
{
//初始化Aera并入栈
Aera MyAera = new Aera((i + 1).ToString(), (Publicenum.FourColor)(RandomColor.Next(4)));
//入栈
if (AeraStack.Count == 0)
{
AeraStack.Push(MyAera);
continue;
}
Aera TestAera = AeraStack.Peek();
if (TestAera.AeraColor == MyAera.AeraColor)
{
int j = 0;
while (j < 5)
{
if (j == 4)
{
throw new InvalidOperationException("超出4色范围!");
}
Publicenum.FourColor TestColor = (Publicenum.FourColor)j;
if (TestAera.AeraColor == TestColor)
{
j++;
continue;
}
else
{
MyAera.AeraColor = TestColor;
break;
}

}
}
AeraStack.Push(MyAera);
}

//输出结果
while (AeraStack.Count != 0)
{
Aera OutputAera = AeraStack.Pop();
Console.WriteLine("Name:{0},Color:{1}", OutputAera.AeraName, OutputAera.AeraColor);
}
Console.ReadLine();
}
}

public class Aera
{
public string AeraName { get; set; }
public Publicenum.FourColor AeraColor { get; set; }

public Aera(string aeraName, Publicenum.FourColor aeraColor)
{
AeraName = aeraName;
AeraColor = aeraColor;
}
}

public class Publicenum
{
public enum FourColor
{
A, B, C, D
}
}
}

控制台程序，调用时输入区域个数如 FourColor.Run(73);

⑻ 急！利用5种不同的算法，为中国地图每个省着色，要求相邻的省份颜色不同，所用的颜色最少！！

这是根据数学史上着名的四色问题，每幅地图都可以用四种颜色着色，使得有共同代表地形的不同！ 颜色不代表什么，主要是为了区分方便，如果用同一种