ハイパーグラフ

数学において、ハイパーグラフとは、辺が任意の数の頂点を結ぶことができるグラフの一般化である。これに対し、通常のグラフでは、辺は正確に2つの頂点を結ぶ。

正式には、有向ハイパーグラフはペアである${\displaystyle (X,E)}$、 どこ${\displaystyle X}$ノード、頂点、ポイント、または要素と呼ばれる要素の集合であり、${\displaystyle E}$は、部分集合のペアの集合です。${\displaystyle X}$これらのペアはそれぞれ${\displaystyle (D,C)\in E}$エッジまたはハイパーエッジと呼ばれる。頂点部分集合${\displaystyle D}$は尾部または領域として知られており、${\displaystyle C}$その中心または終域として。

ハイパーグラフの次数${\displaystyle (X,E)}$は頂点の数です${\displaystyle X}$ハイパーグラフのサイズは、エッジの数です。${\displaystyle E}$エッジの次数${\displaystyle e=(D,C)}$有向ハイパーグラフでは${\displaystyle |e|=(|D|,|C|)}$つまり、その尾部の頂点の数に続いて、その頭部の頂点の数です。

上記の定義は、各エッジの先頭または末尾を頂点の集合として定義することにより、有向グラフから有向ハイパーグラフに一般化されます（${\displaystyle C\subseteq X}$または${\displaystyle D\subseteq X}$単一の頂点としてではなく、複数の要素から構成される集合として扱われます。グラフは、これらの集合のそれぞれが1つの要素のみを含む特殊なケースです。したがって、辺の順序に依存しない標準的なグラフ理論の概念は、${\displaystyle |e|}$ハイパーグラフ理論に一般化する。

集合が与えられた ${\displaystyle {X}}$ そのパワーセットで ${\displaystyle {{\mathcal {P}}\left(X\right)}}$さらに、 ${\displaystyle {E}}$ と ${\displaystyle {E\subseteq {\mathcal {P}}\left(X\right)}}$ペア ${\displaystyle {\left(X,E\right)}}$ これは無向ハイパーグラフと呼ばれる。

ハイパーグラフは、接続構造として捉えることができます。特に、すべてのハイパーグラフには、対応する二部グラフの「接続グラフ」または「レヴィグラフ」が存在し、逆に、すべての二部グラフは、2色で彩色され、ハイパーグラフの頂点と辺に対応する色クラスが示されている場合、ハイパーグラフの接続グラフとみなすことができます。

ハイパーグラフには他にも多くの呼び名があります。計算幾何学では、無向ハイパーグラフはレンジ空間と呼ばれることがあり、その場合、ハイパーエッジはレンジと呼ばれます。^{[ 2 ]}協力ゲーム理論 では、ハイパーグラフは単純ゲーム（投票ゲーム）と呼ばれ、この概念は社会選択理論の問題解決に応用されます。一部の文献では、エッジはハイパーリンクまたはコネクタと呼ばれています。^{[ 3 ]}

ハイパーグラフの集合は、ハイパーグラフ準同型を射とする圏である。

^{無向ハイパーグラフは、充足可能性問題[ 4 ]} 、データベース^{[ 5 ]} 、機械学習^{[ 6 ]}、シュタイナー木問題^{[ 7} ]などのモデリングに役立ちます。機械学習タスクでは^、データモデルや分類器の正則化として広く使用されています^{[ 8 ]}。応用例としては、レコメンダーシステム（ハイパーエッジとしてのコミュニティ）^{[ 9 ] [ 10 ]} 、画像検索（ハイパーエッジとしての相関）^{[ 11 ]} 、バイオインフォマティクス（ハイパーエッジとしての生化学的相互作用） ^{[ 12 ]}などがあります。代表的なハイパーグラフ学習手法としては、ハイパーグラフラプラシアンでスペクトルグラフ理論を拡張したハイパーグラフスペクトルクラスタリング^{[ 13 ]} 、学習結果を制限するためにハイパーグラフ構造コストを追加するハイパーグラフ半教師あり学習^{[ 14 ]}などがあります。大規模なハイパーグラフ向けには、 Apache Sparkを使用して構築された分散フレームワーク^{[ 6 ]}も利用可能です。すべてのハイパーエッジが同じカーディナリティを持つハイパーグラフを研究することが望ましい場合があります。k-一様ハイパーグラフとは、すべてのハイパーエッジのサイズがkであるハイパーグラフのことです。（言い換えれば、そのようなハイパーグラフの1つは集合の集合であり、各集合はk個のノードを接続するハイパーエッジです。）したがって、2-一様ハイパーグラフはグラフであり、3-一様ハイパーグラフは順序付けされていない3つ組の集合であり、以下同様です。

