gm learning
シュぺルナー・パズル
選択メニューからグラフを選んで，ゲームのスタートです．
色選択のパレットから色を選んで，
頂点を着色していきましょう．
ただし，その着色は頂点彩色の条件を
満たす必要はありません．
ただ頂点に色を付けているだけなら，簡単すぎます．
３つの頂点の色がすべて異なる三角形ができないように，
色を割り当ててください．
そういう禁止状態ができてしまうと，
その三角形がピンクになりますよ．
と言われたところで，
３色の頂点を持つ三角形を作らないだけでよいのなら，
すべて同じ色にしてしまえばいいですね．
そこで，初めに周囲の大きな三角形の３個の頂点を３色で塗っておきましょう．
すると，どうがんばっても，３色の三角形ができてしまいます．
どうしてなのでしょうか？
さらに，周囲を異なる色で塗らなくても，
使う色数を増やしていくと，やはり３色の三角形が回避できなくなります．
それぞれのグラフで，最低何色あれば，３色三角形が回避できなくなるのか調べてください．
最初に戻る