我需要一种算法来获得图的色数 [英] I need an algorithm to get the chromatic number of a graph
问题描述
鉴于图的邻接矩阵，我需要获取色数(最小绘制图形的每个节点所需的颜色数，以便相邻节点获得不同的颜色.
Given the adjacency matrix of a graph, I need to obtain the chromatic number (minimum number of colours needed to paint every node of a graph so that adjacent nodes get different colours).
最好应该是Java算法，并且我不在乎性能.
Preferably it should be a java algorithm, and I don't care about performance.
谢谢.
最近推出了一个修复程序，因此答案更加准确.现在它将重新检查他的位置和以前的位置.
recently introduced a fix so the answer is more accurately. now it will recheck his position with his previous positions.
public class Modelacion {
public static void main(String args[]) throws IOException{
// given the matrix ... which i have hidden the initialization here
int[][] matriz = new int[40][40];
int color[] = new int[40];
for (int i = 0 ; i<40;i++)
color[i]=1;
Cromatico c = new Cromatico(matriz, color);
}
}
import java.io.IOException;
public class Cromatico {
Cromatico(int[][]matriz, int[] color, int fila) throws IOException{
for (int i = 0; i<fila;i++){
for (int j = 0 ; j<fila;j++){
if (matriz[i][j] == 1 && color[i] == color [j]){
if (j<i)
color [i] ++;
else
color [j] ++;
}
}
}
int numeroCromatico = 1;
for (int k = 0; k<fila;k++){
System.out.print(".");
numeroCromatico = Math.max(numeroCromatico, color[k]);
}
System.out.println();
System.out.println("el numero cromatico del grafo es: " + numeroCromatico);
}
}
推荐答案
查找图的色数是NP完全的(请参见图形着色).即使确定给定的图形是否是3色的(也可以找到颜色)，它都是NP-Complete的.
Finding the chromatic number of a graph is NP-Complete (see Graph Coloring). It is NP-Complete even to determine if a given graph is 3-colorable (and also to find a coloring).
上一段链接到的Wiki页面上有一些算法描述，您可能可以使用.
The wiki page linked to in the previous paragraph has some algorithms descriptions which you can probably use.
btw，既然它是NP-Complete，而且您并不真正在意性能，为什么不尝试使用蛮力呢?
btw, since it is NP-Complete and you don't really care about performance, why don't you try using brute force?
猜测一个色数k，尝试顶点着色的所有可能性(最大k ^ n种可能性)，如果它不可着色，则对色数= min {n，2k}进行新的猜测.如果它是k色的，则对色数= max {k/2,1}的新猜测.重复此步骤，按照二进制搜索所使用的模式，找到最佳k.
Guess a chromatic number k, try all possibilities of vertex colouring (max k^n possibilities), if it is not colorable, new guess for chromatic number = min{n,2k}. If it is k-colorable, new guess for chromatic number = max{k/2,1}. Repeat, following the pattern used by binary search and find the optimal k.
祝你好运！
然后回答您的编辑.
增加颜色的两个选项均无效.另外，您的算法为O(n ^ 2).这本身足以说明您的算法很可能是错误的，即使没有寻找反例也是如此.这个问题是NP完全的！
Neither option of incrementing the color will work. Also, your algorithm is O(n^2). That itself is enough to tell it is highly likely that your algorithm is wrong, even without looking for counterexamples. This problem is NP-Complete!
这篇关于我需要一种算法来获得图的色数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
