ハイパーグラフの例: X = { v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 } {\displaystyle X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}} , E = { e 1 , e 2 , e 3 , e 4 } {\displaystyle E=\{e_{1},e_{2},e_{3},e_{4}\}} = { { v 1 , v 2 , v 3 } , { v 2 , v 3 } , {\displaystyle =\{\{v_{1},v_{2},v_{3}\},\{v_{2},v_{3}\},} { v 3 , v 5 , v 6 } , { v 4 } } {\displaystyle \{v_{3},v_{5},v_{6}\},\{v_{4}\}\}} . ハイパーグラフ (英 : 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)」であるという。
ここで、 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})} があり、以下が成り立つ。
a i j = { 1 i f v i ∈ e j 0 o t h e r w i s e {\displaystyle a_{ij}=\left\{{\begin{matrix}1&\mathrm {if} ~v_{i}\in e_{j}\\0&\mathrm {otherwise} \end{matrix}}\right.} 接続行列の転置行列 A t {\displaystyle A^{t}} により定義されるハイパーグラフ H ∗ = ( V ∗ , E ∗ ) {\displaystyle H^{*}=(V^{*},E^{*})} を H {\displaystyle H} の「双対(dual)」であるといい、 V ∗ {\displaystyle V^{*}} は m 個の元からなる集合、 E ∗ {\displaystyle E^{*}} は n 個の V ∗ {\displaystyle V^{*}} の部分集合からなる集合である。 v j ∗ ∈ V ∗ {\displaystyle v_{j}^{*}\in V^{*}} と e i ∗ ∈ E ∗ {\displaystyle e_{i}^{*}\in E^{*}} について a i j = 1 {\displaystyle a_{ij}=1} であるときのみ v j ∗ ∈ e i ∗ {\displaystyle ~v_{j}^{*}\in e_{i}^{*}} である。一様なハイパーグラフの双対は、正則であり、逆も成り立つ。双対を考えることで新たな発見があることが多い。
ハイパーグラフの彩色 ハイパーグラフの彩色 は次のように定義される。 H = ( V , E ) {\displaystyle H=(V,E)} というハイパーグラフは ‖ V ‖ = n {\displaystyle \Vert V\Vert =n} であるとする。 C = { c 1 , c 2 , … , c n } {\displaystyle C=\{c_{1},c_{2},\ldots ,c_{n}\}} が H {\displaystyle H} の妥当な彩色であるとは、全ての e ∈ E , | e | > 1 {\displaystyle e\in E,\vert e\vert >1} について任意の頂点 v i , v j ∈ e {\displaystyle v_{i},v_{j}\in e} で c i ≠ c j {\displaystyle c_{i}\neq c_{j}} となる場合のみを指す。
関連項目 この記事は、クリエイティブ・コモンズ・ライセンス 表示-継承 3.0 非移植のもと提供されているオンライン数学辞典『PlanetMath 』の項目hypergraphの本文を含む
要素・定義・表現 指標 部分構造 ループ(英語版) 多重辺(英語版) 部分グラフ(英語版) 道 連結成分(英語版) 橋(英語版) カット クリーク 独立集合 支配集合(英語版) マッチング オイラー路 シュタイナー木 全体構造 固有名を持つグラフ トピック・定理 カテゴリ / コモンズ
典拠管理データベース
全般 国立図書館 フランス BnF data ドイツ イスラエル アメリカ チェコ その他