ハイパーグラフのソースを表示

{{Expand English|Hypergraph|date=2024年5月}}
[[画像:Hypergraph.gif|right|frame|
ハイパーグラフの例: <math>X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}</math>,
<math>E= \{e_1,e_2,e_3,e_4\}</math>
<math>=\{\{v_1, v_2, v_3\}, \{v_2,v_3\},</math>
<math>\{v_3,v_5,v_6\},\{v_4\}\}</math>.
]]

'''ハイパーグラフ'''（{{lang-en-short|Hypergraph}}）とは、[[数学]]における[[グラフ理論|グラフ]]を一般化（拡張）したもので、エッジ（枝）が任意個数のノード（頂点）を連結できる。形式的には <math>(X,E)</math> という対で表され、<math>X</math> はノードあるいは頂点と呼ばれる要素の集合、<math>E</math> はハイパーエッジ（hyperedge）と呼ばれる <math>X</math> の空集合でない部分集合の集合である。したがって、<math>E</math> は <math>\mathcal{P}(X) \setminus \{\emptyset\}</math> の部分集合である。ただし、<math>\mathcal{P}(X)</math> は <math>X</math> の[[冪集合]]を表す。通常のグラフのエッジは2つのノードの対で表されるが、ハイパーエッジは任意のノードの集合で表され、任意個のノードを含む。

グラフとは異なり、ハイパーグラフは紙上に図示するのが困難である。そのため、[[グラフ理論]]のような図解をされることは少なく、[[集合論]]の用語で表される傾向がある。

== 概要 ==
グラフ理論の多くの[[定理]]はハイパーグラフでも成り立つ。典型例として[[ラムゼーの定理]]がある。グラフの対称性に関する研究もハイパーグラフに拡張して適用可能である。ハイパーグラフが[[準同型]]であるとは、あるハイパーグラフの頂点集合から別のそれへの写像があり、1つのエッジがもう一方のエッジに対応することを意味する。ハイパーグラフが[[同型]]であるとは、逆向きにも準同型である場合をいう。ハイパーグラフが[[自己同型]]であるとは、頂点集合がラベルを付け直した頂点集合と準同型であることをいう。ハイパーグラフの自己同型の集合 ''H'' (= (''X'',&nbsp;''E'')) は、合成について[[群 (数学)|群]]となり、ハイパーグラフの[[準同型|自己同型群]]と呼ばれ Aut(''H'') で表される。ハイパーグラフの集まりは、[[射 (圏論)|射]]としてのハイパーグラフ準同型の集まりからなる[[圏論|圏]]である。

ハイパーグラフ ''H'' = (''X'', ''E'') の「横断（transversal）」または「ヒッティングセット（hitting set）」<math>T\subseteq X</math> とは、どのエッジとも、積集合が空ではない集合のことである。すなわち、Tと各エッジの間に共通なノードが必ず存在する。横断 ''T'' は、その真部分集合として横断と呼べるものがない場合に「最小」であるという。''H'' の「横断ハイパーグラフ」は (''X'', ''F'') で表されるハイパーグラフであり、''F'' は ''H'' の全最小横断からなる。横断ハイパーグラフの計算は、[[機械学習]]などの[[計算機科学]]分野で応用されており、[[ゲーム理論]]、[[データベース]]のインデックス付け、[[充足可能性問題]]、[[最適化 (情報工学)|最適化]]などと関連する。

各エッジの濃度（元の個数）が ''k'' であるようなハイパーグラフを「k一様（k-uniform）」または「kハイパーグラフ（k-hypergraph）」と呼ぶ。グラフは2一様なハイパーグラフである。頂点 ''v'' の[[次数 (グラフ理論)|次数]] ''d(v)'' とは、その頂点が属するエッジの個数である。全ての頂点の次数が ''k'' であるハイパーグラフを「k正則（k-regular）」であるという。

ここで、<math>V = \{v_1, v_2, ~\ldots, ~ v_n\}</math> と <math>E = \{e_1, e_2, ~ \ldots, ~ e_m\}</math> があるとする。全てのハイパーグラフには <math>n \times m</math> の「[[接続行列]]」<math>A = (a_{ij})</math> があり、以下が成り立つ。

:<math>a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise} \end{matrix} \right.</math>

接続行列の[[転置行列]] <math>A^t</math> により定義されるハイパーグラフ <math>H^* = (V^*, E^*)</math> を <math>H</math> の「双対（dual）」であるといい、<math>V^*</math> は ''m'' 個の元からなる集合、<math>E^*</math> は ''n'' 個の <math>V^*</math> の部分集合からなる集合である。<math>v^*_j \in V^*</math> と <math>e^*_i \in E^*</math> について <math>a_{ij} = 1</math> であるときのみ <math>~ v^*_j \in e^*_i</math> である。一様なハイパーグラフの双対は、正則であり、逆も成り立つ。双対を考えることで新たな発見があることが多い。

== ハイパーグラフの彩色 ==
ハイパーグラフの[[グラフ彩色|彩色]]は次のように定義される。<math>H=(V,E)</math> というハイパーグラフは <math>\Vert V\Vert = n</math> であるとする。<math>C=\{c_1, c_2, \ldots, c_n\}</math> が <math>H</math> の妥当な彩色であるとは、全ての <math>e \in E, \vert e\vert > 1</math> について任意の頂点 <math>v_i, v_j \in e</math> で <math>c_i \neq c_j</math> となる場合のみを指す。

== 関連項目 ==
* [[素集合]]
* [[集合の分割]]
* [[有限交叉性]]
* [[頂点被覆]]

{{PlanetMath attribution|title=hypergraph|id=33508}}
{{Graph Theory-footer}}

{{Normdaten}}
{{DEFAULTSORT:はいはあくらふ}}
[[Category:集合論]]
[[Category:グラフ理論のグラフ]]
[[Category:組合せ論]]
[[Category:数学に関する記事]]

[[de:Graph (Graphentheorie)#Hypergraph]]