グラフ３彩色問題

けっこう昔に作った Flash アプリ．


任意のグラフを生成したあと，その３彩色問題を 3-term DNF 学習問題へ還元して解となる3-term DNF が満たす条件の例を生成する




クリックでFlashページに飛びます




補足：

グラフ３彩色問題は、次の変換によって 3-term DNF 学習問題へ還元される。
・ノード v_i と変数 x_i との対応： 3-term DNF f(x₁, x₂, …, x_n) の第 c 項(c = 1, 2, 3) に x_i が含まれないとき、色 c を v_i へ割り当てることができる。
・全てのノードにいずれかの色が割り当てられる条件： すべての i について、x_i のみが 0 で他の変数がみな 1 のとき f は充足される。(x_i を含まない項が少なくとも１つ存在する)
・隣り合うノードに異なる色が割り当てられる条件： すべての枝についてその両端のノードに対応する変数 x_a, x_b が 0 で、他の変数がみな 1 のとき f は充足されない。(x_a, x_b を共に含まない項が存在しない)