Java 实现Vizing定理

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

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

任何顶点的度数是入边或出边的总数。

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

注意 -色度指数是一个正整数，需要一定数量的不同颜色来着色所有边，使得同一个顶点永远不会与相同颜色的边共享。

示例

输入

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

输出

“`java

<pre><code class="line-numbers">**解释**

1 -> 2：颜色为1

2 -> 3：颜色为2

3 -> 4：颜色为1

4 -> 1：颜色为2

3 -> 5：颜色为3

0 -> 0：颜色为1

**输入**
“`java
totalEdges = 3, 1 -> 2, 2 -> 3, 3 -> 1

输出

“`java

<pre><code class="line-numbers">**解释**

1 -> 2：颜色为1

2 -> 3：颜色为2

3 -> 1：颜色为3

**输入**
“`java
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是最大度数。程序员可以输入任何图并观察其色度指数。