实现四色定理的C++程序

给出一个图的m-着色的程序段,回溯法:

/* 图的邻接矩阵Graph[n,n]表示无向连通图梁铅握G,

1,2,3,..m代表不同的颜色

顶点i所着色用x[i]表示,初始值都赋为0

*/

void NextValue(int k)

{

int j, flag

do{

x[k] = (x[k]+1) % (m + 1)//分配给x[k]一种新的颜色

if (x[k] == 0)

return//x[k]的颜色已用完

flag = 1//x[k]是否可用的标记

for (j = 0 j < n j++)

if (Graph[k,j] == 1 && x[k] == x[j]){

flag = 0//x[k]不可用

break

}

while (flag)

}

void MColoring(int k)

{

while (x[k] < m){ //产生x[k]的合理分配

NextValue(k)//找x[k]的一个合理分配

if (x[k] == 0)

return //无解,结束调用

if (k == n) { //着完n个顶点,找橡庆到完整着色法,输出

Output(x,k) //输出当前解

else

MColoring(k+1)

}

}

/*

递归算法：

void Coloring(区域 n)

1. 令颜色集ClrSet={ 没有被区域n的邻居区域使用的颜色 }.

2. 如果ClrSet是空集，返回.

3. 对ClrSet中的激亩每种颜色c，作循环：

3.1 为区域n着色c。

3.2 如果所有区域都已着色(n是最后一个区域)，那么显示/保存着色结果.

3.3 否则对下一个尚未着色的区域(n+1)，调用Coloring(n+1).

4. 把区域n变为没有着色的区域.

--------------------------------------------------------

*/

template<int node_count = 8>

class CColoring

{

private:

typedef int node_type

typedef int color_type

typedef std::set<node_type>node_set

typedef std::vector<color_type>color_array

public:

void operator()(const int _Matrix[node_count][node_count])

{

matrix = _Matrix

colors_of_nodes.resize(node_count, 0)

total_count = 0

coloring(0)

}

private:

void coloring(node_type n)

{

// 颜色的使用情况

std::vector<bool>used_colors

node_type m

color_type c

// 初始化颜色的使用情况

used_colors.resize(color_count, false)

// 遍历每个与区域n相邻的区域m

for(m = 0m <node_count++m)

{

if(matrix[n][m])

{

// 获取m的颜色

c = colors_of_nodes[m]

// m已着色

if(c != 0)

used_colors[c] = true

}

}

// 遍历每个未被n的邻居使用的颜色c

for(c = 1c <color_count++c)

{

if(!used_colors[c])

{

// 为n着色c

colors_of_nodes[n] = c

// 着色完毕

if(n >= node_count - 1)

{

++total_count

// 输出结果

_tprintf(_T("---------------------\n"))

_tprintf(_T("Method %d:\n"), total_count)

for(m = 0m <node_count++m)

{

_tprintf(_T("node: %d, color: %d\n"), m, colors_of_nodes[m])

}

}

// 还有区域没有着色

else

{

// 为下一个未着色的区域，调用coloring()

coloring(n + 1)

}

}

}

// 将n设置为没有着色的区域

colors_of_nodes[n] = 0

}

// 0表示无色，1-4表示4种不同颜色

static const int color_count = 5

// 邻接矩阵

const int (* matrix)[node_count]

// 各区域对应的颜色

color_array colors_of_nodes

// 总的着色方案数

int total_count

}

void main()

{

int Matrix[4][4] =

{

{ 0, 1, 0, 0 },

{ 1, 0, 0, 0 },

{ 0, 0, 0, 1 },

{ 0, 0, 1, 0 },

}

CColoring<4>coloring

coloring(Matrix)

}

四色定理（世界近代三大数学难题之一），又称四色猜想、四色问题，是世界三大数学猜想之一。四色定理的本质正是二维平面的固有属性，即平面内不可出现交叉而没有公共点的两条直线。

很多人证明了二维平面内无法构造五个或五个以上两两相连区域，但却没有将其上升到逻辑关系和二维固有属性的层面，以致出现了很多伪反例。

不过这些恰恰是对图肆册论严密性的考证和发展推动。计算机证明虽然做了百亿次判断，终究只是在庞大的数量优势上取得成功，这并不符合数学严密的逻辑体系，至今仍有无数数学爱好者投身其中研究。

扩展资料

四色定理证明的关键可以归纳为二维平面内两条直线相交的问题。

1、将地图上不同的区域用不同的点来表示。

2、点与点之间的连线用来表示地图上两区域之间的相邻逻辑关系，所以,线与线昌雹空之间不可交叉耐瞎（即不可存在交叉而没有公共交点的情况），否则就超越了二维平面，而这种平面暂时称它为逻辑平面，它只反应区域之间的关系，并不反应实际位置。

通过以上的变换处理，可以将对无穷尽的实际位置的讨论，变为有条理可归纳的逻辑关系的讨论，从而提供了简单书面证明的可行性。

参考资料来源：百度百科-四色定理

---