超图

超图（hypergraph）把图的一条边从连接两个顶点推广为包含一组顶点。它适合区分“一次多人共同关系”与“若干两两关系”。把一条三人关系换成三条普通边，虽然保留了谁与谁曾共同出现，却通常丢失原来的组别信息。

设 $V=\{a,b,c,d\}$，三个超边为 $e_1=\{a,b,c\}$、$e_2=\{b,c,d\}$、$e_3=\{d\}$。这描述两个三成员组和一个单成员组，不能把第一个组误读成三个互相独立的二成员组。

区域围住的是一条完整超边，重叠表示同一顶点属于多个组。

集合族与关联矩阵

有限超图可定义为 $H=(V,ℰ)$，其中 $ℰ\subseteq 2^V$。本文允许空超边、单元素超边与孤立顶点，并把重复超边合并；若需要区分相同成员的不同事件，应另设带标签的超边族。所有边大小均为 $r$ 时称为 $r$-均匀超图；无向简单图恰为二均匀情形。

关联矩阵 $B$ 以顶点为行、超边为列，$B_{ve}=1$ 当且仅当 $v\in e$。例中 $$B=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 1& 1& 0\\ 0& 1& 1\end{array}\right).$$ 列和给出超边大小 $3,3,1$；行和给出顶点度数 $1,2,2,2$。两种求和都在数关联对 $(v,e)$，所以对任意有限超图都有 $$\sum _{v\in V}\mathrm{deg}(v)=\sum _{e\in ℰ}|e|.$$ 这就是超图的握手恒等式，例中两边同为七。只有二均匀时右边才等于 $2|ℰ|$，普通图的度数和公式不能原样推广为所有超图的 $2m$。

关联图保留组别，二截面丢失组别

关联图是一个二部图，一侧是原顶点，另一侧是超边标签，$v$ 与 $e$ 相邻当且仅当 $v\in e$。从它的两个已注明角色的部就能逐列重建 $B$，因此能还原超图，包括哪些成员属于同一组。不能把超边侧节点当成新增的原顶点。

二截面则只保留原顶点，只要两点共同属于某条超边就连接普通边。矩阵上，$(B{B}^{𝖳}{)}_{uv}$ 在 $u\ne v$ 时数它们共同出现的超边数；取其是否大于零，就得到二截面的邻接关系。但一个超边 $\{a,b,c\}$，与三个超边 $\{a,b\},\{b,c\},\{c,a\}$ 的二截面都是三角形，原组别却不同。

两种不同超边族的两两投影相同，不能由三角形反推三人是否曾同时成组。

变式。 向例中加入孤立顶点 $z$，关联矩阵增加全零行；加入空超边则增加全零列。二截面看不到空超边；只保存非零关联列表也看不到未另行登记的孤立顶点。这说明使用数据结构前必须确定哪些退化对象需要保留。

击中集要求所选顶点与每条超边相交；超图匹配则选择两两不交的超边；这两个方向分别选顶点和选整条关系。超图的独立集通常指不完整包含任何超边的顶点集，例如在单个三元素超边上，任意二元素集都独立，但把该超边投影成三角形后，普通图独立集至多一个顶点。由投影进行计算时，必须检查想保留的是两两邻接还是整组约束。