^{有向ハイパーグラフは、電話アプリケーション[ 15 ]}、マネーロンダリングの検出^{[ 16 ]}、オペレーションズリサーチ^{[ 17 ]} 、および輸送計画などのモデル化に使用できます。また、ホーン充足可能性のモデル化にも使用できます。^{[ 18 ]}

グラフに関する多くの定理や概念はハイパーグラフにも適用され、特に以下の通りである。

• ハイパーグラフにおけるマッチング;
• ハイパーグラフにおける頂点被覆（別名：横断的）
• ハイパーグラフの線グラフ。
• ハイパーグラフ文法- ハイパーグラフのクラスに置換ルールのセットを追加することによって作成される。
• ラムゼーの定理；
• エルデシュ・コー・ラドの定理;
• 一様ハイパーグラフに関するクルスカル・カトナの定理。
• ハイパーグラフに関するホール型定理。

有向ハイパーグラフでは、推移閉包と最短経路問題が挙げられます。^{[ 17 ]}

ハイパーグラフはグラフよりも紙に描くのが難しいものの、多くの研究者がハイパーグラフの可視化手法を研究してきた。

ハイパーグラフの視覚的表現の 1 つとして、平面上の曲線を使用してグラフのエッジを描写する標準的なグラフ描画スタイルと同様に、ハイパーグラフの頂点は点、円盤、またはボックスとして描かれ、ハイパーエッジは頂点を葉とする木として描かれます。 ^{[ 19 ] [ 20 ]}頂点が点として表現されている場合、ハイパーエッジは点の集合を結ぶ滑らかな曲線、または点の集合を囲む単純な閉曲線として表示することもできます。^{[ 21 ] [ 22 ] [ 23 ]}

ハイパーグラフの可視化の別のスタイルであるハイパーグラフ描画の細分化モデル^{[ 24 ]}では、平面は領域に細分化され、各領域はハイパーグラフの単一の頂点を表します。ハイパーグラフのハイパーエッジは、これらの領域の連続する部分集合によって表され、色付け、周囲に輪郭を描くこと、またはその両方によって示されます。たとえば、n次ベン図は、 n個のハイパーエッジ（図を定義する曲線）と 2 ⁿ  −  1 個の頂点（これらの曲線が平面を細分化する領域によって表される）を持つハイパーグラフの細分化描画と見なすことができます。平面グラフの多項式時間認識とは対照的に、ハイパーグラフが平面細分化描画を持つかどうかを判断することはNP 完全ですが^{[ 25 ]}、領域の隣接パターンがパス、サイクル、または木に制約されている場合、この種の描画の存在を効率的にテストできます^{[ 26 ] 。}

ハイパーグラフの別の表現方法として、PAOH ^{[ 1 ]}と呼ばれるものが、この記事の冒頭の図に示されています。エッジは頂点を結ぶ垂直線です。頂点は左側に並んでいます。右側の凡例にはエッジの名前が示されています。これは動的ハイパーグラフ用に設計されていますが、単純なハイパーグラフにも使用できます。

古典的なハイパーグラフ彩色とは、セットから色を割り当てることである。${\displaystyle \{1,2,3,...,\lambda \}}$ハイパーグラフのすべての頂点に対して、各ハイパーエッジが少なくとも2つの異なる色の頂点を含むように色付けを行う。言い換えれば、濃度が2以上の単色ハイパーエッジは存在してはならない。この意味で、これはグラフ彩色法の直接的な一般化である。すべての彩色法において使用される異なる色の最小数を、ハイパーグラフの彩色数と呼ぶ。

最大k色を用いて彩色可能なハイパーグラフは、 k 彩色可能ハイパーグラフと呼ばれる。2 彩色可能なハイパーグラフは、まさに二部グラフである。

古典的なハイパーグラフ彩色には多くの一般化があります。その一つが、単色エッジが許容される混合ハイパーグラフ彩色です。混合ハイパーグラフの中には、任意の数の色で彩色できないものもあります。彩色不可能性の一般的な基準は知られていません。混合ハイパーグラフが彩色可能な場合、使用される色の最小数と最大数は、それぞれ下側彩色数と上側彩色数と呼ばれます。^{[ 27 ]}

