在 planar graph 上可以著 4 色。 Every planar graph is four-colorable. The problem of finding a minimum coloring of a graph is NP-hard. The corresponding decision problem (is there a coloring which uses at most k colors?) is NP-complete, and in fact was one of Karp's 21 NP-complete problems. It remains NP-complete even on planar graphs of degree at most 4, as shown by Garey and Johnson in 1974, although on planar graphs it's trivial for k ≠ 3 (due to the four color theorem). The four color theorem was the first major theorem to be proved using a computer, and the proof is not accepted by all mathematicians because it would be infeasible for a human to verify by hand (see computer-aided proof). Ultimately, one has to have faith in the correctness of the compiler and hardware executing the program used for the proof. http://en.wikipedia.org/wiki/Graph_coloring_problem http://en.wikipedia.org/wiki/Four_color_theorem -- <@#++＜ ~~~ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.220.92.244 ※ 編輯: yellowfishie 來自: 61.220.92.244 (04/11 21:33)