超图

普通边只能表达成对关系，超边则把“一组对象共同触发约束”保留为不可拆的整体。把三元约束拆成三条普通边通常会变强：要求三者不能同时出现，不等于要求任意两者都不能同时出现。超图因此是集合系统本身，而不仅是画法更复杂的图。

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

在课程安排中，超边 $\{a,b,c\}$ 可以表示三门课不能同时占用同一组合资源，但允许其中任意两门并行；将它替成三角形会错误地禁止所有两两并行。$k$-一致超图要求每条超边恰有 $k$ 个顶点，普通简单图正是 $2$-一致情形。若允许重复超边或有序超边，则需多重超图或有向超图的额外结构。

集合公理库集合Set由成员完全决定的数学对象；成员关系给出集合的内容，额外结构须另行指定。上的超边族推广图公理库有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。，一致超图中的独立集、匹配和着色延伸了对应图参数。组合设计把区组直接视作超边，概率方法公理库概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。和Lovász 局部引理公理库Lovász 局部引理Lovász local lemma当坏事件概率小且依赖稀疏时，所有坏事件同时不发生的概率为正。则常用来证明稀疏超图可二染色；数据库连接、SAT 子句与高阶网络也依赖“约束属于整组”而非成对分解的表达力。