ハイパーグラフの例:
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}
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 は、その真部分集合として横断と呼べるものがない場合に「最小」であるという。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}
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 の本文を含む
