集合のグラフ表現



  • べき集合
    • k個の要素を持つ集合のべき集合は2^kある。
    • べき集合の要素(それぞれが部分集合)が半順序の性質を持ち、その中でも特別の性質を持つ束であることは、この記事(順序集合と束)とこの記事(部分集合の束のグラフ表現)で書いた。
    • 部分集合の関係がグラフになっている。半順序関係があるから、有向グラフである(ただし、「部分集合の束のグラフ表現」の記事では、すべての辺が描図上、上下関係にある点を結び、上の点から下の点へ(その逆でもよい)に向きがあるものとして、辺に矢印頭を描いていない)。
  • k個の集合A_i or ¥bar{A_i}, i=1,2,...,kを用いて、全体を2^kの相互に交わりを持たない部分集合に分けることもできる。
    • (A_1 | ¥bar{A_1}) ¥cap (A_2 | ¥bar{A_2}) ¥cap ... ¥cap (A_k | ¥bar{A_k})
    • このような2^kの部分集合は、包含関係は一切なく、したがって、包含関係による順序(半順序)もない。
    • 2つの部分集合に関係を与えるとすれば、(A_1 | ¥bar{A_1}) ¥cap (A_2 | ¥bar{A_2}) ¥cap ... ¥cap (A_k | ¥bar{A_k})(A_i | ¥bar{A_i})の選び方の遠近関係を評価し、選び方がたった1つしか違わない場合に辺をとることができる。このようにすると、2つの部分集合を現す点の間には距離が定義され、パスの長さがそれに相当することとなる。
    • このようにして出来上がるグラフは、点の数、辺の数が、前項の束のグラフに一致するが、無向グラフである点が異なる。