その2、2つの有向部分グラフの制作

ウィキペディア小見出し辞書

その2、2つの有向部分グラフの制作

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/12/26 21:50 UTC 版)

「インスタント・インサニティ」の記事における「その2、2つの有向部分グラフの制作」の解説

縦一列に積み上げられた4つのキューブにおいて、正面・背面・左側面・右側面の各方向の面における4つの色の配置をはっきりと示すようなグラフを作ってみよう。これは、2つの有向部分グラフを使えばいい。 4つのキューブを縦一列に積み上げる場合、各キューブの上になっている面と下になっている面の色はどうでもよくて、正面・背面・左側面・右側面の4方向の色だけが問題になる。つまり、この問題を解くには、キューブを縦一列に積み上げた時に、それぞれのキューブごとに、それぞれの色の面が、自分から見て正面・背面・左側面・右側面の4方向のどちら側に配置されていれば良いのかが把握できればいい。 4つのキューブにおける、全ての向かい合った2つの面の色の配置の情報を表すには、無向部分グラフではなく有向部分グラフが必要となる。なぜなら無向グラフを使った場合、各キューブにおいて「2つの面が向かい合っている」という情報しか示すことができず、その面が正面にあるのか背面にあるのか分からないためである。 1つの有向グラフで、キューブの正面と背面の情報を同時に表すことができ、もう一つの有向グラフで、キューブの左側面と右側面の情報を同時に表すことができる。したがって、2つの有向サブグラフを使えば、各キューブにおいて4方面に配置されるべき面の色の情報、すなわちパズルを解くのに必要となる全ての情報を表すことができる。 ただし、図2のグラフから、2つの色を結んだ辺（部分グラフ）を適当に選んで、新たに作る2つの有向グラフのそれぞれに割り振るようなことはしてはいけない。次のような基準で、割り振る対象の有向グラフを選択する必要がある。 2つの有向グラフにおいては、互いに共通の辺（同じ2色を結ぶ、同じ色の辺）が存在してはいけないものとする。「共通の辺が存在する」と言うのは、少なくとも1つのキューブがまったく同じ色で構成された向かい合わせの面のペアを持っていることを意味する。例えば、キューブの正面・背面のペアと、左側面・右側面のペアがどちらも赤と青で構成されている、と言うような状況だが、こんなことはあってはいけない。 2つの有向グラフのそれぞれにおいては、図2のグラフの辺のうち、各キューブごとに1つの辺しか引用できないものとする。なぜなら、新たに作る2つの有向グラフのそれぞれの辺は、4つの全てのキューブから引用される必要があるからだ。そもそも、グラフの1つの辺だけで、向かい合わせになった2つの面の情報を完全に示すことができるので、各キューブから引用する辺は1つだけで構わない。 2つの有向グラフにおいては、全ての点は、次数が「2」（つまり、2本の辺が接続されている）でないといけないものとする。これは、次数が2の場合、その点の色は2枚の面にしか現れることがない、ということを意味するからだ。正面4枚と背面4枚（もしくは左側面4枚と右側面4枚）、合計8枚の面の集合において、4種類の色があり、各色ごとに2枚の面がある、と考えれば理解しやすいだろう。 上記のルールに従って、図2のグラフから辺（部分グラフ）を抜き出して新たな2つの有向グラフに割り振った結果、図3のような2つの有向グラフが導かれた。最初の有向グラフは、縦一列に積み上げた4つのキューブにおける、「正面・背面」の2方面の色の情報を同時に示したものである。2番目の有向グラフは、縦一列に積み上げた4つのキューブにおける、「左側面・右側面」の2方面の色の情報を同時に示したものである。