我需要一种算法来获得图的色数

本文介绍了我需要一种算法来获得图的色数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

鉴于图的邻接矩阵，我需要获取色数(最小绘制图形的每个节点所需的颜色数，以便相邻节点获得不同的颜色.

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!