概要

先日投稿した以下の記事で、「グラフの隣接リスト表現」というものを紹介していました：

紹介したということはつまり、この概念を用いるゲームがあるということです。それが、今回紹介する集合トランプゲーム adjaSet *1 です！

ルール

プレイヤーは、0 人でさえなければ 理論上どれだけ多くても 遊べます。

集合トランプ 1 色 32 枚をよく切って山札とし、そこから 12 枚程度引いて場に並べます。*2 プレイヤーは、場札の中から、隣接リスト表現となっている集合 5 枚組 を探してください。*3

条件を満たす組を最も早く見つけたプレイヤーが、その 5 枚を獲得して、山札から新たに 5 枚の場札を補充します。取れそうなカードがなくなるまでこれを繰り返して、より多くのカードを獲得したプレイヤーが勝利となります。

ルールは以上です。*4

テクニック

物は試し、以下の 12 個の集合から「隣接リスト表現」を探し出してみてください：

f:id:muratsubo:20190427220851j:image — 12 個の集合

どうですか？　発見できましたか？
ルール文の簡潔さとは裏腹に、隣接リストの組はそう簡単には見つけられないはずです。

カード 12 枚の中から順序も気にして 5 枚のカードを選ぶ方法は $_{12} \mathrm P_5 = 95040$ 通りもあります。そのうえ、条件を満たすような組はこの中に平均で およそ 0.1 % (95 組) しか存在しません。*5 さらに、そもそも条件を満たすかどうかの判定がそれほど簡単に行えないので、場当たり的に探したところで目的の 5 つ組はまず見つかりません。

そこで、隣接リストを効率的に探す方法をいくつか考えました。

包含列

$\{a\}, \{a, b\}$
$\{a\}, \{a, b\}, \{a, b, c\}$
$\{a\}, \{a, b\}, \{a, b, c\}, \{a, b, c, d\}$
$\{a\}, \{a, b\}, \{a, b, c\}, \{a, b, c, d\}, \{a, b, c, d, e\}$

このような「要素が 1 つずつ増えていく集合たち」は、"降順に" 並べると隣接リスト表現になります：

\[ \xymatrix{ \overset{\{a, b\}}a \ar@{-}[r] \ar@(dl,dr)@{-}[ ] & \overset{\{a\}}b } \] \[ \xymatrix{ \overset{\{a, b, c\}}a \ar@{-}@/^10pt/[rr] \ar@{-}[r] \ar@(dl,dr)@{-}[ ] & \overset{\{a, b\}}b \ar@(dl,dr)@{-}[ ] & \overset{\{a\}}c } \] \[ \xymatrix{ \overset{\{a, b, c, d\}}a \ar@{-}@/^15pt/[rrr] \ar@{-}@/^10pt/[rr] \ar@{-}[r] \ar@(dl,dr)@{-}[ ] & \overset{\{a, b, c\}}b \ar@{-}[r] \ar@(dl,dr)@{-}[ ] & \overset{\{a, b\}}c & \overset{\{a\}}d } \] \[ \xymatrix{ \overset{\{a, b, c, d, e\}}a \ar@{-}@/^20pt/[rrrr] \ar@{-}@/^15pt/[rrr] \ar@{-}@/^10pt/[rr] \ar@{-}[r] \ar@(dl,dr)@{-}[ ] & \overset{\{a, b, c, d\}}b \ar@{-}@/^10pt/[rr] \ar@{-}[r] \ar@(dl,dr)@{-}[ ] & \overset{\{a, b, c\}}c \ar@(dl,dr)@{-}[ ] & \overset{\{a, b\}}d & \overset{\{a\}}e } \]

このことを知っているだけでも、上の例にある 12 個の集合の中から、

\[ (\{2\}, \{1, 2, 3, 4, 5\}, \{2, 4\}, \{2, 3, 4, 5\}, \{2, 4, 5\}) \\ (\{1\}, \{2, 4, 5\}, \{3\}, \{2, 4\}, \{2\}) \]

などの隣接リスト表現を見つけ出すことができるようになります。

完全グラフ

すべての異なる頂点どうしが辺で結ばれているグラフを 完全グラフ といいます。完全グラフの隣接リストをつくるには：

3 頂点 $a, b, c$ からなる完全グラフ → $\{b, c\}, \{a, c\}, \{a, b\}$
4 頂点 $a, b, c, d$ からなる完全グラフ → $\{b, c, d\}, \{a, c, d\}, \{a, b, d\}, \{a, b, c\}$

のように、「 $n$ 頂点のうち $n-1$ 個が入っている $n$ 個の集合すべて」があればよいことになります：

\[ \xymatrix@C=7pt{ & \overset{\{b, c\}}a \ar@{-}[ld] \ar@{-}[rd] & \\ \overset{\{a, c\}}b \ar@{-}[rr] & & \overset{\{a, b\}}c } \] \[ \xymatrix{ \overset{\{b, c, d\}}a \ar@{-}[r] \ar@{-}[d] \ar@{-}[rd] & \overset{\{a, c, d\}}b \ar@{-}[d]\ar@{-}[ld] \\ \overset{\{a, b, d\}}c \ar@{-}[r] & \overset{\{a, b, c\}}d } \]

先ほどの例では、 $\{2, 4\}, \{4, 5\}, \{2, 4, 5\}$ の 3 つを用いれば、 $2, 4, 5$ を頂点とする完全グラフ（に $4$ の自己ループが加わったもの）を作れるので、これを基にして

\[ (\{1\}, \{4, 5\}, \{3\}, \{2, 4, 5\}, \{2, 4\}) \]

を得ることができます。

辺を加える

汎用的な考え方として、「いったん不完全なグラフを作ってしまい、その後に辺を付け足してつじつまを合わせる」というものがあります。

先ほどの 12 個の集合を再び例にします。もし仮に $\{3, 5\}$ があれば、 \[ (\ast, \ast, \{4, 5\}, \{3, 5\}, \{3, 4\}) \] とすれば 3 頂点の完全グラフができるのですが、残念ながら $\{3, 5\}$ が存在しません。そこで、代わりに "わりと似てる" $\{2, 3, 4, 5\}$ を入れてみます：