{{Translated page}}
图着色问题(英語: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]
取材自維基百科 - 中文時事百科