Java程序实现Vizing定理

---

在这个问题中，我们需要实现Vizing定理。Vizing定理用于图论。

定理陈述 - 对于任何无向图G，色数指数等于d或d+1，其中d是图的最大度数。

任何顶点的度数是进入或离开该顶点的边的总数。

问题陈述 - 我们给定一个图，需要实现Vizing定理来找到图的色数指数。

注意 - 色数指数是一个正整数，表示对所有边进行着色所需的不同的颜色总数，使得同一个顶点上的边永远不会使用相同的颜色。

示例

输入

totalEdges = 6, 1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1, 4 -> 5, 3 -> 5

输出

解释

1 -> 2：颜色为1

2 -> 3：颜色为2

3 -> 4：颜色为1

4 -> 1：颜色为2

3 -> 5：颜色为3

0 -> 0：颜色为1

输入

totalEdges = 3, 1 -> 2, 2 -> 3, 3 -> 1

输出

1 -> 2：颜色为1

2 -> 3：颜色为2

3 -> 1：颜色为3

输入

totalEdges = 10, 1 -> 5, 1 -> 2, 1 -> 4, 1 -> 3,  2 -> 3, 2 -> 4, 2 -> 5, 3 -> 4, 3 -> 5, 4 -> 5

输出

6

解释

1 -> 5：颜色为1

1 -> 2：颜色为2

1 -> 4：颜色为3

1 -> 3：颜色为4

2 -> 3：颜色为1

2 -> 4：颜色为4

2 -> 5：颜色为3

3 -> 4：颜色为2

3 -> 5：颜色为5

4 -> 5：颜色为6

方法1

此方法将使用二维数组来存储图的边。此外，我们将迭代每条边，并根据连接到同一顶点的其他边的颜色为边分配颜色。

算法

步骤1 - 定义变量'totalEdges'并将其初始化为图中的总边数。

步骤2 - 定义数组'edgeMatrix'，它存储边的起始顶点、结束顶点和颜色。最初，所有边的颜色都为-1。之后，初始化矩阵并添加边。

步骤3 - 执行findChrometicIndex()函数。在函数中，定义变量currentEdge和currentColor，分别表示边的颜色。

步骤4 - 使用循环为每条边分配颜色。将currentColor分配给edgeMatrix[currentEdge][2]。

步骤5 - 现在，我们需要检查与当前边的两个顶点相关的任何边是否包含相同的颜色。因此，定义变量'isSameColor'并将其初始化为false。

步骤6 - 遍历所有边。如果q等于currentEdge，则转到下一个迭代。

步骤7 - 如果任何边与当前边共享一个顶点并且具有相同的颜色，则将currentColor的值增加1并将isSameColor更新为true。

步骤8 - 如果isSameColor为true，则继续下一个迭代。否则，将currentColor更新为1并移动到下一条边。

步骤9 - 找到所有边中最大的颜色值，即图的色数指数。

示例

import java.util.*;
public class Main {
   public static void findChrometicIndex(int[][] edgeMatrix, int 
totalEdges) {
      // start color with 1
      int currentEdge = 0, currentColor = 1;
      // Making iterations
      while (currentEdge < totalEdges) {
         // Assign a current color to the current edge
         edgeMatrix[currentEdge][2] = currentColor;
         // variable to track the same color vertex on two different edges
         boolean isSameColor = false;
         // Traverse edges
         for (int q = 0; q < totalEdges; q++) {
            if (q == currentEdge)
               continue;
            // Check for the same vertex of two edges
            if ((edgeMatrix[currentEdge][0] == edgeMatrix[q][0]) || (edgeMatrix[currentEdge][1] == edgeMatrix[q][0])
                  || (edgeMatrix[currentEdge][0] == edgeMatrix[q][1])
                  || (edgeMatrix[currentEdge][1] == edgeMatrix[q][1])) {
               // If two edges share a vertex and the color is the same, increase the color by 1 and update isSameColor
               if (edgeMatrix[currentEdge][2] == edgeMatrix[q][2]) {
                  // Increment the color by 1
                  currentColor++;
                  isSameColor = true;
                  break;
               }
            }
         }
         // start a new iteration for the same color
         if (isSameColor == true) {
            continue;
         }
         // reset color to 1
         currentColor = 1;
         currentEdge++;
      }
      // Find the maximum color
      int MaxColorValue = -1;
      for (currentEdge = 0; currentEdge < totalEdges; currentEdge++) {
         MaxColorValue = Math.max(MaxColorValue, edgeMatrix[currentEdge]
         [2]);
      }
      System.out.println("Chromatic Index for the given graph is = " + 
      MaxColorValue);
   }
   public static void main(String[] args) {
      // variable to store total edges
      int totalEdges = 6;
      // array to store edges
      int[][] edgeMatrix = new int[totalEdges][3];
      // edgeMatrix[i][2] represents the color of edge, Initially -1
      for (int i = 0; i < totalEdges; i++) {
         edgeMatrix[i][2] = -1;
      }
      // add edges
      edgeMatrix[0][0] = 1;
      edgeMatrix[0][1] = 2;
      edgeMatrix[1][0] = 2;
      edgeMatrix[1][1] = 3;
      edgeMatrix[2][0] = 3;
      edgeMatrix[2][1] = 4;
      edgeMatrix[3][0] = 4;
      edgeMatrix[3][1] = 1;
      edgeMatrix[4][0] = 4;
      edgeMatrix[4][1] = 5;   
      edgeMatrix[4][0] = 3;
      edgeMatrix[4][1] = 5;
      findChrometicIndex(edgeMatrix, totalEdges);
   }
}

输出

Chromatic Index for the given graph is = 3

时间复杂度 - O(N*N)，其中N是边的总数。

空间复杂度 - O(1)，因为我们不使用额外的空间来查找色数指数。

在上面的代码中，我们证明了图的色数指数可以是d或d+1，其中d是最大度数。程序员可以输入任何输入并观察其色数指数。