图的着色问题(给定图的顶点数和边数计算需要的颜色数)
问题描述
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使图G中每条边的两个顶点有不同的颜色?
问题分析
这个问题是图的m可着色判定问题。
若一个图最少需要m种颜色才能使图中每条边相连接的两个顶点着不同颜色,称这个数m为这个图的色数。
求一个图的色数m称为图的m可着色优化问题。
给定一个图以及m种颜色,请计算出涂色方案数。
算法实现
package com.bean.algorithm.graph;import java.util.Scanner;
/** 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。* 是否有一种着色法使图G中每条边的两个顶点有不同的颜色?* */
public class MGraphColoring {public static int N=100;public static void main(String[] args) {// 接收键盘输入数据Scanner in = new Scanner(System.in);// 定义一个二维数组,限定int[][] a = new int[N][N];// 定义一个一维数组int[] b = new int[N];System.out.println("请输入顶点的数目和边的数目(顶点数小于100个)");// n——顶点数;m——边数int n = in.nextInt();int m = in.nextInt();System.out.println("边的连接");// 读取边的连接