ハイパーグラフ
ハイパーグラフ（英: Hypergraph）とは、数学におけるグラフを一般化（拡張）したもので、エッジ（枝）が任意個数のノード（頂点）を連結できる。形式的には [math](X,E)[/math] という対で表され、[math]X[/math] はノードあるいは頂点と呼ばれる要素の集合、[math]E[/math] はハイパーエッジ（hyperedge）と呼ばれる [math]X[/math] の空集合でない部分集合の集合である。従って、[math]E[/math] は [math]\mathcal{P}(X) \setminus \{\emptyset\}[/math] の部分集合である。ただし、[math]\mathcal{P}(X)[/math] は [math]X[/math] の冪集合を表す。通常のグラフのエッジは2つのノードの対で表されるが、ハイパーエッジは任意のノードの集合で表され、任意個のノードを含む。
グラフとは異なり、ハイパーグラフは紙上に図示するのが困難である。そのため、グラフ理論のような図解をされることは少なく、集合論の用語で表される傾向がある。
概要
グラフ理論の多くの定理はハイパーグラフでも成り立つ。典型例としてラムゼーの定理がある。グラフの対称性に関する研究もハイパーグラフに拡張して適用可能である。ハイパーグラフが準同型であるとは、あるハイパーグラフの頂点集合から別のそれへの写像があり、1つのエッジがもう一方のエッジに対応することを意味する。ハイパーグラフが同型であるとは、逆向きにも準同型である場合をいう。ハイパーグラフが自己同型であるとは、頂点集合がラベルを付け直した頂点集合と準同型であることをいう。ハイパーグラフの自己同型の集合 H (= (X, E)) は、合成について群となり、ハイパーグラフの自己同型群と呼ばれ Aut(H) で表される。ハイパーグラフの集まりは、射としてのハイパーグラフ準同型の集まりからなる圏である。
ハイパーグラフ H = (X, E) の「横断（transversal）」または「ヒッティングセット（hitting set）」[math]T\subseteq X[/math] とは、どのエッジとも、積集合が空ではない集合のことである。すなわち、Tと各エッジの間に共通なノードが必ず存在する。横断 T は、その真部分集合として横断と呼べるものがない場合に「最小」であるという。H の「横断ハイパーグラフ」は (X, F) で表されるハイパーグラフであり、F は H の全最小横断からなる。横断ハイパーグラフの計算は、機械学習などの計算機科学分野で応用されており、ゲーム理論、データベースのインデックス付け、充足可能性問題、最適化などと関連する。
各エッジの濃度（元の個数）が k であるようなハイパーグラフを「k一様（k-uniform）」または「kハイパーグラフ（k-hypergraph）」と呼ぶ。グラフは2一様なハイパーグラフである。頂点 v の次数 d(v) とは、その頂点が属するエッジの個数である。全ての頂点の次数が k であるハイパーグラフを「k正則（k-regular）」であるという。
ここで、[math]V = \{v_1, v_2, ~\ldots, ~ v_n\}[/math] と [math]E = \{e_1, e_2, ~ \ldots, ~ e_m\}[/math] があるとする。全てのハイパーグラフには [math]n \times m[/math] の「接続行列（incidence matrix）」[math]A = (a_{ij})[/math] があり、以下が成り立つ。
- [math]a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise} \end{matrix} \right.[/math]
接続行列の転置行列 [math]A^t[/math] により定義されるハイパーグラフ [math]H^* = (V^*, E^*)[/math] を [math]H[/math] の「双対（dual）」であるといい、[math]V^*[/math] は m 個の元からなる集合、[math]E^*[/math] は n 個の [math]V^*[/math] の部分集合からなる集合である。[math]v^*_j \in V^*[/math] と [math]e^*_i \in E^*[/math] について [math]a_{ij} = 1[/math] であるときのみ [math]~ v^*_j \in e^*_i[/math] である。一様なハイパーグラフの双対は、正則であり、逆も成り立つ。双対を考えることで新たな発見があることが多い。
ハイパーグラフの彩色
ハイパーグラフの彩色は次のように定義される。[math]H=(V,E)[/math] というハイパーグラフは [math]\Vert V\Vert = n[/math] であるとする。[math]C=\{c_1, c_2, \ldots, c_n\}[/math] が [math]H[/math] の妥当な彩色であるとは、全ての [math]e \in E, \vert e\vert \gt 1[/math] について任意の頂点 [math]v_i, v_j \in e[/math] で [math]c_i \neq c_j[/math] となる場合のみを指す。