`
xmong
  • 浏览: 264117 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

图着色问题

阅读更多
图着色问题



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



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



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



可以用一下邻接矩阵来表示
 {{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个子集。然后我们对每个子集内的顶点涂一种颜色。
• 同色顶点对应的课程安排在同一场次考试,颜色数即为学期考试所需要的最少场次数。





  • 大小: 75.5 KB
  • 大小: 11.5 KB
分享到:
评论

相关推荐

    地图着色问题 图论 四着色

    这个问题在数学上被转化为图的着色问题,其中地图的每个区域被视为图中的一个节点(或顶点),相邻的区域则用边相连。四色定理是地图着色问题的一个重要结论,它断言任何平面图都可以用不超过四种颜色进行着色,确保...

    图着色问题 贪心法-C语言

    图着色问题是一种经典的计算机科学问题,它源于数学和图论领域,被广泛应用于网络规划、资源分配等实际场景。在图着色问题中,我们需要为一张图的各个顶点分配颜色,使得相邻的顶点颜色不同。这个问题的解决方法之一...

    算法(c++)——地图着色问题.rar

    C++中实现地图着色问题,我们可以使用邻接矩阵或邻接表来表示图。邻接矩阵是一个二维数组,用于存储图中节点之间的连接信息;而邻接表则是通过链表或者向量来表示节点的邻居,更节省空间。 1. **邻接矩阵**:对于每...

    GCP(图着色问题)_GCP模拟退火_gcp_图着色问题_SA_

    图着色问题(Graph Coloring Problem, GCP)是图论中的一个重要问题,它涉及到如何给图的各个顶点分配颜色,使得相邻的顶点颜色不同。这个问题在实际中有着广泛的应用,例如在电视频道调度、资源分配、网络设计等...

    数据结构综合课设地图着色问题.docx

    【数据结构综合课设——地图着色问题】 地图着色问题是一个典型的图论问题,它在现实生活中有广泛的应用,例如资源分配、时间表规划等。在这个课设中,我们被要求设计一个软件来解决江西地图中11个地级市的着色问题...

    连通图着色问题 程序以及报告

    连通图着色问题是图论中的一个重要议题,它在计算机科学和算法设计中具有广泛的应用。这个题目主要涉及两个核心概念:连通图和图着色。在此,我们将深入探讨这两个概念,以及如何通过编程来解决这个问题。 首先,...

    图着色问题 回溯法-C语言

    图着色问题是一种经典的计算机科学问题,它在解决复杂优化问题和逻辑推理中扮演着重要角色。在图论中,图着色问题是指给定一个图,为图中的每个节点分配颜色,使得相邻节点之间颜色不同。这个问题在现实生活中有很多...

    C++ 算法设计与分析 地图着色问题(中国+美国)

    图着色问题(Graph Coloring Problem, GCP) 又称着色问题,是最著名的NP-完全问题之一。 这里展示可以选择中国地图和美国地图进行染色,同时可选择4-7种颜色进行染色。 采用了队列方法解决问题。

    GCP.rar_graph coloring_图着色 模拟退火 MATLAB_图着色算法_图着色问题_着色算法

    图着色问题(Graph Coloring Problem, GCP)是图论中的一个重要概念,它涉及到将图的顶点分配颜色,使得相邻的顶点不具有相同的颜色。这个问题在实际中有着广泛的应用,例如在电视频道调度、资源分配、网络路由等...

    tulun.rar_图着色_图着色 matlab_图着色 matlab_图着色问题_着色问题

    图着色问题是一个经典的计算机科学和图论问题,它在许多领域都有应用,包括调度、资源分配和网络设计。在图着色问题中,我们通常要将一张图的顶点用有限种颜色进行着色,使得相邻的顶点不能使用相同的颜色。这个问题...

    回溯法解决图着色问题

    这是用C++语言写的一个关于图着色的问题。对于初学算法的人有帮助。

    经典图着色java源码实现

    在计算机科学领域,图着色问题是一个典型的图论问题,它涉及到如何用有限数量的颜色给图中的各个顶点着色,使得相邻的顶点颜色各不相同。在经典的图着色问题中,我们通常考虑最小颜色数,即寻找最少数量的颜色来完成...

    连通图着色问题——韦尔奇鲍威尔算法

    连通图着色问题——韦尔奇鲍威尔算法 连通图着色问题是离散数学中一个重要的研究方向,韦尔奇鲍威尔算法是一种常用的解决方法。下面我们将详细介绍连通图着色问题的定义、韦尔奇鲍威尔算法的原理和实现细节,以及在...

    数据结构课设-地图着色问题-java(源代码)

    1、设计数据结构,表示各省与各省间邻接关系 2、设计染色算法 3、根据染色算法的运行结果对地图进行染色,将染色过程制作视频,最终 染色结果呈现写在报告了,鼓励用计算机实现染色过程,也可以手工根 据染色方案...

    基于Matlab实现的蚁群算法结合RLF求解图着色问题源码+程序说明+超详细注释(课程作业).zip

    基于Matlab实现的蚁群算法结合RLF求解图着色问题源码+程序说明+超详细注释(课程作业).zip基于Matlab实现的蚁群算法结合RLF求解图着色问题源码+程序说明+超详细注释(课程作业).zip基于Matlab实现的蚁群算法结合RLF...

    数据结构地图着色问题

    (1) 数据结构的设计:地图可以采用图的数据结构,每个省为一个节点,边表示对应的两个省相邻。 (2) 算法设计:设计着色算法,保证邻接点不是同一种颜色。 (3) 地图数据的输入采取从文件中读取。 (4) 结果...

    地图着色贪心算法代码

    地图着色问题是一个经典的图论问题,它涉及到如何给地图上的不同区域分配颜色,使得任意两个相邻的区域颜色不同。通常情况下,地图着色问题的目标是最小化所需的最少颜色数量。在实际应用中,地图着色问题不仅限于...

    回溯法解决图着色(PPT+代码(C++))

    本资源提供了利用回溯法解决图着色问题的详细讲解和实现,包括PPT演示文稿和C++源代码。 在图着色问题中,我们需要给一个图的各个节点分配颜色,使得相邻节点之间颜色不同,目标是找到最少的颜色数。这个问题在实际...

Global site tag (gtag.js) - Google Analytics