インスタント・インサニティ
縦一列に積み上げられた4つのキューブにおいて、正面・背面・左側面・右側面の各方向の面における4つの色の配置をはっきりと示すようなグラフを作ってみよう。これは、2つの有向部分グラフを使えばいい。
4つのキューブを縦一列に積み上げる場合、各キューブの上になっている面と下になっている面の色はどうでもよくて、正面・背面・左側面・右側面の4方向の色だけが問題になる。つまり、この問題を解くには、キューブを縦一列に積み上げた時に、それぞれのキューブごとに、それぞれの色の面が、自分から見て正面・背面・左側面・右側面の4方向のどちら側に配置されていれば良いのかが把握できればいい。
4つのキューブにおける、全ての向かい合った2つの面の色の配置の情報を表すには、無向部分グラフではなく有向部分グラフが必要となる。なぜなら無向グラフを使った場合、各キューブにおいて「2つの面が向かい合っている」という情報しか示すことができず、その面が正面にあるのか背面にあるのか分からないためである。
1つの有向グラフで、キューブの正面と背面の情報を同時に表すことができ、もう一つの有向グラフで、キューブの左側面と右側面の情報を同時に表すことができる。したがって、2つの有向サブグラフを使えば、各キューブにおいて4方面に配置されるべき面の色の情報、すなわちパズルを解くのに必要となる全ての情報を表すことができる。
ただし、図2のグラフから、2つの色を結んだ辺(部分グラフ)を適当に選んで、新たに作る2つの有向グラフのそれぞれに割り振るようなことはしてはいけない。次のような基準で、割り振る対象の有向グラフを選択する必要がある。
2つの有向グラフにおいては、互いに共通の辺(同じ2色を結ぶ、同じ色の辺)が存在してはいけないものとする。