ハイパーグラフ

Generalization of graph theory

とを持つ無向ハイパーグラフの例。このハイパーグラフの位数は7、サイズは4です。ここでは、辺は2つの頂点だけでなく複数の頂点を接続し、色で表されます ${\displaystyle X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}}$ ${\displaystyle E=\{e_{1},e_{2},e_{3},e_{4}\}=}$ ${\displaystyle \{\{v_{1},v_{2},v_{3}\},}$ ${\displaystyle \{v_{2},v_{3}\},}$ ${\displaystyle \{v_{3},v_{5},v_{6}\},}$ ${\displaystyle \{v_{4}\}\}}$

上図に示したハイパーグラフの代替表現で、PAOHと呼ばれます。^[1]辺は頂点を結ぶ垂直線です。V7は孤立した頂点です。頂点は左揃えで並んでいます。右側の凡例は辺の名前を示しています。

有向ハイパーグラフの例。 ${\displaystyle X=\{1,2,3,4,5,6\}}$ ${\displaystyle E=\{a_{1},a_{2},a_{3},a_{4},a_{5}\}=}$ ${\displaystyle \{(\{1\},\{2\}),}$ ${\displaystyle (\{2\},\{3\}),}$ ${\displaystyle (\{3\},\{1\}),}$ ${\displaystyle (\{2,3\},\{4,5\}),}$ ${\displaystyle (\{3,5\},\{6\})\}}$

数学において、ハイパーグラフとは、辺が任意の数の頂点を結べるグラフの一般化です。対照的に、通常のグラフでは、辺は正確に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|)}$

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

無向ハイパーグラフ とは、辺が2つの頂点だけでなく任意の数の頂点を接続する無向グラフです。^[2]無向ハイパーグラフは、集合系または普遍集合から抽出された集合の族とも呼ばれます。 ${\displaystyle (X,E)}$

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

ハイパーグラフには様々な名称があります。計算幾何学では、無向ハイパーグラフは値域空間と呼ばれることもあり、その場合ハイパーエッジは値域と呼ばれます。^[3]協力ゲーム理論 では、ハイパーグラフは単純ゲーム（投票ゲーム）と呼ばれ、この概念は社会選択理論における問題を解く際に適用されています。文献によっては、エッジはハイパーリンクまたはコネクタと呼ばれることもあります。^[4]

ハイパーグラフのコレクションは、ハイパーグラフ準同型を射として持つカテゴリです。

応用

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

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

グラフからの概念の一般化

グラフに関する多くの定理や概念はハイパーグラフにも当てはまります。特に次のようになります。

• ハイパーグラフにおけるマッチング;
• ハイパーグラフの頂点カバー（横断的とも呼ばれる）
• ハイパーグラフの線グラフ。
• ハイパーグラフ文法- 一連の置換ルールを使用してハイパーグラフのクラスを拡張することによって作成されます。
• ラムゼーの定理;
• エルデシュ・コー・ラドの定理;
• 一様超グラフ上のKruskal-Katona定理;
• ハイパーグラフに関するホール型定理。

有向ハイパーグラフでは、推移閉包と最短経路問題が存在します。^[18]

ハイパーグラフの描画

この回路図は、4つの頂点（白い長方形と円盤で描かれている）が木として描かれた3つのハイパーエッジで接続されているハイパーグラフの描画として解釈できます

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

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

4次のベン図。15個の頂点（15個の色付き領域）と4個のハイパーエッジ（4個の楕円）を持つハイパーグラフの分割図として解釈できます。

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

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

ハイパーグラフ彩色

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

k色までの彩色が存在するハイパーグラフはk-彩色可能と呼ばれます。2-彩色可能なハイパーグラフはまさに二部ハイパーグラフです。

古典的なハイパーグラフ彩色には多くの一般化がある。その一つは、単色エッジが許容される、いわゆる混合ハイパーグラフ彩色である。混合ハイパーグラフの中には、任意の色数で彩色不可能なものがある。彩色不可能性の一般的な基準は不明である。混合ハイパーグラフが彩色可能である場合、使用される色の最小数と最大数は、それぞれ下限彩色数と上限彩色数と呼ばれる。^[28]

ハイパーグラフの特性

ハイパーグラフには、次のような様々な特性があります。

• 空- 辺がない
• 単純ではない (または 複数) - ループ (単一の頂点を持つハイパーエッジ) または繰り返しエッジがあり、同じ頂点セットを含む 2 つ以上のエッジが存在する可能性があることを意味します。
• シンプル- ループや繰り返しエッジはありません。
• ${\displaystyle d}$-正則- すべての頂点は次数 を持ち、つまり、正確にハイパーエッジに含まれます。 ${\displaystyle d}$ ${\displaystyle d}$
• 2色可能- 頂点は2つのクラスUとVに分割でき、その場合、濃度が2以上の各ハイパーエッジは両方のクラスから少なくとも1つの頂点を含む。別名、性質B。
  • 2 つのより強力な特性は、二部構成とバランスです。
