Java 用于查找循环图的色指数

色指数 是指指示着色所有图边所需的最小颜色数的参数，使得共享公共顶点的两条边没有相同颜色边。在本文中，我们将讨论如何使用Java编程语言查找循环图的色指数。

什么是循环图

循环图 是是指那个特定图中至少包含一个循环路径的图。循环路径是从特定节点开始且在同一节点结束的路径。

什么是图着色

对图的边或顶点进行着色的过程被称为“图着色”。

图的色指数是图论中最重要的主题之一，因为它在现实生活场景中有许多实际应用，如任务调度、无线通信网络中的频率分配、寄存器分配等。在本文中，我们将讨论Vizing理论来检测循环图的色指数，并使用Java编程语言实现。

顶点的度是什么

连接到顶点的边的数量称为 “顶点的度” 。

Vizing定理

Vizing定理指出，如果一个简单图G的最大度为d，则图G的色指数可以是d或d+1。你可以在vizing定理中详细了解算法。

步骤

步骤1 - 使用2维数组初始化表示图的数据结构。

步骤2 - 使用0初始化一个变量，表示图的色指数。

步骤3 - 计算图G的每个顶点的度。

步骤4 - 计算图G的最大度。

步骤5 - 如果图G的最大度为偶数，则图的色指数为最大度。

步骤6 - 否则，如果图G的最大度为奇数，则图的色指数为最大度+1。

示例

在下面的示例中，使用Java编程语言实现了Vizing算法来查找图的色指数。

我们初始化一个表示图的2维数组，并将该图传递给函数“chromaticIndexOfGraph”。该函数返回图的色指数。函数使用vizing定理计算图的色指数，该定理通常计算图的每个顶点的度。在找到每个顶点的度后，它从degree[]数组中找到最大度。如果最大度为偶数，则函数返回最大度；否则，如果最大度为奇数，则返回最大度+1的值。

import java.util.*;
public class Main {
   // returns the chromatic index of the graph
   public static int chromaticIndexOfGraph(int[][] graph, int n) {
      int maxDegree = 0;
      int degree[] = new int[n];
      for (int i = 0; i < graph.length; i++) {
         for (int j = 0; j < graph[i].length; j++) {
            if (graph[i][j] == 1) {
               degree[j]++;
            }
         }
      }
      for(int i=0 ; i<degree.length; i++) {
         if(degree[i] > maxDegree) {
            maxDegree = degree[i];
         }
      }
      System.out.println("Max Degree:" + maxDegree);
      if (maxDegree % 2 == 0) {

         return maxDegree; //if maxDegree is even then chromaticIndex is maxDegree
      } else {

         return maxDegree + 1; //if maxDegree is odd then chromaticIndex is maxDegree+1
      }
   }
   public static void main(String[] args) {
      int n = 4; // defines the number of vertices in Graph
      int[][] graph = {
         {0, 1, 1, 1},{1, 0, 1, 0},{1, 1, 0, 1},{1, 0, 1, 0}
      };
      int chromatic_index = chromaticIndexOfGraph(graph, n);
      System.out.println("Chromatic index: " + chromatic_index);
    }
}