ハイパーグラフ
横断ハイパーグラフの計算は、機械学習などの計算機科学分野で応用されており、ゲーム理論、データベースのインデックス付け、充足可能性問題、最適化などと関連する。
各エッジの濃度(元の個数)が k であるようなハイパーグラフを「k一様(k-uniform)」または「kハイパーグラフ(k-hypergraph)」と呼ぶ。グラフは2一様なハイパーグラフである。頂点 v の次数 d(v) とは、その頂点が属するエッジの個数である。全ての頂点の次数が k であるハイパーグラフを「k正則(k-regular)」であるという。
ここで、 V = { v 1 , v 2 , ... , v n } {\displaystyle V=\{v_{1},v_{2},~\ldots ,~v_{n}\}} と E = { e 1 , e 2 , ... , e m } {\displaystyle E=\{e_{1},e_{2},~\ldots ,~e_{m}\}} があるとする。全てのハイパーグラフには n × m {\displaystyle n\times m} の「接続行列」 A = ( a i j ) {\displaystyle A=(a_{ij})} があり、以下が成り立つ。