图着色问题

图着色问题


目录
1 图着色问题 1
1.1 问题背景 1
1.2 问题解析 1
1.3 问题解决 2
1.4 着色应用 5



1 图着色问题
1.1 问题背景
图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。
问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。

[img]http://dl.iteye.com/upload/attachment/0077/1195/b7691e5c-6d4e-3a64-b209-03f380a191f9.png[/img]

1.2 问题解析
可以给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。如果有则称这个图是m可着色，否则称这个图不是m可着色。若一个图最少需要k种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数k为该图的色数。如下图：

[img]http://dl.iteye.com/upload/attachment/0077/1197/adaa6a42-9fdf-36e5-97f1-7e5fb9f98ff8.png[/img]

可以用一下邻接矩阵来表示

 {{1,1,1,1,0,0},
   {1,1,1,1,1,0},
   {1,1,1,1,0,0},
   {1,1,1,1,1,0},
   {0,1,0,1,1,1},
   {0,0,0,0,1,1}};

邻接矩阵中通常用二维数组来存放边之间的关系，用一维数组来存放顶点的信息。所以在接下来的求解问题中我们将用到二维数组a来存放两边是否相邻，用一维数组x来存放每个顶点的颜色;x[i]=j表示第i个节点图第j中颜色。

根据矩阵我们要求出矩阵的色数K和着色方案？

1.3 问题解决
我们可以用贪心法给图着色，选择第一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果第一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，增加第二种颜色，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此类推。
代码实现：

package com.tuzhese;

public class TestTuzhese {

	int n = 0;

	/**
	 * 着色方法
	 */
	public void color(){

		/**
		 * 关系图矩阵，1代表连接关系，0代表无连接关系。
		 */
		int[][] x = new int[][]{
				{1,1,1,1,0,0},
				{1,1,1,1,1,0},
				{1,1,1,1,0,0},
				{1,1,1,1,1,0},
				{0,1,0,1,1,1},
				{0,0,0,0,1,1}}; 

		/**
		 * 着图颜色，初始颜色为0代表第一种颜色，1代表第二种颜色，以此类推。
		 */
		int c = 0;
		/**
		 * 存储着色方案
		 */
		int[] k = new int[x.length];
		/**
		 * 为每个顶点着色
		 */
		setColor(x, 0, c, k);

	}

	/**
	 * 
	 * 为第i个顶点x着色，
	 * 当x着色成功后递归向下一个顶点着色，直到所以顶点都着色完成。
	 * 将每一种着色方案存储并打印
	 * 
	 * @param x 着色矩阵
	 * @param i 第几个着色顶点
	 * @param c 当前最大颜色值
	 * @param k 颜色存储方案
	 */
	public void setColor(int[][] x, int i, int c, int[] k){

		boolean fc = false;//当前已有颜色值是否够用

		if(i<x.length){
			/**
			 * 用现有的所有颜色依次为第i个顶点着色，判断是否存在着色冲突。
			 */
			for (int t = 0; t <= c; t++) {
				/**
				 * 颜色t不存在冲突着可以给该顶点着色，继续为下一个顶点着色。
				 */
				if(checkColor(x, i, t, k)){
					fc = true;
					k[i] = t;
					setColor(x, i+1, c, k);
				}
			}
			/**
			 * 如果现有的颜色值都发生冲突，不可着色。
			 * 现有颜色c自增，添加一种新颜色值，并用该颜色值为第i个顶点着色，继续为下一顶点着色
			 */
			if(!fc){
				c++;
				k[i] = c;
				i++;
				setColor(x, i, c, k);
			}

		}else{
			/**
			 * 输出着色方案
			 */
			n++;
			System.out.println("着色方案"+n+":");
			for (int j = 0; j < k.length; j++) {
				System.out.print(k[j]+",");
			}
			System.out.println();
		}


	}

	/**
	 * 
	 * 判断现有的颜色是否可以着色，即是否存在着色冲突。
	 * 用颜色t给第i个顶点着色，判断该色值是否存在着色冲突，
	 * 如果存在冲突返回false，即该颜色不可以为该顶点着色。
	 * 如果没有发生冲突则放回true,即该颜色可以为该顶点着色。
	 * 
	 * @param x 着色顶点
	 * @param i 第i个着色顶点
	 * @param t 着色值
	 * @param k 着色方案
	 * @return
	 */
	public boolean checkColor(int[][] x, int i, int t, int[] k){
		for (int j = 0; j < i; j++) {
			/**
			 * 着色冲突的判断条件，
			 * 与该顶点连接的其他顶点的颜色值是否与该着色值t冲突
			 */
			if(x[i][j] == 1 && k[j] == t){
				return false;
			}
		}
		return true;
	}



	public static void main(String[] args) {
		TestTuzhese  tt = new TestTuzhese();
		tt.color();
	}

}

输出结果：

着色方案1:
0,1,2,3,0,1,
着色方案2:
0,1,2,3,0,2,
着色方案3:
0,1,2,3,0,3,
着色方案4:
0,1,2,3,2,0,
着色方案5:
0,1,2,3,2,1,
着色方案6:
0,1,2,3,2,3,

1.4 着色应用

1，学校共有n门功课需要进行期末考试，因为不少学生不止选修一门课，所以不能把一个同学选修的两门课安排在同一场次进行考试。问学期的期末考试最少需要多少场次才能完成？
• 问题处理：我们以每门功课为一个顶点，当且仅当两门功课被同一个学生选修时，在响应两个顶点之间连一条边，得到一个图G。我们将n门功课划分成k个子集U1,U2,…,UK两两子集的功课都不相同。
• 每个子集Ui（1≤i≤k）的顶点两两子集不相邻，即子集内的任意两门功课都不能被一个学生选修。能这种要求划分的子集数K必须最少，即不能划分成k-1个子集。然后我们对每个子集内的顶点涂一种颜色。
• 同色顶点对应的课程安排在同一场次考试，颜色数即为学期考试所需要的最少场次数。