Skip to content

定义Definition

超图

施工中 · 内容逐步修订

Hypergraph

边可以连接任意多个顶点而非仅两个顶点的离散结构。

形式陈述 ​

超图是二元组 H=(V,E),其中 V 是顶点集,E⊆P(V) 是幂集中的一个子集,称为超边族。一条超边本身就是一组顶点。本页采用有限集合模型,允许空边和单点边,但同一个子集只出现一次;具体问题若禁止这些边,应另外说明。

若每条超边都恰含 r 个顶点,称为 r-一致超图。普通无自环简单图正是 2-一致超图,顶点集与每条二元边都原样保留。顶点 v 的度定义为

degH⁡(v)=|{e∈E:v∈e}|.

关联矩阵 B 以顶点为行、超边为列,Bv,e=1 当且仅当 v∈e,否则为零。这里行、列的标签也是表示的一部分:从第 e 列的非零行恰好恢复集合 e;全零列表示空边,全零行表示孤立顶点。简单模型的列不能重复,且最多有一个全零列。

为证明度数恒等式,取记录集合 I={(v,e):e∈E, v∈e},按关联记录的双计数分别固定两个坐标。按顶点分组有 degH⁡(v) 条记录,按超边分组有 |e| 条;每次分组都互斥且覆盖全部记录。因此逐行和逐列计算矩阵中 1 的总数,得到

∑v∈VdegH⁡(v)=∑e∈E|e|.

特别地,r-一致超图的度数和为 r|E|。

直觉

普通图记录成对关系,超图保留“哪些对象属于同一组”。一个三人群聊和三个两人群聊产生相同的两两相识关系,却是不同的超图。把每条超边替换成它所含顶点之间的全部二元边,会丢失这种分组信息。例如同一顶点集 {a,b,c} 上,超边族 {{a,b,c}} 与 {{a,b},{a,c},{b,c}} 的两两投影都是三角形,超边数却分别是一与三;从该投影不能逆推原分组。

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

例子与边界

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

B=(100110100011).

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

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

若不同群聊恰好具有相同成员,集合模型会把它们合并。需要保留身份时,应改用有限索引集 I 和带索引的超边族 (ei)i∈I,即多重超图。其关联矩阵改以 I 为列标签,允许不同列有相同内容;度数按索引计为 |{i:v∈ei}|,总和仍等于 ∑i|ei|,不能先把重复列去掉。例如两条不同编号的 {a,b} 给 a,b 各贡献二,而简单集合族只各贡献一。类似地,普通图的自环不能通过二元子集表达;单点超边的度数贡献是 1,也不同于图论自环贡献的 2。

超图的路径、圈与着色有不同惯例。若把弱着色规定为每条边至少出现两种颜色,空边或单点边便使该要求不可满足;强着色只要求边内不同顶点两两异色,在这两类边上真空成立。例如“每条边不能全同色”与“每条边内部两两异色”是不同要求。使用这些词时需给出规则,不能只沿用普通图术语。

推论与应用

关联矩阵可改画为二分图:取带不同标记的两侧 V×{0} 与 E×{1},当且仅当 v∈e 时连接 (v,0) 与 (e,1)。从右侧顶点的左邻集去掉标记,就恢复每条超边;孤立的右侧顶点仍须保留,它对应空边。多重模型把右侧换为 I×{1},相同邻集的不同右顶点仍表示不同的超边。保留两侧划分、标签和全部孤点时,这个往返才完整。与带标签关联矩阵的逐列恢复一样,编码与解码的两次复合分别还原各自输入,给出相应表示类之间的双射;把两侧或孤点忘掉,便是另一份数据。它与两两投影的关键差别,是超边本身也有一个可识别的位置。

组合设计把区组视作超边,数据库连接把关系所涉及的属性集视作超边。研究超图着色时,概率方法和Lovász 局部引理可用于证明不存在单色超边的着色存在;具体结论还取决于边大小与相互依赖程度。

在最坏情形最优连接中,给超边分配非负权重,使每个属性被覆盖至少一次,就能证明连接输出的乘积上界。不同关系即使属性集相同,也保留各自索引与大小;这正是带索引超边族比简单集合模型更合适的场景。

参考资料
  • Encyclopedia of Mathematics:Hypergraph,EMS Press 在线百科,访问于 2026 年,“定义、关联矩阵与度数”段。
  • Peter Keevash,The existence of designs,2018-02-16 作者稿,§1.1 的 Definition 1.1 与 Definition 1.5,分别采用集合与多重超边模型;本页另明确允许空边和单点边。
  • Michael Tait,Lecture Notes for 21-301: Combinatorics,Carnegie Mellon University 课程讲义,第 3 章开头,第 21–22 页,超图与群聊例子;在线文件访问于 2026 年。
关系图谱18 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

暂未标注直接上位概念。

下位 / 直接特例

类型化关系