結合構造とは
結合関係を表す理論としては無向グラフと無向グラフなどのグラフ理論やそれらのグラフを一般化したハイパーグラフが有名である。
このハイパーグラフをより現代幾何学や組合せ論で扱いやすくなるように定義しなおしたのが次で紹介する結合構造である。
結合構造(接続構造)
結合構造(接続構造)
空でない集合、と共通を持たない集合、と上の関係からなる組を(二次元)結合構造(incidence structure)という。
また、の元を点(point)、の元を直線(line)、の元を旗(flag)という。さらに、は旗集合の他に結合関係(incidence relation)と呼ぶこともしばしばある。
なお、簡単のためにをそれぞれ結合構造の点集合、直線集合、旗集合のことと略記する。
組合せ論では、有限の対象を扱うのが一般的なため結合構造でも有限版が定義される。
有限結合構造
結合構造に対してがそれぞれ有限のときを有限結合構造、または単に結合構造という。
部分集合との同一視
直線状の点と交点
を結合構造とする。
に対して、
に対してとする。
このときを点を通る直線の集合、を直線上にある点の集合という。そして、直線をと同一視して点が直線上にあるときにと表記する。
このとき直線に対して、の元をとの交点という。一般にこの交点の集合をと表記する。この交点の集合が一点の集合となるときその一点と同一視してのことをとの交点と呼ぶこともしばしばある。
であってもが成り立つこともある。これは直線が重なることを意味する。このことは組合せ論で重複を許す組み合わせのこととなるため、一般に扱うのが難しい。そこでこの直線の重なりがない場合を特別視して結合構造を単純な結合構造ということもある。
結合構造の例
定義ばかりではつまらないので、結合構造の例をいくつか挙げてみる。
無向グラフとハイパーグラフ
点を頂点、直線を辺、旗を頂点と辺の結合関係とすると無向グラフやハイパーグラフは結合構造とみることができる。(画像はそれぞれグラフ理論(
Wikipedia
)、ハイパーグラフ(
Wikipedia
)から拝借してます。)
無向グラフ
ハイパーグラフ
路線図
点を駅、直線を路線、旗を路線と駅の関係とすると路線図は結合構造とみることができる。
ユークリッド平面などの平面空間
点を平面上の点、直線を平面上の点、旗を直線と点の包含関係とすると平面は結合構造とみることができる。なお、この結合構造は有限とは限らない。
例えば、ユークリッド空間(
Wikipedia
)は無限結合構造、有限幾何学(
Wikipedia
)で良く使われる位数3のアフィン平面や位数3のファノ平面は有限結合構造である。
構造から構造の生成
構造を調べるのに単体では扱うのが難しいので、ある意味で対となる構造を生みだして考えることが多い。例えば、「数えるために全体からそれ以外を引く」、「群の構造を調べるために反対群を考える」、「圏論の双対概念」など幾らでもある。
結合構造でも似たようなことをする。そこで、補構造と双対構造を紹介する。
補構造
結合構造に対し、とする。
このとき組をの補構造と呼ぶ。
これをと表記する。
同じく組合せ論の一つであるグラフ理論においてのグラフの補構造(補グラフ)は、ここで定義した方法では定義できない。ここで定義できるのは(無向)ハイパーグラフの補構造である。グラフの補構造ではない理由は、辺で接続していない頂点の集合が必ずしもサイズが2になるわけではないためである。
もちろん補構造の補構造は元に戻る。
実はこの補構造は、次の結合行列を用いて定義できる。
結合行列
を結合構造とする。このとき行列(点や直線は適当な順番に並んでおり、行列のインデックスを定めているものとする)を
で定義する。この行列をの結合行列、または接続行列(incidence matrix,
Wikipedia
)という。
そして、を結合構造の結合行列のことと略記する。
この結合行列を用いると補構造は次で定義される。
補構造(結合行列を用いた定義)
を結合構造とし、行列を成分がすべての行列とする。
このとき行列を接続行列として持つ結合構造をの補構造という。
証明は自明なので省略する。
次は、双対構造を説明する。
双対構造
結合構造に対し、組をの双対構造という。
これをと表記する。
双対構造も同様に次が成り立つ。
そして、双対構造も結合行列で定義できる。
双対構造(結合行列を用いた定義)
を結合構造とする。
このとき結合行列の転置行列を接続行列として持つ結合構造をの双対構造という。
こちらの定義の同値性も自明である。
元の構造のクラス次第では補構造や双対構造は同じクラスになるので調べるのに便利な時がしばしば存在する。
よく使われる調べ方
補構造や双対構造以外にもよく使われる調べ方が他にもある。
ある種の正則条件の設定
先ほど出てきた扱いやすいクラスを得るための条件である、ある種の正則条件の設定である。
「任意の異なる二点を通る直線はただ一つ」と「任意の直線は二つ以上の点からなる」、「直線が二本以上存在する」という条件を結合構造が満たすとき、その結合構造を線形幾何という。
ここでは直線をブロックと呼ぶことにする。
となる正整数 に対して「点の数は個である。」、「各ブロックに含まれる点の数は個である。」、「任意の相異なる個の点に対してそれらを含むブロックの個数は個であり、そのブロックの個数は個の点の取り方によらない。」を結合構造が満たすとき、その結合構造は-デザインという。
なお、-は無向グラフとしても見ることができる。
準同型写像
とを結合構造とする。が次の三つの条件を満たしているとき、をからへの準同型写像という。
- はからへの写像である。
- はからへの写像である。
一般的な準同型の定義と同様に逆写像、同型も定義される。また、有限で単純な結合構造から自身への自己同型写像のとき自己同型群を置換群とみることで、置換群の旗集合に対して結合構造への置換群による作用が定義できる。同様にして結合構造への群の作用も定義できる。(これらの定義を紹介すると長くなりすぎるのでここでは説明しない。)
おわりに
今回は結合構造の利用については解説していないが、今後どこかで書くと思う。
以上です。