集合トランプ

次世代のトランプ「集合トランプ」で遊べるゲームを紹介しています

集合トランプにまつわる集合の諸概念(応用編)

以前の記事では、「属する」「含む」「和集合」「補集合」などなど、集合に関する基礎的な概念を紹介しました:

一方で、集合トランプゲームの中には、「集合論」の範囲を飛び越えた概念を用いているものもあります。「集合」という概念は基礎的かつ汎用的であるゆえに、数学のあらゆる分野で用いられています。そのため、集合というものを使うだけでも、数学のさまざまな分野で "遊ぶ" ことができるのです!

この記事では、そんな "応用的な" 集合トランプゲームで用いられている概念の紹介・説明を行っています。

目次

位相

数学には「位相空間論」という分野があるのですが、そこでは 位相 (topology) *1 という概念が顔を出します。どんなものかというと:

集合  X に対し、 \mathcal O \subset \mathcal P(X) X 上の位相である( X 上に位相構造を定める)とは、以下の 3 条件を満たしていることをいう:

  1.  \emptyset, X \in \mathcal O
  2. 有限個の  A_\lambda \in \mathcal O に対し、 \bigcap_\lambda A_\lambda \in \mathcal O
  3. 任意個の  A_\lambda \in \mathcal O に対し、 \bigcup_\lambda A_\lambda \in \mathcal O

よく、位相とは「"近さ" を表すグループ分け」みたいなイメージだ、とか言われていたりいなかったりするのですが、上の定義から "近さ" っぽさは感じ取れませんね……。この記事では、この抽象的でむずかしそうな「一般の場合」における位相については深く触れないことにして、「集合トランプでの実用に耐える程度の」位相の解説をします。

集合トランプでは、全体集合  U = \{1, 2, 3, 4, 5\} でした。この  U の上の位相のみを考えることにすれば、上のややこしい定義は以下のように言い換えることができます:

 \mathcal O \subset \mathcal P(U) U 上の位相であるとは、以下の 2 条件を満たしていることをいう:

  1.  \emptyset, U \in \mathcal O
  2.  A_1, A_2 \in \mathcal O に対し、 A_1 \cup A_2,\ A_1 \cap A_2 \in \mathcal O

標語的に言えば、 U 上の位相とは、 \emptyset U が属していて、かつ和 ( \cup) と積 ( \cap) について閉じているような、「いくつかの  U の部分集合」の集合のことを指します。

具体例を挙げます。まず、 U 上のいちばん単純な位相として、

 \{\emptyset, U\}

 
があります。条件 1. に従って、最低限必要な 2 つの集合  \emptyset, U だけを集めたものですね。条件 2. を満たしていることも、かんたんにわかるかと思います。

それから、 U の部分集合を全部集めたもの、つまり  U のべき集合:

 \mathcal P(U)

 
これも、 U 上に位相を定めます。この位相にはあらゆる集合が属しているわけだから、その中のどの 2 つをとってきても、それらの和集合や共通部分はこの位相の中にあるはずですよね。

ちょっと難しい例では、

 \{\emptyset, \{1\}, \{1, 2\}, \{1, 3\}, \{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 3, 4\}, U\}

 
なんかも  U 上の位相になります。条件 2. を満たしていることを確認してみてください。

グラフの隣接リスト表現

グラフ理論」というワードを聞いたことがありますでしょうか。これは、その名の通り、グラフ と呼ばれるものについて考える分野です。ここでいうグラフとは、いくつかの 頂点 によってつながっている、以下のようなものを指します:

f:id:muratsubo:20190407211054p:plain
グラフの例

ところで、こういったグラフを表現しようと思ったとき、いちいち図を描くのは面倒ですね。この例のように頂点の数が十分に少ないときはまだしも、頂点が  100 個とか  5 \times 10^{15} 個とか、あるいは無限個とかになってしまうと、もうどうしようもありません。

そこで、お絵描きせずに グラフを表現する方法が求められます。ここでは、そのような方法のひとつである、隣接リスト表現 というものを紹介します。

試しに、上で例示したグラフを、隣接リスト表現に直してみます。まず、各頂点をちゃんと区別できるように、番号を振ってあげましょう:

f:id:muratsubo:20190407212618p:plain
各頂点に  1 \sim 5 の番号を振った

そうしたら、各頂点について、「その頂点が結びついている頂点」を列挙します:

  • 頂点  1 とつながっている頂点は  2, 3, 4
  • 頂点  2 とつながっている頂点は  1, 4
  • 頂点  3 とつながっている頂点は  1
  • 頂点  4 とつながっている頂点は  1, 2, 5
  • 頂点  5 とつながっている頂点は  4

そして、これらを各頂点ごとにまとめて(集合にして)並べたもの:

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

 
が、グラフの隣接リスト表現です。この集合 5 つ組について、1 番目の集合は頂点  1 に隣接する頂点、2 番目の集合は頂点  2 に隣接する頂点たち、…… と読み取っていくと、ちゃんと元のグラフを復元できることが確かめられますね。*2

以下に、5 頂点からなるグラフの隣接リスト表現を表示する、javascript で動作するプログラムを用意しました。2 つの頂点がクリックで選択されると、それらの間に辺がなければ追加、あれば削除します。*3 いろいろ試して、隣接リスト表現と仲良くなってみてください。

*1:同じ「位相」でも、物理の波らへんの話なんかで出てくる位相 (phase) はまた別物です。ややこしい

*2:グラフを考えるときは、「頂点どうしのつながりかた」のみに着目するものとします。この隣接リスト表現からは、たとえば元々のグラフの頂点の位置関係などを復元することはできませんが、そういう細かいことは気にしないのです。つながりかたさえ同じであればよいんです。

*3:2 つの頂点として同じものを選んでも構いません。その場合、自己ループ(ある頂点から出発して、同じ頂点に戻ってくるような辺)が追加または削除されます。