图着色问题维基百科,自由的 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] Jetson Nano B01 4GB Developer Kit
图着色问题(英语: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]