📂グラフ理論

ハイパーグラフの定義

定義

1. ある有限集合 $V \ne \emptyset$ をハイパーバーテックスセット^{hypervertex set}と呼びます。
2. ハイパーエッジ^hyperedgeとはハイパーバーテックスセットの部分集合を指し、ハイパーエッジの集合 $E$ をハイパーエッジセット^{hyperedge set}と呼びます。つまり、ハイパーエッジセットはハイパーバーテックスセットの冪集合の部分集合 $E \subset 2^{V}$ として定義されます。
3. ハイパーバーテックスとハイパーエッジのペア $G = (V, E)$ をハイパーグラフ^hypergraphと呼びます。

説明 ¹

簡単に言えば、ハイパーグラフとは「二者間の関係」に注目するグラフを超え、「多者間の関係」に関心を持つ概念です。例えば、人的ネットワークで $A$ と $B$、$B$ と $C$ は個人的に会いますが、$B$ がいない時には $A, C$ は会わなくても、$B$ がいる時には三人で会う場合、$A, B, C$ は基数 $3$ のハイパーエッジで結ばれているとみなされます。

ハイパーグラフはその自由な定義から分かるように、単にグラフの一般化というよりは、集合やデータといったものを新しく表現することに近いです。点と線で視覚化できるグラフと異なり、想像することから難しく、またその分、複雑な対象に対して新しい視点を提供することもあります。

当然、応用数学の分野で大きな注目を浴びていますが、ハイパーグラフ自体に関する理論的な研究はグラフ理論の枠組みをうまく保ちながら拡張するのが容易ではないと言われています。最も先に思い浮かぶ隣接行列のような概念でさえ、テンソルが必要になるほどですから、当然のことと言えるでしょう。