この記事は英語版の対応するページ
を翻訳することにより充実させることができます。(2024年5月)翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。ハイパーグラフ(英: Hypergraph)とは、数学におけるグラフを一般化(拡張)したもので、エッジ(枝)が任意個数のノード(頂点)を連結できる。形式的には ( X , E ) {\displaystyle (X,E)} という対で表され、 X {\displaystyle X} はノードあるいは頂点と呼ばれる要素の集合、 E {\displaystyle E} はハイパーエッジ(hyperedge)と呼ばれる X {\displaystyle X} の空集合でない部分集合の集合である。したがって、 E {\displaystyle E} は P ( X ) ∖ { ∅ } {\displaystyle {\mathcal {P}}(X)\setminus \{\emptyset \}} の部分集合である。ただし、 P ( X ) {\displaystyle {\mathcal {P}}(X)} は X {\displaystyle X} の冪集合を表す。通常のグラフのエッジは2つのノードの対で表されるが、ハイパーエッジは任意のノードの集合で表され、任意個のノードを含む。
グラフとは異なり、ハイパーグラフは紙上に図示するのが困難である。そのため、グラフ理論のような図解をされることは少なく、集合論の用語で表される傾向がある。 グラフ理論の多くの定理はハイパーグラフでも成り立つ。典型例としてラムゼーの定理がある。グラフの対称性に関する研究もハイパーグラフに拡張して適用可能である。ハイパーグラフが準同型であるとは、あるハイパーグラフの頂点集合から別のそれへの写像があり、1つのエッジがもう一方のエッジに対応することを意味する。ハイパーグラフが同型であるとは、逆向きにも準同型である場合をいう。ハイパーグラフが自己同型であるとは、頂点集合がラベルを付け直した頂点集合と準同型であることをいう。ハイパーグラフの自己同型の集合 H (= (X, E)) は、合成について群となり、ハイパーグラフの自己同型群と呼ばれ Aut(H) で表される。ハイパーグラフの集まりは、射としてのハイパーグラフ準同型の集まりからなる圏である。 ハイパーグラフ H = (X, E) の「横断(transversal)」または「ヒッティングセット(hitting set)」 T ⊆ X {\displaystyle T\subseteq X} とは、どのエッジとも、積集合が空ではない集合のことである。すなわち、Tと各エッジの間に共通なノードが必ず存在する。横断 T は、その真部分集合として横断と呼べるものがない場合に「最小」であるという。H の「横断ハイパーグラフ」は (X, F) で表されるハイパーグラフであり、F は H の全最小横断からなる。横断ハイパーグラフの計算は、機械学習などの計算機科学分野で応用されており、ゲーム理論、データベースのインデックス付け、充足可能性問題、最適化などと関連する。 各エッジの濃度(元の個数)が k であるようなハイパーグラフを「k一様(k-uniform)」または「kハイパーグラフ(k-hypergraph)」と呼ぶ。グラフは2一様なハイパーグラフである。頂点 v の次数 d(v) とは、その頂点が属するエッジの個数である。全ての頂点の次数が k であるハイパーグラフを「k正則(k-regular)」であるという。
概要