• ${\displaystyle k}$-uniform - 各ハイパーエッジには正確に頂点が含まれます。 ${\displaystyle k}$
• ${\displaystyle k}$-partite - 頂点は部分に分割され、各ハイパーエッジには各タイプの頂点が 1 つだけ含まれます。 ${\displaystyle k}$
  • すべての- 部ハイパーグラフ ( の場合) は- 一様かつ二部 (2 色可能) です。 ${\displaystyle k}$ ${\displaystyle k\geq 2}$ ${\displaystyle k}$
• 縮約：^[29]いかなるハイパーエッジも他のハイパーエッジの厳密な部分集合ではない。つまり、すべてのハイパーエッジは包含に関して最大​​である。ハイパーグラフの縮約とは、他のハイパーエッジに含まれるすべてのハイパーエッジを削除することによって得られる縮約ハイパーグラフである。
• 下向き閉- 無向ハイパーグラフの辺のすべての部分集合もハイパーエッジである。下向き閉ハイパーグラフは通常、抽象単体複体と呼ばれる。すべてのハイパーエッジの濃度が1でない限り、一般的には縮約されない。
  • 増大特性を持つ抽象単体複体はマトロイドと呼ばれます。
• 層状：任意の2つのハイパーエッジは、互いに素であるか、一方が他方に含まれるかのいずれかである。言い換えれば、ハイパーエッジの集合は層状集合族を形成する。

関連するハイパーグラフ

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

頂点から成るハイパーグラフとする ${\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への制限がある。^{[30] : 468}

サブハイパーグラフの拡張とは、そのハイパーエッジがサブハイパーグラフに部分的に含まれ、その拡張に完全に含まれるようなハイパーグラフのことである。正式には ${\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 }$

部分ハイパーグラフは、いくつかのエッジが削除されたハイパーグラフである。^{[30] : 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のホストグラフであるとは、 HのすべてのハイパーエッジがG に連結サブグラフを誘導することを意味する。連結されていないハイパーグラフ H の場合、 Gの連結成分とHの連結成分の間に一対一の関係があり、 Gの各連結成分G'が対応するH'のホストとなることを意味する。

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

接続行列

ととする。すべてのハイパーグラフには接続行列がある ${\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.}$

接続行列の転置は 、の双対と呼ばれるハイパーグラフを定義します。ここで、はm要素の集合であり、はのサブセットのn要素の集合です。 およびの場合、かつ の場合に限ります。 ${\displaystyle I^{t}}$ ${\displaystyle H^{*}=(V^{*},\ E^{*})}$ ${\displaystyle H}$ ${\displaystyle V^{*}}$ ${\displaystyle E^{*}}$ ${\displaystyle V^{*}}$ ${\displaystyle v_{j}^{*}\in V^{*}}$ ${\displaystyle e_{i}^{*}\in E^{*},~v_{j}^{*}\in e_{i}^{*}}$ ${\displaystyle b_{ij}=1}$

有向ハイパーグラフの場合、各ハイパーエッジのヘッドとテールはそれぞれとで表される。^[19]ここで ${\displaystyle e_{j}}$ ${\displaystyle H(e_{j})}$ ${\displaystyle T(e_{j})}$ ${\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.}$

インシデンスグラフ

ハイパーグラフHは、​​次のように二部グラフ BGで表すことができます。集合XとEはBGの部分であり、頂点x ₁がHの辺e ₁に含まれる場合のみ、 ( x ₁ , e _{1 )は辺で接続されます}

逆に、固定部分を持ち、第2部分に未接続のノードを持たない任意の二部グラフは、上述のようなハイパーグラフを表します。この二部グラフは接続グラフとも呼ばれます。

隣接行列

ハイパーグラフの隣接行列は、グラフの隣接行列から類似したものを描くことができます。グラフの場合、隣接行列は頂点のペアが隣接しているかどうかを示す正方行列です。同様に、ハイパーエッジが実数の重みを 持つ一般的なハイパーグラフの隣接行列を定義できます ${\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つしか存在しませんが、ハイパーグラフでは、サイクルの自然な非等価な定義が複数存在します。グラフの場合を考えると、それらは通常のサイクルの概念に帰着します

ベルジュサイクル

サイクルの最初の概念は、クロード・ベルジュによって導入されました。^[31]ハイパーグラフにおけるベルジュサイクルは、異なる頂点と辺が交互に並ぶシーケンスであり、それぞれに対してと が両方とも となります（添え字は を法として取られます）。 ${\displaystyle (v_{1},e_{1},\dots ,v_{n},e_{n})}$ ${\displaystyle n\geq 2}$ ${\displaystyle v_{i},v_{i+1}}$ ${\displaystyle e_{i}}$ ${\displaystyle i\in [n]}$ ${\displaystyle n}$

この定義によれば、ハイパーグラフが非巡回的であるためには、その接続グラフ（上記で定義した二部グラフ）が非巡回的である必要があります。したがって、接続グラフを探索することで、 ベルゲ巡回性は明らかに線形時間で検証できます。

タイトサイクル

この定義は、すべてのハイパーエッジのサイズが である -一様ハイパーグラフに特に使用されます。ハイパーグラフの長さ のタイトサイクルとは、連続するすべての-組（ を法とするインデックス）が におけるハイパーエッジを形成するような、異なる頂点の列です。この概念は、Katona と Kierstead ^[32]によって導入され、それ以来、特に極限組合せ論におけるハミルトン性の研究において、かなりの注目を集めています。^{[33] [34]} ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle H}$ ${\displaystyle v_{1},\dots ,v_{n}}$ ${\displaystyle k}$ ${\displaystyle \{v_{i},\dots ,v_{i+k-1}\}}$ ${\displaystyle n}$ ${\displaystyle H}$

Rödl、Szemerédi、およびRucińskiは、すべての頂点の-部分集合が少なくとも 個の超辺に含まれるようなすべての -頂点 -一様超グラフには、ハミルトン閉路が含まれることを示した。これは、グラフにおけるハミルトン閉路に関する有名なディラックの定理の近似的な超グラフ拡張に相当する。 ^[35] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle H}$ ${\displaystyle (k-1)}$ ${\displaystyle n/2+o(n)}$

（タイトに）非巡回な -一様ハイパーグラフにおけるハイパーエッジの最大数は未だ不明である。SudakovとTomon ^[36]によって得られた最もよく知られている上限は、少なくとも 個のハイパーエッジを持つすべての-頂点 -一様ハイパーグラフには必ずタイトサイクルが含まれることを示している。この上限は誤差項を除いて最適である。 ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n^{k-1+o(1)}}$ ${\displaystyle o(1)}$

