圖着色問題維基百科,自由的 encyclopedia 圖着色問題(英語:Graph Coloring Problem,簡稱GCP),又稱着色問題,是最著名的NP-完全問題之一[1]。 此條目可參照英語維基百科相應條目來擴充。 給定一個無向圖 G = ( V , E ) {\displaystyle G=(V,E)} ,其中 V {\displaystyle V} 為頂點集合, E {\displaystyle E} 為邊集合,圖着色問題即為將 V {\displaystyle V} 分為 K {\displaystyle K} 個顏色組,每個組形成一個獨立集,即其中沒有相鄰的頂點。其優化版本是希望獲得最小的 K {\displaystyle K} 值。[2]
圖着色問題(英語:Graph Coloring Problem,簡稱GCP),又稱着色問題,是最著名的NP-完全問題之一[1]。 此條目可參照英語維基百科相應條目來擴充。 給定一個無向圖 G = ( V , E ) {\displaystyle G=(V,E)} ,其中 V {\displaystyle V} 為頂點集合, E {\displaystyle E} 為邊集合,圖着色問題即為將 V {\displaystyle V} 分為 K {\displaystyle K} 個顏色組,每個組形成一個獨立集,即其中沒有相鄰的頂點。其優化版本是希望獲得最小的 K {\displaystyle K} 值。[2]