超图

在数学中，超图（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.