ハイパーグラフは、次のような様々な特性を持つことができます。

• 空っぽ- 端がない。
• 非単純（または多重） - ループ（単一の頂点を持つハイパーエッジ）または繰り返しエッジがあり、同じ頂点のセットを含むエッジが 2 つ以上存在する可能性があることを意味します。
• シンプル- ループや重複する辺がない。
• ${\displaystyle d}$-通常- すべての頂点に次数がある${\displaystyle d}$つまり、正確に${\displaystyle d}$ハイパーエッジ。
• 2彩色可能- その頂点は、 UとVの2つのクラスに分割でき、カーディナリティが2以上の各ハイパーエッジには、両方のクラスから少なくとも1つの頂点が含まれる。別の用語は特性Bである。
  • より強い特性は、二部グラフであることとバランスが取れていることである。
• ${\displaystyle k}$-一様- 各ハイパーエッジは正確に${\displaystyle k}$頂点。
• ${\displaystyle k}$-partite - 頂点は分割されます${\displaystyle k}$各ハイパーエッジは、各タイプの頂点をちょうど1つずつ含んでいる。
  • 毎${\displaystyle k}$- 分割ハイパーグラフ (${\displaystyle k\geq 2}$) は両方とも${\displaystyle k}$-一様かつ二部グラフ（かつ2色彩色可能）。
• 縮小: ^{[ 28 ]}どのハイパーエッジも他のハイパーエッジの厳密な部分集合ではない。同等に、すべてのハイパーエッジは包含に関して極大である。ハイパーグラフの縮小は、他のハイパーエッジに含まれるすべてのハイパーエッジを削除することによって得られる縮小ハイパーグラフである。
• 下方閉性- 無向ハイパーグラフのエッジのすべての部分集合がハイパーエッジでもある。下方閉性ハイパーグラフは通常、抽象単体複体と呼ばれる。すべてのハイパーエッジの濃度が1でない限り、一般に縮約されない。
  • 拡大特性を持つ抽象的な単体複体をマトロイドと呼ぶ。
• 層状：任意の2つのハイパーエッジは互いに素であるか、または一方が他方に含まれるかのいずれかである。言い換えれば、ハイパーエッジの集合は層状集合族を形成する。
• つながる：すべての人へ${\displaystyle S\subseteq X}$と${\displaystyle \emptyset \neq S\neq X}$がある${\displaystyle e\in E}$両方を満たす${\displaystyle S}$そして${\displaystyle X\setminus S}$接続されていないハイパーグラフは、非接続ハイパーグラフと呼ばれます。

ハイパーグラフのリンクは任意のカーディナリティを持つことができるため、サブグラフの概念には、サブハイパーグラフ、部分ハイパーグラフ、セクションハイパーグラフと呼ばれるいくつかの概念が存在します。

させて${\displaystyle H=(X,E)}$頂点からなるハイパーグラフとする

${\displaystyle X=\lbrace x_{i}\mid i\in I_{v}\rbrace ,}$

エッジセットを持つ

${\displaystyle E=\lbrace e_{i}\mid i\in I_{e},e_{i}\subseteq X,e_{i}\neq \emptyset \rbrace ,}$

どこ${\displaystyle I_{v}}$そして${\displaystyle I_{e}}$これらはそれぞれ頂点と辺のインデックスセットです。

部分ハイパーグラフは、いくつかの頂点が削除されたハイパーグラフです。正式には、部分ハイパーグラフは${\displaystyle H_{A}}$誘発される${\displaystyle A\subseteq X}$は次のように定義される。

${\displaystyle H_{A}=\left(A,\lbrace e\cap A\mid e\in E,e\cap A\neq \emptyset \rbrace \right).}$

別の用語としては、HをAに制限するというものがある。^{[ 29 ]： 468}