-サイクルはタイトサイクルの概念を一般化したものです。これは、頂点とハイパーエッジのシーケンスで構成され、各ハイパーエッジはシーケンス内の連続する頂点から成り、任意の に対して成り立ちます。-サイクルのすべてのエッジには、前のエッジに含まれていない頂点がちょうど 個含まれているため、は で割り切れる必要があります。はタイトサイクルの定義を復元することに注意してください。 ${\displaystyle l}$ ${\displaystyle v_{1},\dots ,v_{n}}$ ${\displaystyle e_{1},\dots ,e_{t}}$ ${\displaystyle e_{i}}$ ${\displaystyle k}$ ${\displaystyle |e_{i}\cap e_{i+1}|=l}$ ${\displaystyle 1\leq i\leq t}$ ${\displaystyle l}$ ${\displaystyle k-l}$ ${\displaystyle n}$ ${\displaystyle k-l}$ ${\displaystyle l=k-1}$

α-非巡回性

ベルジュ非巡回性の定義は非常に制限的であるように思えるかもしれません。例えば、ハイパーグラフが頂点のペアとハイパーエッジのペアを持ち、かつとなる場合、それはベルジュ巡回性です ${\displaystyle v\neq v'}$ ${\displaystyle f\neq f'}$ ${\displaystyle v,v'\in f}$ ${\displaystyle v,v'\in f'}$

我々はハイパーグラフの非巡回性というより弱い概念を定義することができ、これは^[6]後に α-非巡回性と呼ばれる。この非巡回性の概念は、ハイパーグラフが共形であること（主グラフのすべてのクリークが何らかのハイパーエッジで覆われている）およびその主グラフが弦であることと同等である。また、これは、 earsの一般化された定義を使用してハイパーエッジを削除する合流反復プロセスであるGYO アルゴリズム^{[37] [38]}（グラハムのアルゴリズムとしても知られる）による空グラフへの還元可能性と同等である。データベース理論の領域では、データベーススキーマの基盤となるハイパーグラフが α-非巡回である場合に、そのデータベーススキーマが特定の望ましい特性を持つことが知られている。^{[39]さらに、α-非巡回性は}、一階述語論理の保護されたフラグメントの表現力にも関連している。

ハイパーグラフがα非巡回であるかどうかは線形時間でテストできる。 ^[40]

α-非巡回性には、α-巡回ハイパーグラフにハイパーエッジを追加すると、α-非巡回になる可能性があるという直感に反する特性があることに注意する必要がある (たとえば、ハイパーグラフのすべての頂点を含むハイパーエッジを追加すると、常に α-非巡回になる)。 この認識された欠点に一部動機付けられて、ロナルド・フェイギン^[41]は、より強い概念である β-非巡回性と γ-非巡回性を定義した。 β-非巡回性は、ハイパーグラフのすべてのサブハイパーグラフが α-非巡回であるという要件であると述べることができ、これは^[41]グラハムによる以前の定義^[38]と同等である。 γ-非巡回性の概念は、データベーススキーマのいくつかの望ましい特性と同等のより制限的な条件であり、バッハマン図に関連している。 β-非巡回性と γ-非巡回性はどちらも多項式時間でテストできる。

これら4つの非巡回性の概念は互いに比較可能である。γ-非巡回性はβ-非巡回性を、β-非巡回性はα-非巡回性をそれぞれ含意する。さらに、ベルゲ-非巡回性はこれらすべてを含意する。逆の含意は、ベルゲの含意を含め、どれも成立しない。言い換えれば、これら4つの概念は互いに異なる。^[41]

同型性、対称性、そして等価性

ハイパーグラフ準同型性は、各エッジが他の 1 つのエッジにマッピングされる、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 ) と表記されます。

