ハイパーグラフ

ハイパーグラフとは

ハイパーグラフは、数学におけるグラフの概念を一般化したものです。通常のグラフでは、エッジ（枝）は2つのノード（頂点）を結びますが、ハイパーグラフでは、エッジは任意個数のノードを連結できます。このエッジはハイパーエッジと呼ばれます。

定義

ハイパーグラフは、ノードの集合 \( X \) と、ハイパーエッジの集合 \( E \) の対 \( (X, E) \) で表されます。

\( X \) は、ノード（頂点）の集合です。
\( E \) は、\( X \) の空でない部分集合の集合で、ハイパーエッジの集合です。つまり、各ハイパーエッジは、1つ以上のノードを含む集合となります。

グラフとの違い

通常のグラフのエッジは2つのノードを結びますが、ハイパーグラフのハイパーエッジは任意の数のノードを連結できる点が大きく異なります。そのため、ハイパーグラフはグラフよりも複雑な関係性を表現できます。

図示の難しさ

ハイパーグラフは、複数のノードが1つのエッジに接続されるため、通常のグラフのように図示するのが難しい場合があります。そのため、集合論の用語を用いて表現されることが多いです。

ハイパーグラフの性質

グラフ理論における多くの定理は、ハイパーグラフにも適用できます。以下にいくつかの例を挙げます。

ラムゼーの定理

ラムゼーの定理は、ハイパーグラフにおいても成立する重要な定理です。

対称性

グラフの対称性に関する研究は、ハイパーグラフにも拡張して適用できます。

準同型と自己同型

準同型：あるハイパーグラフの頂点集合から別のハイパーグラフへの写像で、エッジが別のエッジに対応する場合を指します。
同型：双方向に準同型である場合を指します。
自己同型：頂点集合がラベルを付け直した頂点集合と準同型である場合を指します。

ハイパーグラフ H の自己同型群 Aut(H) は、合成演算に関して群をなします。

横断と横断ハイパーグラフ

ハイパーグラフ \( H = (X, E) \) の横断（またはヒッティングセット）\( T \) は、全てのハイパーエッジと共通のノードを持つようなノードの集合 \( T \subseteq X \) です。

最小横断：真部分集合に横断となるものが存在しない横断を指します。
横断ハイパーグラフ：\( H \) の全最小横断からなるハイパーグラフを指します。

横断ハイパーグラフの計算は、機械学習やゲーム理論、データベースのインデックス付け、充足可能性問題、最適化問題など、様々な分野に応用されています。

k-一様ハイパーグラフとk-正則ハイパーグラフ

k-一様（k-uniform）ハイパーグラフ：全てのハイパーエッジが k 個のノードを持つハイパーグラフを指します。グラフは2-一様ハイパーグラフの一例です。
k-正則（k-regular）ハイパーグラフ：全てのノードの次数（そのノードが含まれるエッジの数）が k であるハイパーグラフを指します。

接続行列と双対ハイパーグラフ

ハイパーグラフは、接続行列を用いて表現できます。\( n \times m \) の接続行列 \( A = (a_{ij}) \) において、ノード \( v_i \) がエッジ \( e_j \) に含まれる場合、\( a_{ij} = 1 \) となり、含まれない場合は \( a_{ij} = 0 \) となります。


接続行列の転置行列 \( A^t \) を用いて、ハイパーグラフ \( H \) の双対ハイパーグラフ \( H^ = (V^, E^) \) を定義できます。

\( V^ \) は \( m \) 個の要素を持つ集合です。
\( E^ \) は \( n \) 個の \( V^ \) の部分集合からなる集合です。

双対ハイパーグラフは、元のハイパーグラフの視点を変えることで、新たな発見をもたらすことがあります。例えば、一様なハイパーグラフの双対は正則であり、逆もまた真です。

ハイパーグラフの彩色

ハイパーグラフの彩色とは、以下の条件を満たすようにノードに色を割り当てることです。

ハイパーグラフ \( H = (V, E) \) において、\( V \) の要素数を \( n \) とします。
色集合 \( C = \{c_1, c_2, ..., c_n\} \) を用いて、各ノードに色を割り当てます。
ハイパーエッジ \( e \in E \) において、\( |e| > 1 \) の場合、\( e \) 内の任意の2つのノード \( v_i, v_j \) に対して、割り当てられた色 \( c_i \) と \( c_j \) が異なる必要があります。

この条件を満たすように色を割り当てることで、ハイパーグラフの構造を解析することができます。

関連項目

素集合
集合の分割
有限交叉性
頂点被覆



この文章は、クリエイティブ・コモンズ・ライセンス 表示-継承 3.0 非移植のもとで提供されているオンライン数学辞典『PlanetMath』の項目hypergraphの本文を参考に作成されました。

もう一度検索