接続されたコンポーネント${\displaystyle H}$は、最大連結部分ハイパーグラフである。${\displaystyle H}$つまり、部分ハイパーグラフ${\displaystyle H_{A}}$の${\displaystyle H}$誘発される${\displaystyle A}$そのため${\displaystyle H_{A}}$接続されており、部分ハイパーグラフは存在しない${\displaystyle H_{A'}}$と${\displaystyle A\subsetneq A'}$接続されています。

部分ハイパーグラフの拡張は、各ハイパーエッジが${\displaystyle H}$これは部分的にサブハイパーグラフに含まれている${\displaystyle H_{A}}$拡張機能に完全に含まれている${\displaystyle Ex(H_{A})}$正式に

${\displaystyle Ex(H_{A})=(A\cup A',E')}$と${\displaystyle A'=\bigcup _{e\in E}e\setminus A}$そして${\displaystyle E'=\lbrace e\in E\mid e\subseteq (A\cup A')\rbrace }$。

部分ハイパーグラフとは、一部のエッジが削除されたハイパーグラフのことである。^{[ 29 ]： 468}部分集合が与えられた場合${\displaystyle J\subset I_{e}}$エッジインデックスセットの、によって生成された部分ハイパーグラフ${\displaystyle J}$ハイパーグラフは

${\displaystyle \left(X,\lbrace e_{i}\mid i\in J\rbrace \right).}$

部分集合が与えられた場合${\displaystyle A\subseteq X}$セクションハイパーグラフは部分ハイパーグラフである

${\displaystyle H\times A=\left(A,\lbrace e_{i}\mid i\in I_{e},e_{i}\subseteq A\rbrace \right).}$

二重${\displaystyle H^{*}}$の${\displaystyle H}$は頂点と辺が入れ替わったハイパーグラフであり、頂点は次のように与えられる。${\displaystyle \lbrace e_{i}\rbrace }$そしてその辺は${\displaystyle \lbrace X_{m}\rbrace }$どこ

${\displaystyle X_{m}=\lbrace e_{i}\mid x_{m}\in e_{i}\rbrace .}$

等号の概念が以下のように適切に定義されると、ハイパーグラフの双対を取る操作は対合、すなわち、

${\displaystyle \left(H^{*}\right)^{*}=H.}$

連結ハイパーグラフHと同じ頂点集合を持つ連結グラフG は、 HのすべてのハイパーエッジがGに連結部分グラフを誘導する場合、 Hのホストグラフである。非連結ハイパーグラフHの場合、GとHの連結成分の間に全単射が存在し、 Gの各連結成分G 'が対応するH 'のホストである場合、G はホストグラフである。

ハイパーグラフの2セクション（またはクリークグラフ、表現グラフ、プライマルグラフ、ガイフマングラフ）とは、ハイパーグラフと同じ頂点を持ち、すべての頂点のペア間のエッジが同じハイパーエッジに含まれるグラフのことです。

させて${\displaystyle V=\{v_{1},v_{2},~\ldots ,~v_{n}\}}$そして${\displaystyle E=\{e_{1},e_{2},~\ldots ~e_{m}\}}$すべてのハイパーグラフには${\displaystyle n\times m}$発生率マトリックス。

無向ハイパーグラフの場合、${\displaystyle I=(b_{ij})}$どこ

${\displaystyle b_{ij}=\left\{{\begin{matrix}1&\mathrm {if} ~v_{i}\in e_{j}\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

転置​${\displaystyle I^{t}}$発生行列のハイパーグラフを定義する${\displaystyle H^{*}=(V^{*},\ E^{*})}$双対と呼ばれる${\displaystyle H}$、 どこ${\displaystyle V^{*}}$はm個の要素からなる集合であり、${\displaystyle E^{*}}$は、 n個の要素からなる部分集合の集合である。${\displaystyle V^{*}}$。 のために${\displaystyle v_{j}^{*}\in V^{*}}$そして${\displaystyle e_{i}^{*}\in E^{*},~v_{j}^{*}\in e_{i}^{*}}$かつその場合に限り${\displaystyle b_{ij}=1}$。

有向ハイパーグラフの場合、各ハイパーエッジの頭と尾は${\displaystyle e_{j}}$は、${\displaystyle H(e_{j})}$そして${\displaystyle T(e_{j})}$それぞれ。^{[ 18 ]}${\displaystyle I=(b_{ij})}$どこ

${\displaystyle b_{ij}=\left\{{\begin{matrix}-1&\mathrm {if} ~v_{i}\in T(e_{j})\\1&\mathrm {if} ~v_{i}\in H(e_{j})\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

ハイパーグラフの隣接行列は、グラフの隣接行列から類似したものを導き出すことができる。グラフの場合、隣接行列は頂点のペアが隣接しているかどうかを示す正方行列である。同様に、隣接行列を定義することができる。${\displaystyle A=(a_{ij})}$ハイパーエッジが一般的にハイパーグラフである場合${\displaystyle e_{k\leq m}}$実際の重みを持つ${\displaystyle w_{e_{k}}\in \mathbb {R} }$と

${\displaystyle a_{ij}=\left\{{\begin{matrix}w_{e_{k}}&\mathrm {if} ~(v_{i},v_{j})\in E\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

通常の無向グラフでは、サイクルと非巡回グラフという単一の自然な概念が存在するのに対し、ハイパーグラフでは、サイクルには複数の自然な非等価な定義が存在し、グラフの場合を考慮すると、それらは通常のサイクルの概念に収束する。

ハイパーグラフ準同型写像とは、あるハイパーグラフの頂点集合から別のハイパーグラフへの写像であり、各辺が他の1つの辺に対応するものである。

ハイパーグラフ${\displaystyle H=(X,E)}$ハイパーグラフと同型である${\displaystyle G=(Y,F)}$と表記される${\displaystyle H\simeq G}$全単射が存在する場合

${\displaystyle \phi :X\to Y}$

そして順列${\displaystyle \pi }$の${\displaystyle I}$そのため

${\displaystyle \phi (e_{i})=f_{\pi (i)}}$

全単射${\displaystyle \phi }$これはグラフの同型性と呼ばれます。

${\displaystyle H\simeq G}$かつその場合に限り${\displaystyle H^{*}\simeq G^{*}}$。

ハイパーグラフのエッジが明示的にラベル付けされている場合、強同型性という概念が追加されます。${\displaystyle H}$は​​${\displaystyle G}$置換が恒等置換である場合、次のように書く。${\displaystyle H\cong G}$強同型グラフはすべて同型であるが、その逆は必ずしも成り立たないことに注意してください。

ハイパーグラフの頂点が明示的にラベル付けされている場合、同値性の概念と等価性の概念が存在する。${\displaystyle H}$と同等​${\displaystyle G}$、そして、${\displaystyle H\equiv G}$同型性${\displaystyle \phi }$もっている

${\displaystyle \phi (x_{n})=y_{n}}$

そして

${\displaystyle \phi (e_{i})=f_{\pi (i)}}$

ご了承ください

${\displaystyle H\equiv G}$かつその場合に限り${\displaystyle H^{*}\cong G^{*}}$

さらに、順列${\displaystyle \pi }$アイデンティティは、${\displaystyle H}$等しい${\displaystyle G}$、そして、${\displaystyle H=G}$なお、この等式の定義では、グラフは自己双対性を持つことに注意してください。

${\displaystyle \left(H^{*}\right)^{*}=H}$

ハイパーグラフの自己同型とは、頂点集合からそれ自身への同型写像、つまり頂点のラベル付け替えのことです。ハイパーグラフH (= ( X , E ))の自己同型写像​​の集合は合成に関して群であり、ハイパーグラフの自己同型群と呼ばれ、Aut( H ) と表記されます。 

^{E. Dauber [ 42 ]}による分割定理によれば、辺推移的ハイパーグラフの場合、${\displaystyle H=(X,E)}$パーティションが存在する

${\displaystyle (X_{1},X_{2},\cdots ,X_{K})}$

頂点集合の${\displaystyle X}$部分ハイパーグラフが${\displaystyle H_{X_{k}}}$によって生成されました${\displaystyle X_{k}}$各${\displaystyle 1\leq k\leq K}$、そして、

${\displaystyle \sum _{k=1}^{K}r\left(H_{X_{k}}\right)=r(H)}$

どこ${\displaystyle r(H)}$Hのランクです。

その結果として、頂点推移的でない辺推移的なハイパーグラフは双彩色可能である。

グラフ分割（特にハイパーグラフ分割）は、IC設計^{[ 43 ]}や並列コンピューティング^{[ 44 ] [ 45 ] [ 46 ]}に多くの応用例がある。効率的でスケーラブルなハイパーグラフ分割アルゴリズムは、機械学習タスクで大規模なハイパーグラフを処理するためにも重要である。^{[ 6 ]}

ハイパーグラフの可能な一般化の 1 つは、エッジが他のエッジを指すことを許可することです。^{[ 47 ]}この一般化には 2 つのバリエーションがあります。1 つは、エッジが頂点の集合だけでなく、頂点のサブセット、頂点のサブセットのサブセットなど、無限に続くものも含むことができるというものです。本質的に、すべてのエッジは木または有向非巡回グラフの内部ノードであり、頂点は葉ノードです。ハイパーグラフは、共通の共有ノードを持つ木の集合です (つまり、特定の内部ノードまたは葉は、複数の異なる木に現れる可能性があります)。^{[ 48 ] [ 49 ]}逆に、すべての木の集合は、この一般化されたハイパーグラフとして理解できます。木はコンピュータ サイエンスや他の多くの数学の分野で広く使用されているため、ハイパーグラフも自然に現れると言えるでしょう。^{[ 50 ]}例えば、この一般化は項代数のモデルとして自然に現れます。辺は項に対応し、頂点は定数または変数に対応する。^{[ 51 ]}

このようなハイパーグラフの場合、集合メンバーシップは順序付けを提供するが、推移的ではないため、その順序付けは部分順序でも前順序でもない。 ^{[ 52 ]}この一般化のレヴィグラフに対応するグラフは、有向非巡回グラフである。^{[ 53 ]}例えば、頂点集合が次の一般化ハイパーグラフを考える。${\displaystyle V=\{a,b\}}$そしてその縁は${\displaystyle e_{1}=\{a,b\}}$そして${\displaystyle e_{2}=\{a,e_{1}\}}$その時、${\displaystyle b\in e_{1}}$そして${\displaystyle e_{1}\in e_{2}}$それは真実ではない${\displaystyle b\in e_{2}}$しかし、このようなハイパーグラフの集合メンバーシップの推移閉包は部分順序を誘導し、ハイパーグラフを部分順序集合に「平坦化」します。^{[ 54 ]}

あるいは、エッジが他のエッジを指すことを許容することもできます。これは、エッジが有向非巡回グラフのように順序付けられているという要件とは無関係です。^{[ 47 ] [ 48 ]}これにより、頂点を全く含まないエッジループを持つグラフが可能になります。たとえば、2つのエッジからなる一般化ハイパーグラフを考えてみましょう。${\displaystyle e_{1}}$そして${\displaystyle e_{2}}$、そして頂点はゼロなので、${\displaystyle e_{1}=\{e_{2}\}}$そして${\displaystyle e_{2}=\{e_{1}\}}$このループは無限に再帰的であるため、エッジである集合は基礎公理に違反します。^{[ 48 ]}特に、このようなハイパーグラフには集合メンバーシップの推移閉包がありません。このような構造は最初は奇妙に見えるかもしれませんが、それらのレヴィグラフの同等の一般化はもはや二部グラフではなく、単なる一般的な有向グラフであることに注目すれば、容易に理解できます。^{[ 55 ]}

このようなハイパーグラフの一般化接続行列は、定義により、頂点の総数と辺の総数に等しいランクを持つ正方行列である。^{[ 56 ]}したがって、上記の例では、接続行列は単純に

${\displaystyle \left[{\begin{matrix}0&1\\1&0\end{matrix}}\right]}$。

• ベルジュ、クロード（1984）。ハイパーグラフ：有限集合の組み合わせ論。エルゼビア。ISBN 978-0-08-088023-5。
• Berge, C.; Ray-Chaudhuri, D. (2006).ハイパーグラフセミナー：オハイオ州立大学、1972年。数学講義ノート。第 411巻。Springer。ISBN 978-3-540-37803-7。
• 「ハイパーグラフ」、数学百科事典、EMS Press、2001年 [1994年]
• ブレット、アラン（2013）。ハイパーグラフ理論入門。シュプリンガー。ISBN 978-3-319-00080-0。
• Voloshin, Vitaly I. (2002). Coloring Mixed Hypergraphs: Theory, Algorithms and Applications: Theory, Algorithms, and Applications . Fields Institute Monographs. Vol.  17. American Mathematical Society. ISBN 978-0-8218-2812-0。
• Voloshin, Vitaly I. (2009).グラフ理論とハイパーグラフ理論入門. Nova Science. ISBN 978-1-61470-112-5。
• この記事は、PlanetMathのhypergraphの素材を組み込んでおり、Creative Commons Attribution-Share-Alike Licenseの下でライセンスされています。

• PAOHVis：動的ハイパーグラフを可視化するためのオープンソースのPAOHVisシステム。