資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究Java程式查詢環圖的色指數
圖的色指數是一個引數，它指示為圖的所有邊著色所需的最少顏色數量，使得沒有兩條共享公共頂點的邊具有相同顏色的邊。在本文中，我們將討論如何使用Java程式語言查詢環圖的色指數。
什麼是環圖？
環圖是一個至少包含一條環路的圖。環路是從特定節點開始並在同一節點結束的路徑。
什麼是圖著色？
用於為圖的邊或圖的頂點著色的過程稱為“圖著色”。
圖的色指數是圖論中最重要的話題之一，因為它在現實生活中的許多場景中都有許多實際應用，例如任務排程、無線通訊網路中的頻率分配、暫存器分配等等。在本文中，我們將討論Vizing理論來檢測環圖的色指數，並使用Java程式語言實現。
什麼是頂點的度？
連線頂點的邊的數量稱為“頂點的度”。
Vizing定理
Vizing定理指出，如果一個簡單圖“G”的最大度為“d”，則圖“G”的色指數可以是“d”或“d+1”。您可以詳細瞭解Vizing定理中的演算法。
演算法
步驟1 - 初始化一個表示圖的二維陣列。
步驟2 - 初始化一個值為零的變數，表示圖的色指數。
步驟3 - 查詢圖“G”的每個頂點的度。
步驟4 - 計算圖“G”的最大度。
步驟5 - 如果圖“G”的最大度是偶數，則圖的色指數是最大度。
步驟6 - 否則，如果圖“G”的最大度是奇數，則圖的色指數是最大度 + 1。
示例
在下面的示例中，Vizing演算法在Java程式語言中實現，以查詢圖的色指數。
我們初始化一個二維陣列來表示一個圖，並將該圖傳遞給函式“chromaticIndexOfGraph”。此函式返回圖的色指數。該函式使用Vizing定理計算圖的色指數，該定理通常計算圖的每個頂點的度。在找到每個頂點的度之後，它從degree[]陣列中找到maxDegree。如果maxDegree是偶數，則函式返回maxDegree；否則，如果maxDegree是奇數，則返回maxDegree + 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);
}
}
輸出
Max Degree:3 Chromatic index: 4
時間複雜度：O(N2) 輔助空間：O(N)
在本文中，我們學習瞭如何使用Java程式語言查詢環圖的色指數。
130 次瀏覽
