ハイパーグラフ

ハイパーグラフ（）とは、数学におけるグラフを一般化（拡張）したもので、エッジ（枝）が任意個数のノード（頂点）を連結できる。形式的には formula_1 という対で表され、formula_2 はノードあるいは頂点と呼ばれる要素の集合、formula_3 はハイパーエッジ（hyperedge）と呼ばれる formula_2 の空集合でない部分集合の集合である。したがって、formula_3 は formula_6 の部分集合である。ただし、formula_7 は formula_2 の冪集合を表す。通常のグラフのエッジは2つのノードの対で表されるが、ハイパーエッジは任意のノードの集合で表され、任意個のノードを含む。
グラフとは異なり、ハイパーグラフは紙上に図示するのが困難である。そのため、グラフ理論のような図解をされることは少なく、集合論の用語で表される傾向がある。
概要.
グラフ理論の多くの定理はハイパーグラフでも成り立つ。典型例としてラムゼーの定理がある。グラフの対称性に関する研究もハイパーグラフに拡張して適用可能である。ハイパーグラフが準同型であるとは、あるハイパーグラフの頂点集合から別のそれへの写像があり、1つのエッジがもう一方のエッジに対応することを意味する。ハイパーグラフが同型であるとは、逆向きにも準同型である場合をいう。ハイパーグラフが自己同型であるとは、頂点集合がラベルを付け直した頂点集合と準同型であることをいう。ハイパーグラフの自己同型の集合 "H" (= ("X", "E")) は、合成について群となり、ハイパーグラフの自己同型群と呼ばれ Aut("H") で表される。ハイパーグラフの集まりは、射としてのハイパーグラフ準同型の集まりからなる圏である。
ハイパーグラフ "H" = ("X", "E") の「横断（transversal）」または「ヒッティングセット（hitting set）」formula_9 とは、どのエッジとも、積集合が空ではない集合のことである。すなわち、Tと各エッジの間に共通なノードが必ず存在する。横断 "T" は、その真部分集合として横断と呼べるものがない場合に「最小」であるという。"H" の「横断ハイパーグラフ」は ("X", "F") で表されるハイパーグラフであり、"F" は "H" の全最小横断からなる。横断ハイパーグラフの計算は、機械学習などの計算機科学分野で応用されており、ゲーム理論、データベースのインデックス付け、充足可能性問題、最適化などと関連する。
各エッジの濃度（元の個数）が "k" であるようなハイパーグラフを「k一様（k-uniform）」または「kハイパーグラフ（k-hypergraph）」と呼ぶ。グラフは2一様なハイパーグラフである。頂点 "v" の次数 "d(v)" とは、その頂点が属するエッジの個数である。全ての頂点の次数が "k" であるハイパーグラフを「k正則（k-regular）」であるという。
ここで、formula_10 と formula_11 があるとする。全てのハイパーグラフには formula_12 の「接続行列」formula_13 があり、以下が成り立つ。
接続行列の転置行列 formula_15 により定義されるハイパーグラフ formula_16 を formula_17 の「双対（dual）」であるといい、formula_18 は "m" 個の元からなる集合、formula_19 は "n" 個の formula_18 の部分集合からなる集合である。formula_21 と formula_22 について formula_23 であるときのみ formula_24 である。一様なハイパーグラフの双対は、正則であり、逆も成り立つ。双対を考えることで新たな発見があることが多い。
ハイパーグラフの彩色.
ハイパーグラフの彩色は次のように定義される。formula_25 というハイパーグラフは formula_26 であるとする。formula_27 が formula_17 の妥当な彩色であるとは、全ての formula_29 について任意の頂点 formula_30 で formula_31 となる場合のみを指す。