| 算法题解：图的着色问题（给定无向连通图的顶点数和边数计算图的色数） | 您所在的位置：网站首页 › 顶点着色问题公式推导 › 算法题解：图的着色问题（给定无向连通图的顶点数和边数计算图的色数） |
|
图的着色问题（给定图的顶点数和边数计算需要的颜色数）
问题描述
给定无向连通图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("边的连接"); // 读取边的连接 |
| CopyRight 2018-2019 实验室设备网 版权所有 |