图着色问题維基百科,自由的 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]