超圖

在數學中，超圖（Hypergraph）是一種廣義上的圖。不同於普通圖的一條邊只能連接兩個頂點，超圖的一條邊可以連接任意數量的頂點。理論上，超圖${\displaystyle H}$是一個集合組${\displaystyle H=(X,E)}$，其中${\displaystyle X}$是一個有限集合，該集合的元素被稱為節點或頂點，${\displaystyle E}$是${\displaystyle X}$的非空子集的集合，被稱為超邊或連接。因此，${\displaystyle E}$是${\displaystyle {\mathcal {P}}(X)\setminus \{\emptyset \}}$的一個子集，其中${\displaystyle {\mathcal {P}}(X)}$是${\displaystyle X}$的冪集。

一個超圖的例子，圖示中包含了 ${\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}\}\}}$.

儘管圖的邊各有一對節點，而超邊是節點的任意集合，因而能包含任意數量的節點。然而，通常的研究更傾向於每個超邊連接的節點數相同的超圖：k-均勻超圖（每個超邊都連接了k個節點）。因此，2-均勻超圖就是圖，3-均勻超圖就是三元組的集合，依此類推。

性質

應用

無向超圖在建模可滿足性問題、數據庫、機器學習和斯坦納樹問題等方面非常有用。它們作為數據模型和分類器正則化(數學)被廣泛應用於機器學習任務中。應用包括推薦系統、圖像檢索和生物信息學。典型的超圖學習技術包括用超圖拉普拉斯擴展譜圖理論的超圖譜聚類，以及引入額外超圖結構代價來限制學習結果的超圖半監督學習。對於大規模超圖，還可以使用Apache Spark構建分佈式框架。

有向超圖可用於對包括電話應用程式、檢測洗錢、運籌學和運輸規劃在內的事物進行建模。它們也可以用來模擬霍恩可滿足性。

參考

• Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", Lecture Notes in Mathematics 411 Springer-Verlag
• 本條目含有來自PlanetMath《Hypergraph》的內容，版權遵守共享創意協議：署名-相同方式共享協議。
• Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". Nova Science Publishers, Inc., 2009.