形式陈述

超图是二元组 $H=(V,E)$$H=(V,E)$，其中 $V$$V$ 是顶点集，$E\subseteq\mathcal P(V)$$E\subseteq \mathcal{P}(V)$ 是超边族；每条超边可包含任意数量顶点。若每条边恰含 $r$$r$ 个顶点，称 $r$$r$-一致超图；普通简单图正是 $2$$2$-一致超图。顶点 $v$$v$ 的度是包含 $v$$v$ 的超边数。若超边族允许重复，则得到多重超图；是否允许空边或单点边取决于约定。对有限超图，有握手式

$$ \sum_{v\in V}\deg(v)=\sum_{e\in E}|e|. $$$$\sum _{v\in V}\mathrm{deg}(v)=\sum _{e\in E}|e|.$$

直觉

图的一条边只连接一对顶点，超边则能直接表达一个多元关系。它是把成对关系推广到集合关系的最小结构。

例子与边界

集合系统可直接视为超图：顶点是底集元素，子集是超边。$3$$3$-SAT 实例可产生每个子句对应一条变量超边，但符号信息还需额外标签。超图中的“路径”“连通”“匹配”和“着色”有多种不完全等价定义，使用时必须说明。若把 $E$$E$ 定义为集合，则相同超边只出现一次；要计重数需用多重集或带索引族。超图的关联矩阵以顶点为行、超边为列，不能与普通图邻接矩阵简单混同。普通图嵌入超图时通常排除环，因为二元超边是集合而非有序对。

推论与应用

超图建模数据库关系、组合设计、约束满足、网络高阶相互作用和概率方法中的集合系统。

参考资料

• Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016，Ch. 1, hypergraphs as set systems and uniformity。
• Béla Bollobás, Modern Graph Theory, Springer, 1998，Ch. I, hypergraphs and incidence structures。