超图

普通图记录成对关系，超图保留“哪些对象属于同一组”。一个三人群聊和三个两人群聊产生相同的两两相识关系，却是不同的超图。把每条超边替换成它所含顶点之间的完全图，会丢失这种分组信息。

超边并不天然表示冲突；它也可以表示合作、共同出现或一项约束的作用范围。只有先规定“某个选集不得完整包含一条超边”，超边才成为禁止组合。此时禁止同时选择 $a,b,c$ 并不禁止同时选择 $a,b$，而将三元边替换成三条冲突边会错误地加强约束。

取 $V=\{a,b,c,d\}$，$E=\{\{a,b,c\},\{b,d\},\{d\}\}$。按此顺序排列行列，关联矩阵为

四个顶点的度为 $(1,2,1,2)$，和为 $6$；三条边的大小为 $(3,2,1)$，和也为 $6$。这不是一致超图。若加入空边，会多出一个全零列，却不改变任何顶点度数。

课程安排中，若三门课共同需求超过资源容量、任意两门却不超限，可以用超边 $\{a,b,c\}$ 记录这一最小禁止组合。$3$-SAT 子句也可用变量集合记录其作用范围，但超图本身不能区分 $x\vee y\vee z$ 与 $\mathrm{\neg }x\vee y\vee z$，还需要文字的正负标签。

若不同群聊恰好具有相同成员，集合模型会把它们合并。需要保留身份时，应改用带索引的超边族 $(e_i{)}_{i\in I}$，即多重超图。类似地，普通图的自环不能通过二元子集表达；单点超边的度数贡献是 $1$，也不同于图论自环贡献的 $2$。

超图的路径、圈与着色有不同惯例。例如“每条边不能全同色”与“每条边内部两两异色”是不同要求。使用这些词时需给出规则，不能只沿用普通图术语。

关联矩阵可改画为二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。：一侧是原顶点，另一侧是超边，包含关系成为普通边。这种关联表示保留了超边身份；只连接原顶点的两两投影则通常不能恢复超图。

组合设计把区组视作超边，数据库连接把关系所涉及的属性集视作超边。研究超图着色时，概率方法公理库概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。和Lovász 局部引理公理库Lovász 局部引理Lovász local lemma当坏事件概率小且依赖稀疏时，所有坏事件同时不发生的概率为正。可用于证明不存在单色超边的着色存在；具体结论还取决于边大小与相互依赖程度。

在最坏情形最优连接公理库最坏情形最优连接Worst-case optimal joins · WCOJ从AGM熵界到一般NPRR锚关系递归，完整核算三角形和四三元表实例的枚举与索引成本。中，给超边分配非负权重，使每个属性被覆盖至少一次，就能证明连接输出的乘积上界。不同关系即使属性集相同，也保留各自索引与大小；这正是带索引超边族比简单集合模型更合适的场景。