图着色问题

维基百科,自由的百科全书
跳转至: 导航搜索

图着色问题英语Graph Coloring Problem,簡稱GCP),又称着色问题,是最著名的NP-完全问题之一[1]

给定一个无向图G=(V, E),其中V为顶点集合,E为边集合,图着色问题即为将V分为K个颜色组,每个组形成一个独立集,即其中没有相邻的顶点。其优化版本是希望获得最小的K值[2]

參考來源[编辑]

  1. ^ Michael R. Garey; D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. 1979-01-15: 125 [2015-09-21]. ISBN 978-0716710455. 
  2. ^ Michael Molloy; Bruce Reed. Graph Colouring and the Probabilistic Method illustrated. Springer Science & Business Media. 2002: 3 [2015-09-22]. ISBN 9783540421399.