例

エッジを持つハイパーグラフを考える ${\displaystyle H}$

${\displaystyle H=\lbrace e_{1}=\lbrace a,b\rbrace ,e_{2}=\lbrace b,c\rbrace ,e_{3}=\lbrace c,d\rbrace ,e_{4}=\lbrace d,a\rbrace ,e_{5}=\lbrace b,d\rbrace ,e_{6}=\lbrace a,c\rbrace \rbrace }$

そして

${\displaystyle G=\lbrace f_{1}=\lbrace \alpha ,\beta \rbrace ,f_{2}=\lbrace \beta ,\gamma \rbrace ,f_{3}=\lbrace \gamma ,\delta \rbrace ,f_{4}=\lbrace \delta ,\alpha \rbrace ,f_{5}=\lbrace \alpha ,\gamma \rbrace ,f_{6}=\lbrace \beta ,\delta \rbrace \rbrace }$

すると、明らかにとは（ などと）同型であるが、強同型ではない。したがって、例えば では、頂点 は辺1、4、6と交わるので、 ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle \phi (a)=\alpha }$ ${\displaystyle H}$ ${\displaystyle a}$

${\displaystyle e_{1}\cap e_{4}\cap e_{6}=\lbrace a\rbrace }$

グラフには、辺1、4、6と交わる頂点は存在しません。 ${\displaystyle G}$

${\displaystyle f_{1}\cap f_{4}\cap f_{6}=\varnothing }$

この例では、とは同値であり、 の双対は強同型です。 ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H\equiv G}$ ${\displaystyle H^{*}\cong G^{*}}$

対称性

ザ ハイパーグラフのランクとは、ハイパーグラフ内の任意の辺の最大濃度です。すべての辺が同じ濃度k、ハイパーグラフは均一またはk-均一、k-ハイパーグラフ。グラフは単に 2-均一ハイパーグラフです ${\displaystyle r(H)}$ ${\displaystyle H}$

頂点vの次数d(v)は、頂点 vを含む辺の数です。すべての頂点の次数がkである場合、 Hはk 正則です。

一様ハイパーグラフの双対は正則であり、逆もまた同様である。

Hの2つの頂点xとy は、 となる自己同型が存在するとき対称的であるといわれます。2つの辺と は、となる自己同型が存在するとき対称的であるといわれます。 ${\displaystyle \phi (x)=y}$ ${\displaystyle e_{i}}$ ${\displaystyle e_{j}}$ ${\displaystyle \phi (e_{i})=e_{j}}$

ハイパーグラフのすべての頂点が対称である場合、そのハイパーグラフは頂点推移的（または頂点対称的）であると言われます。同様に、すべての辺が対称である場合、ハイパーグラフは辺推移的であると言われます。ハイパーグラフが辺対称性と頂点対称性の両方を満たす場合、そのハイパーグラフは単に推移的であると言えます。

ハイパーグラフの双対性のため、エッジ推移性の研究は頂点推移性の研究と同一です。

分割

^{E.ドーバー[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)}$

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

結果として、頂点推移的ではないエッジ推移的ハイパーグラフは二色可能です。

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

さらなる一般化

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

このようなハイパーグラフでは、集合の所属関係によって順序が与えられるが、この順序は推移的でないため、半順序でも事前順序でもない。 ^{[52] [53]}この一般化のレヴィグラフに対応するグラフは、有向非巡回グラフである。^[54]例えば、頂点集合が で辺が およびである一般化ハイパーグラフを考えてみよう。このとき、および であるにもかかわらず、 は真ではない。しかし、このようなハイパーグラフの集合の所属関係の推移閉包によって半順序が誘導され、ハイパーグラフが半順序集合に「平坦化」される。^[55] ${\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}}$

