資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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是最大度數。程式設計師可以輸入任何輸入並觀察其色數指數。
78 次瀏覽
