形式陈述
超图是二元组 ,其中 是顶点集, 是幂集理路幂集Power set把 A 的每一种子集选择提升为元素所得的集合,记作 P(A)。中的一个子集,称为超边族。一条超边本身就是一组顶点。本页采用有限集合理路有限集Finite set与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。模型,允许空边和单点边,但同一个子集只出现一次;具体问题若禁止这些边,应另外说明。
若每条超边都恰含 个顶点,称为 -一致超图。普通无自环简单图理路有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。正是 -一致超图,顶点集与每条二元边都原样保留。顶点 的度定义为
关联矩阵理路矩阵Matrix以有限行列集合为索引、取值于半环,并以中间指标求和定义乘法的函数。 以顶点为行、超边为列, 当且仅当 ,否则为零。这里行、列的标签也是表示的一部分:从第 列的非零行恰好恢复集合 ;全零列表示空边,全零行表示孤立顶点。简单模型的列不能重复,且最多有一个全零列。
为证明度数恒等式,取记录集合 ,按关联记录的双计数理路握手引理Handshaking lemma有限无向图中所有顶点度数之和等于边数的两倍。分别固定两个坐标。按顶点分组有 条记录,按超边分组有 条;每次分组都互斥且覆盖全部记录。因此逐行和逐列计算矩阵中 的总数,得到
特别地,-一致超图的度数和为 。
直觉
普通图记录成对关系,超图保留“哪些对象属于同一组”。一个三人群聊和三个两人群聊产生相同的两两相识关系,却是不同的超图。把每条超边替换成它所含顶点之间的全部二元边,会丢失这种分组信息。例如同一顶点集 上,超边族 与 的两两投影都是三角形,超边数却分别是一与三;从该投影不能逆推原分组。
超边并不天然表示冲突;它也可以表示合作、共同出现或一项约束的作用范围。只有先规定“某个选集不得完整包含一条超边”,超边才成为禁止组合。此时禁止同时选择 并不禁止同时选择 ,而将三元边替换成三条冲突边会错误地加强约束。
例子与边界
取 ,。按此顺序排列行列,关联矩阵为
四个顶点的度为 ,和为 ;三条边的大小为 ,和也为 。这不是一致超图。若加入空边,会多出一个全零列,却不改变任何顶点度数。
课程安排中,若三门课共同需求超过资源容量、任意两门却不超限,可以用超边 记录这一最小禁止组合。-SAT 子句也可用变量集合记录其作用范围,但超图本身不能区分 与 ,还需要文字的正负标签。
若不同群聊恰好具有相同成员,集合模型会把它们合并。需要保留身份时,应改用有限索引集 和带索引的超边族 ,即多重超图。其关联矩阵改以 为列标签,允许不同列有相同内容;度数按索引计为 ,总和仍等于 ,不能先把重复列去掉。例如两条不同编号的 给 各贡献二,而简单集合族只各贡献一。类似地,普通图的自环不能通过二元子集表达;单点超边的度数贡献是 ,也不同于图论自环贡献的 。
超图的路径、圈与着色有不同惯例。若把弱着色规定为每条边至少出现两种颜色,空边或单点边便使该要求不可满足;强着色只要求边内不同顶点两两异色,在这两类边上真空成立。例如“每条边不能全同色”与“每条边内部两两异色”是不同要求。使用这些词时需给出规则,不能只沿用普通图术语。
推论与应用
关联矩阵可改画为二分图理路二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。:取带不同标记的两侧 与 ,当且仅当 时连接 与 。从右侧顶点的左邻集去掉标记,就恢复每条超边;孤立的右侧顶点仍须保留,它对应空边。多重模型把右侧换为 ,相同邻集的不同右顶点仍表示不同的超边。保留两侧划分、标签和全部孤点时,这个往返才完整。与带标签关联矩阵的逐列恢复一样,编码与解码的两次复合分别还原各自输入,给出相应表示类之间的双射理路双射Bijective function · One-to-one correspondence让每个陪域元素恰有一个原像、等价于存在唯一双侧逆函数的映射。;把两侧或孤点忘掉,便是另一份数据。它与两两投影的关键差别,是超边本身也有一个可识别的位置。
组合设计把区组视作超边,数据库连接把关系所涉及的属性集视作超边。研究超图着色时,概率方法理路概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。和Lovász 局部引理理路Lovász 局部引理Lovász local lemma当坏事件概率小且依赖稀疏时,所有坏事件同时不发生的概率为正。可用于证明不存在单色超边的着色存在;具体结论还取决于边大小与相互依赖程度。
在最坏情形最优连接理路最坏情形最优连接Worst-case optimal joins · WCOJ从AGM熵界到一般NPRR锚关系递归,完整核算三角形和四三元表实例的枚举与索引成本。中,给超边分配非负权重,使每个属性被覆盖至少一次,就能证明连接输出的乘积上界。不同关系即使属性集相同,也保留各自索引与大小;这正是带索引超边族比简单集合模型更合适的场景。
参考资料