あるいは、辺が有向非巡回グラフとして順序付けられるという要件に関わらず、辺が他の辺を指すことを許可することもできる。^{[47] [48]}これにより、頂点をまったく含まないエッジループを持つグラフが可能になる。たとえば、2 つの辺と、および 0 個の頂点から構成される一般化ハイパーグラフ ( および )を考える。このループは無限再帰的であるため、辺である集合は基礎公理に違反する。^{[48]特に、このようなハイパーグラフには集合の帰属関係の推移閉包がない。 このような構造は最初は奇妙に思えるかもしれないが、それらのレヴィグラフの同等の一般化はもはや}二部ではなく、むしろある一般的な有向グラフであることに注目すれば、すぐに理解できる。^[56] ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{1}=\{e_{2}\}}$ ${\displaystyle e_{2}=\{e_{1}\}}$

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

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

参照

• BFグラフ – 有向ハイパーグラフの種類
• 組み合わせ設計 – 有限集合の対称的な配置
• 因子グラフ – 因数分解を表す関数グラフ
• Greedoid  – 貪欲最適化で使用される集合システム
• 発生構造 – 2種類のオブジェクトとそれらの関係の抽象的な数学的システム
• マルチグラフ – 2つの頂点間に複数の辺を持つグラフ
• Pシステム – 計算モデル
• 疎行列-ベクトル乗算 – 計算ルーチン
• ペトリネット – 分散システムを記述するモデルPages displaying short descriptions of redirect targets

注記

1. Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2020). 「並列集約順序付きハイパーグラフ可視化による動的ハイパーグラフの分析」(PDF) . IEEE Transactions on Visualization and Computer Graphics . 26 (1). IEEE: 12. doi :10.1109/TVCG.2019.2933196. eISSN  1941-0506. hdl :11586/518500. ISSN  1077-2626. PMID  31398121. S2CID 199518871. 2021年1月26日時点のオリジナルから アーカイブ(PDF) . 2020年9月8日閲覧
2. Ouvrard, Xavier (2020)、「ハイパーグラフ：入門とレビュー」、arXiv : 2002.05014 [cs.DM]。
3. ハウスラー、デイヴィッド；ウェルツル、エモ（1987）、「ε-ネットとシンプレックス範囲クエリ」、離散幾何学と計算幾何学、2（2）：127–151、doi：10.1007/BF02187876、MR  0884223。
4. パール、ジューディア（1984年）。『ヒューリスティックス：コンピュータによる問題解決のための知的探索戦略』アディソン・ウェスレー出版社。25ページ。ISBN 978-0-201-05594-8 2023年2月4日にオリジナルからアーカイブ。2021年6月12日閲覧
5. フェイジ, ウリエル; キム, ジョン・ハン; オフェク, エラン (2006). 「稠密ランダム3CNF式の非充足可能性の証拠」. 2006 第47回IEEEコンピュータサイエンス基礎シンポジウム (FOCS'06) . IEEE. pp.  497– 508. doi :10.1109/FOCS.2006.78. ISBN 0-7695-2720-5。
6. Beeri, C.; Fagin, R .; Maier, D.; Yannakakis, M. (1983). 「非巡回データベーススキームの望ましさについて」(PDF) . Journal of the ACM . 30 (3): 479– 513. doi :10.1145/2402.322389. S2CID 2418740. 2021年4月21日時点のオリジナルから アーカイブ(PDF) . 2021年1月3日閲覧
7. Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015). 「スケーラブルなハイパーグラフ学習と処理」. 2015 IEEE International Conference on Data Mining (PDF) . pp.  775– 780. doi :10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. S2CID 5130573. 2021年1月26日にオリジナルから アーカイブ（PDF） 。 2021年1月8日閲覧
8. Brazil, M; Zachariasen, M (2015). 「グラフとハイパーグラフにおけるシュタイナー木」.平面グラフにおける最適相互接続木. アルゴリズムと組合せ論. 第29巻. Springer. pp.  301– 317. doi :10.1007/978-3-319-13915-9_5. ISBN 978-3-319-13915-92021年1月29日にオリジナルからアーカイブ。2021年1月20日閲覧
9. 周, Dengyong; 黄, Jiayuan; ショルコフ, Bernhard (2006)、「ハイパーグラフによる学習：クラスタリング、分類、埋め込み」、ニューラル情報処理システムの進歩、MITプレス、pp.  1601–8、ISBN 978-0-262-25691-9、2021年10月22日にオリジナルからアーカイブ、 2021年7月24日閲覧
10. Ghoshal, Gourab; Zlatic, Vinko; Caldarelli, Guido; Newman, Mark EJ (2009)、「ランダムハイパーグラフとその応用」、Physical Review E、79 (6) 066118、arXiv : 0903.0419、Bibcode :2009PhRvE..79f6118G、doi :10.1103/PhysRevE.79.066118、PMID  19658575、S2CID  6391099
11. Tan, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, Can; He, Xiaofei (2011年10月)「ハイパーグラフモデルによる音楽推薦のための豊富なソーシャルメディア情報の利用」、ACM Transactions on Multimedia Computing, Communications, and Applications、7S (1)、Article 22、Bibcode :2011smma.book..213T、doi :10.1145/2037676.2037679、S2CID  432036
12. Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2013)、「画像検索のためのサンプリングを用いたハイパーグラフ」、パターン認識、44 ( 10– 11): 2255– 2262、doi :10.1016/j.patcog.2010.07.014
13. Patro, Rob; Kingsoford, Carl (2013)、「簡潔なネットワーク履歴推論によるタンパク質相互作用の予測」、Bioinformatics、29 ( 10– 11): 237– 246、doi :10.1093/bioinformatics/btt224、PMC 3694678、PMID  23812989 
14. Gao, Tue; Wang, Meng; Zha, Zheng-Jun; Shen, Jialie; Li, Xuelong; Wu, Xindong (2013), "Visual-textual joint relevance learning for tag-based social image search", IEEE Transactions on Image Processing , 22 (1): 363– 376, Bibcode :2013ITIP...22..363Y, doi :10.1109/tip.2012.2202676, PMID  22692911, S2CID  7432373, 2017年9月23日アーカイブ, 2017年9月22日取得
15. Tian, Ze; Hwang, TaeHyun; Kuang, Rui (2009)「事前知識を用いた遺伝子発現とアレイCGHデータの分類のためのハイパーグラフベース学習アルゴリズム」、Bioinformatics、25 (21): 2831– 2838、doi : 10.1093/bioinformatics/btp467、PMID  19648139
16. Goldstein, A. (1982). 「有向ハイパーグラフデータベース：市内回線電話設備のモデル」. Bell System Technical Journal . 61 (9): 2529–54 . doi :10.1002/j.1538-7305.1982.tb03439.x. S2CID  11290643.
17. Ranshous, Stephen; Joslyn, Cliff; Kreyling, Sean; Nowak, Kathleen; Samatova, Nagiza; West, Curtis; Winters, Samuel (2017). Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph (PDF) . Financial Cryptography and Data Security. Springer. doi :10.1007/978-3-319-70278-0_16. 2021年7月15日時点のオリジナルよりアーカイブ(PDF) 。 2021年1月20日閲覧。
18. Ausiello, Giorgio; Laura, Luigi (2017). 「有向ハイパーグラフ：入門と基本アルゴリズム - 概要」.理論計算機科学. 658 : 293–306 . doi : 10.1016/j.tcs.2016.03.016 .
19. Gallo, G.; Longo, G.; Pallottino, S.; Nguyen, S. (1993). 「有向ハイパーグラフとその応用」.離散応用数学. 42 ( 2–3 ): 177–201 . doi : 10.1016/0166-218X(93)90045-P .
20. Sander, G. (2003)、「直交ハイパーエッジを持つ有向ハイパーグラフのレイアウト」、Proc. 11th International Symposium on Graph Drawing (GD 2003)、Lecture Notes in Computer Science、vol. 2912、Springer、pp.  381– 6、ISBN 978-3-540-24595-7、2011年7月18日にオリジナルからアーカイブ、 2010年5月17日閲覧。
21. Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006)、「視認性向上のための直交ハイパーグラフ描画」(PDF)、Journal of Graph Algorithms and Applications、10 (2): 141– 157、doi : 10.7155/jgaa.00122、2011年7月18日にオリジナルからアーカイブ(PDF) 、 2010年5月17日取得。
22. Mäkinen, Erkki (1990)、「ハイパーグラフの描き方」、International Journal of Computer Mathematics、34 (3): 177– 185、doi :10.1080/00207169008803875。
23. Bertault, François; Eades, Peter (2001)、「サブセット標準におけるハイパーグラフの描画」、Graph Drawing、Lecture Notes in Computer Science、vol. 1984、Springer-Verlag、pp.  45– 76、doi : 10.1007/3-540-44541-2_15、ISBN 978-3-540-41554-1。
24. Naheed Anjum, Arafat; Bressan, Stéphane (2017)、「力指向配置によるハイパーグラフ描画」、データベースおよびエキスパートシステムアプリケーション、コンピュータサイエンスの講義ノート、第10439巻、Springer International Publishing、pp.  387– 394、doi :10.1007/978-3-319-64471-4_31、ISBN 978-3-319-64470-7。
25. カウフマン、マイケル；ヴァン・クレフェルト、マーク；スペックマン、ベッティーナ(2009)、「ハイパーグラフの細分描画」、グラフ描画、コンピュータサイエンスの講義ノート、第5417巻、シュプリンガー・フェアラーク、pp.  396– 407、doi : 10.1007/978-3-642-00219-9_39、ISBN 978-3-642-00218-2。
26. ジョンソン、デイビッド・S.；ポラック、HO（2006）、「ハイパーグラフの平面性とベン図の描画の複雑さ」、Journal of Graph Theory、11（3）：309–325、doi：10.1002/jgt.3190110306。
27. ケビン・ブチン、マーク・ファン・クレーフェルト、ヘンク・マイヤー、ベッティーナ・スペックマン、ケビン・フェルベーク (2010)、「ハイパーグラフの平面サポートについて」、グラフ描画、コンピュータサイエンス講義ノート、第5849巻、シュプリンガー・フェアラーク、  345～ 356ページ、doi : 10.1007/978-3-642-11805-0_33、ISBN 978-3-642-11804-3。
28. 「Vitaly Voloshin：Mixed Hypergraph Coloring Website」spectrum.troy.edu。2022年1月20日時点のオリジナルよりアーカイブ。2022年4月27日閲覧
29. Fagin, Ronald (1983-07-01). 「ハイパーグラフとリレーショナルデータベーススキームの非巡回性の度合い」. Journal of the ACM . 30 (3): 514– 550. doi : 10.1145/2402.322390 . ISSN  0004-5411.
30. ロヴァース、ラースロー;プラマー医学博士(1986 年)、『マッチング理論』、『離散数学年報』、第 1 巻。 29、北オランダ、ISBN 0-444-87916-1、MR  0859549
31. ベルゲ、クロード (1973).グラフとハイパーグラフ. アムステルダム: 北ホラント. ISBN 0-7204-2450-X。
32. カトナ、G. ;ハーステッド州キーアステッド (1999 年)。 「ハイパーグラフにおけるハミルトニアン連鎖」。グラフ理論ジャーナル。30 (3): 205–212 . doi :10.1002/(SICI)1097-0118(199903)30:3<205::AID-JGT5>3.0.CO;2-O。
33. Zhao, Y. (2016). 「ハイパーグラフにおけるディラック型問題に関する最近の進歩」.最近の組合せ論の動向. IMA数学とその応用巻. 第159巻. pp.  145– 165. arXiv : 1508.06170 . doi :10.1007/978-3-319-24298-9_6. ISBN 978-3-319-24296-5。
34. Kühn, D. ; Osthus, D. (2014). 「グラフとハイパーグラフにおけるハミルトンサイクル：極限的視点」(PDF) .国際数学者会議論文集: 381–406 . ISBN 978-89-6105-807-0。
35. Rödl, V. ; Szemerédi, E. ; Ruciński, A. (2008). 「k-一様ハイパーグラフに対する近似ディラック型定理」. Combinatorica . 28 (2): 229– 260. doi :10.1007/s00493-008-2295-z
36. Sudakov, B. ; Tomon, I. (2022). 「タイトサイクルの極値数」.国際数学研究通知. 2022 (13): 9663– 9684. arXiv : 2009.00528 . doi :10.1093/imrn/rnaa396.
37. Yu, CT; Özsoyoğlu, MZ (1979). 「分散クエリのツリークエリメンバーシップのためのアルゴリズム」(PDF) . COMPSAC 79. Proceedings. Computer Software and the IEEE Computer Society's Third International Applications Conference, 1979. pp.  306– 312. doi :10.1109/CMPSAC.1979.762509. オリジナル(PDF)から2018年9月2日にアーカイブ。 2018年9月2日閲覧。
38. Graham, MH (1979). 「普遍関係について」.技術報告書. トロント、オンタリオ州、カナダ: トロント大学.
39. Abiteboul, S. ; Hull, RB; Vianu, V. (1995). 『データベースの基礎』Addison-Wesley. ISBN 0-201-53771-0。
40. Tarjan, RE ; Yannakakis, M. (1984). 「グラフの弦性、ハイパーグラフの非巡回性をテストし、非巡回ハイパーグラフを選択的に削減するための単純な線形時間アルゴリズム」SIAM Journal on Computing . 13 (3): 566– 579. doi :10.1137/0213035.
41. Fagin, Ronald (1983). 「ハイパーグラフとリレーショナルデータベーススキームの非巡回度」Journal of the ACM . 30 (3): 514– 550. doi : 10.1145/2402.322390 . S2CID  597990.
42. Harary, F. (2018) [1969]. グラフ理論. CRC Press. p. 172. ISBN 978-0-429-96231-8。2023年2月4日にオリジナルからアーカイブ。 2021年6月12日閲覧。次に、エレイン・ドーバーの定理を述べま​​す。この定理の系は線対称グラフの性質を記述します。すべての線対称グラフは線正則であるという、明白でありながら重要な観察に留意してください
43. Karypis, G., Aggarwal, R., Kumar, V., Shekhar, S. (1999年3月)、「マルチレベルハイパーグラフパーティショニング：VLSIドメインへの応用」、IEEE Transactions on Very Large Scale Integration (VLSI) Systems、7 (1): 69– 79、CiteSeerX 10.1.1.553.2367、doi :10.1109/92.748202。 {{citation}}: CS1 maint: multiple names: authors list (link)
44. Hendrickson, B., Kolda, TG (2000)、「並列コンピューティングのためのグラフ分割モデル」、Parallel Computing（提出原稿）、26 (12): 1519– 1545、doi :10.1016/S0167-8191(00)00048-X、OSTI  4179、2021年1月26日のオリジナルからアーカイブ、 2018年10月13日取得。{{citation}}: CS1 maint: multiple names: authors list (link)
45. Catalyurek, UV; Aykanat, C. (1995).反復スパース行列–ベクトル積計算をマルチコンピュータにマッピングするためのハイパーグラフモデル. Proc. International Conference on Hi Performance Computing (HiPC'95).
46. Catalyurek, UV; Aykanat, C. (1999)、「並列スパース行列ベクトル乗算のためのハイパーグラフ分割ベースの分解」、IEEE Transactions on Parallel and Distributed Systems、10 (7): 673– 693、Bibcode :1999ITPDS..10..673C、CiteSeerX 10.1.1.67.2498、doi :10.1109/71.780863。 
47. 「A Gentle Introduction to Hypergraph Mathematics — HyperNetX 2.4.1 documentation」HyperNetX . 2021 . 2025年11月19日閲覧。{{cite web}}: CS1 maint: url-status (link)
48. Delvin (2020年4月). 「7. 非Well-Founded集合論」. pp.  143–184 . {{cite book}}:欠落または空|title=(ヘルプ)
49. Vepstas, Linas (2013年3月24日). 「なぜハイパーグラフなのか？」OpenCog Brainwave . 2025年11月19日閲覧。
50. バーツィンガー、ダニエル;エル・マーロウリー、ニコラス。クライスト、リンダ。ミルツォウ、ティルマン。ウェーバー、サイモン (2025)。 「幾何学的ハイパーグラフの認識の複雑さ」。グラフ理論の革新(フランス語)。2 : 157–190。土井:10.5802/igt.9。ISSN  3050-743X。
51. Kannin, Ravi; Hopcroft, John. 「第4章」(PDF) . 4 Random Graphs (PDF) . p. 16.{{cite book}}: CS1 maint: url-status (link)
52. Assari, Amir; Hosseinzadeh, Narges; Macpherson, Dugald (2023). 「集合同質ハイパーグラフ」. Journal of the London Mathematical Society . 108 (5): 1852– 1885. doi :10.1112/jlms.12796. ISSN  1469-7750.
53. Assari, Amir; Hosseinzadeh, Narges; Macpherson, Dugald (2023). 「集合同質ハイパーグラフ」. Journal of the London Mathematical Society . 108 (5): 1852– 1885. doi :10.1112/jlms.12796. ISSN  1469-7750.
54. Popp, Merten; Schlag, Sebastian; Schulz, Christian; Seemaier, Daniel (2020-10-15), Multilevel Acyclic Hypergraph Partitioning, arXiv, doi :10.48550/arXiv.2002.02962, arXiv:2002.02962 , 2025-11-19取得
55. Bushaw, Neal; Kettle, Nathan (2011年11月). 「多重パスと等分フォレストのTurán数」.組合せ論、確率、計算. 20 (6): 837– 853. doi :10.1017/S0963548311000460. ISSN  1469-2163.
56. Pisanski, T.; Boben, M.; Marušič, D.; Orbanić, A.; Graovac, A. (2004-01-28). 「10ケージと導出配置」.離散数学. 275 (1): 265– 276. doi :10.1016/S0012-365X(03)00110-9. ISSN  0012-365X.
57. Parui、Samiron (2024-09-24)、ハイパーグラフの出現行列について、arXiv、doi :10.48550/arXiv.2409.16055、arXiv: 2409.16055、2025-11-19取得

参考文献

• ベルジュ、クロード (1984). 『ハイパーグラフ：有限集合の組合せ論』エルゼビア. ISBN 978-0-08-088023-5。
• Berge, C.; Ray-Chaudhuri, D. (2006). ハイパーグラフセミナー：オハイオ州立大学、1972年。数学講義ノート。第411巻。Springer。ISBN 978-3-540-37803-7。
• 「ハイパーグラフ」、数学百科事典、EMSプレス、2001年 [1994]
• ブレット、アラン（2013年）『ハイパーグラフ理論入門』シュプリンガー、ISBN 978-3-319-00080-0。
• Voloshin, Vitaly I. (2002). 混合ハイパーグラフの着色：理論、アルゴリズム、および応用. フィールズ研究所モノグラフ. 第17巻. アメリカ数学会. ISBN 978-0-8218-2812-0。
• Voloshin, Vitaly I. (2009). グラフとハイパーグラフ理論入門. Nova Science. ISBN 978-1-61470-112-5。
• この記事には、クリエイティブ・コモンズ表示/継承ライセンスの下でライセンスされているPlanetMathのハイパーグラフの資料が組み込まれています

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Hypergraph&oldid=1323247313"