集合トランプにまつわる集合の諸概念(応用編)
以前の記事では、「属する」「含む」「和集合」「補集合」などなど、集合に関する基礎的な概念を紹介しました:
一方で、集合トランプゲームの中には、「集合論」の範囲を飛び越えた概念を用いているものもあります。「集合」という概念は基礎的かつ汎用的であるゆえに、数学のあらゆる分野で用いられています。そのため、集合というものを使うだけでも、数学のさまざまな分野で "遊ぶ" ことができるのです!
この記事では、そんな "応用的な" 集合トランプゲームで用いられている概念の紹介・説明を行っています。
目次
位相
数学には「位相空間論」という分野があるのですが、そこでは 位相 (topology) *1 という概念が顔を出します。どんなものかというと:
集合 に対し、 が 上の位相である( 上に位相構造を定める)とは、以下の 3 条件を満たしていることをいう:
- 有限個の に対し、
- 任意個の に対し、
よく、位相とは「"近さ" を表すグループ分け」みたいなイメージだ、とか言われていたりいなかったりするのですが、上の定義から "近さ" っぽさは感じ取れませんね……。この記事では、この抽象的でむずかしそうな「一般の場合」における位相については深く触れないことにして、「集合トランプでの実用に耐える程度の」位相の解説をします。
集合トランプでは、全体集合 でした。この の上の位相のみを考えることにすれば、上のややこしい定義は以下のように言い換えることができます:
が 上の位相であるとは、以下の 2 条件を満たしていることをいう:
- に対し、
標語的に言えば、 上の位相とは、 と が属していて、かつ和 () と積 () について閉じているような、「いくつかの の部分集合」の集合のことを指します。
具体例を挙げます。まず、 上のいちばん単純な位相として、
があります。条件 1. に従って、最低限必要な 2 つの集合 だけを集めたものですね。条件 2. を満たしていることも、かんたんにわかるかと思います。
それから、 の部分集合を全部集めたもの、つまり のべき集合:
これも、 上に位相を定めます。この位相にはあらゆる集合が属しているわけだから、その中のどの 2 つをとってきても、それらの和集合や共通部分はこの位相の中にあるはずですよね。
ちょっと難しい例では、
なんかも 上の位相になります。条件 2. を満たしていることを確認してみてください。
グラフの隣接リスト表現
「グラフ理論」というワードを聞いたことがありますでしょうか。これは、その名の通り、グラフ と呼ばれるものについて考える分野です。ここでいうグラフとは、いくつかの 頂点 が 辺 によってつながっている、以下のようなものを指します:
ところで、こういったグラフを表現しようと思ったとき、いちいち図を描くのは面倒ですね。この例のように頂点の数が十分に少ないときはまだしも、頂点が 個とか 個とか、あるいは無限個とかになってしまうと、もうどうしようもありません。
そこで、お絵描きせずに グラフを表現する方法が求められます。ここでは、そのような方法のひとつである、隣接リスト表現 というものを紹介します。
試しに、上で例示したグラフを、隣接リスト表現に直してみます。まず、各頂点をちゃんと区別できるように、番号を振ってあげましょう:
そうしたら、各頂点について、「その頂点が結びついている頂点」を列挙します:
- 頂点 とつながっている頂点は
- 頂点 とつながっている頂点は
- 頂点 とつながっている頂点は
- 頂点 とつながっている頂点は
- 頂点 とつながっている頂点は
そして、これらを各頂点ごとにまとめて(集合にして)並べたもの:
が、グラフの隣接リスト表現です。この集合 5 つ組について、1 番目の集合は頂点 に隣接する頂点、2 番目の集合は頂点 に隣接する頂点たち、…… と読み取っていくと、ちゃんと元のグラフを復元できることが確かめられますね。*2
以下に、5 頂点からなるグラフの隣接リスト表現を表示する、javascript で動作するプログラムを用意しました。2 つの頂点がクリックで選択されると、それらの間に辺がなければ追加、あれば削除します。*3 いろいろ試して、隣接リスト表現と仲良くなってみてください。