最近在啃超图理论第一章“超图基本概念”虽然内容不多但信息密度挺高。我一边读一边对照原来熟悉的普通图概念记了不少对比笔记这篇算是把第一遍的学习心得整理出来。超图Hypergraph这个概念本身不难难的是从“一条边只能连接两个顶点”的惯性思维里跳出来真正接受“一条边可以同时连接一堆顶点”的设定。这篇文章既是我自己的总结也适合正要入门超图理论、或者想搞懂超图到底是什么的朋友参考。我会从基本定义、术语细节、超图的各种变形到实际应用一点点拆开讲把容易看晕的地方都用大白话重新说一遍。1. 为什么先讲超图而不是直接啃代数表示1.1 普通图装不下的多对多关系学超图之前我一直觉得普通图已经够用了。节点和边、有向无向、权值、路径、连通性这套语言几乎能描述所有网络结构。直到我真正开始处理一些“天然就是多对多”的数据时才发现普通图其实很吃力。举个例子。你在微信里建了一个聊天群群里有五个人。在这个五人群里张三发了一条消息这条消息同时被李四、王五、赵六、孙七看到。如果要用普通图表示这种关系你只能给张三和李四连一条边张三和王五连一条边这样两两之间各连一条。如果是几百个人的大群两两连线就会形成一张特别密集的图信息冗余不说还会把“一个群整体”这个内部结构彻底弄丢。超图解决的就是这个问题。在超图里我们可以把“这个群”本身作为一条超边这条超边直接把这五个人全部收入其中。不需要拆成两两配对群的整体性一下子保住了。类似的场景还有论文合作一篇文章有六个作者普通图得画十五条边才能表示六个人两两合作过超图只需要一条超边就把六个人的合作关系打包了。这就是超图存在的核心理由它专门处理“一组一组”的关系而普通图只擅长处理“两两”的关系。1.2 超图的形式化定义到底在说什么第一章给的定义并不复杂一个超图 (H) 是一个二元组 ((V, E))其中 (V) 是顶点的有限集合(E) 是 (V) 的非空子集的一个有限集合。(E) 中的每一个元素称为一条超边hyperedge。听着好像就是把普通图的“边”替换成“超边”但这里面有一个非常关键的细节普通图的边都是二元组((u, v))而超图的超边是 (V) 的任意非空子集也就是说一条超边可以包含两个顶点也可以包含三个、五个甚至全部顶点。我一开始读这个定义的时候脑子里自动把“非空子集”理解成了“可以有任意多个元素”后来做题才发现还有两个很容易忽略的边界情况第一空集不是超边因为定义明确说了是非空子集第二单个顶点的集合可以是超边也就是 (\lbrace v \rbrace) 这种形式。单个顶点的超边看起来好像没什么意义但在超图的递推构造、某些图的分解算法里它起着非常基础的占位作用。另外一个容易混淆的点是普通图的 (E) 是从所有二元子集中选出来的所以普通图天然是简单图没有重边、没有环的图。但超图的 (E) 是从所有非空子集里选的这就允许两条超边包含完全相同的顶点集合。这种情况叫作多重超边后面会专门说到。2. 必须抠字眼的基本术语2.1 阶、规模、顶点数、超边数一个都不能混第一章最基础也最容易被忽略的就是这几个计数概念。超图的阶order指顶点数也就是 (|V|)。超图的规模size指超边数也就是 (|E|)。这两个词在中文资料里经常翻译得不太统一有的教材把阶叫“顶点数”把规模叫“超边数”其实意思完全一样。我在笔记里专门做了一个对照术语英文含义记号顶点数 / 阶order图里有多少个点(超边数 / 规模size图里有多少条超边(顶点 (v) 的次数degree包含该顶点的超边数量(d(v))顶点 (v) 的度degree同上同一概念不同译法(d(v))超边 (e) 的基数cardinality这条超边里有多少个顶点(|e|)为什么要强调这个因为我发现很多初学者包括我自己会在“超边的基数”和“超图顶点次数”这两个概念上绕圈子。超边的基数说的是“一条超边能装多少人”顶点的次数说的是“一个顶点出现在多少条超边里”一个是看超边内部一个是看超边之间完全不同。2.2 顶点的次数与孤立顶点的坑给定超图 (H (V, E))顶点 (v) 的次数degree定义为包含 (v) 的超边的数量记作 (d(v))。如果一个顶点的次数是 0说明没有任何一条超边包含它这个顶点就叫孤立顶点。看到定义的时候我想当然地觉得孤立顶点就是超图里没人理的顶点这个直觉没问题。但做题时容易踩的一个坑是孤立顶点虽然不在任何超边里但它仍然是 (V) 的成员仍然算在阶里面。也就是说一个超图完全可以有几个顶点在那儿“挂着”不参与任何关系但你不能说它们不存在。这个概念在后续讨论超图的连通性时特别重要。第一章虽然还没展开讲连通性但孤立顶点的存在会直接影响很多性质的定义。比如在关联矩阵里孤立顶点对应的行是全零行在计算超图的某种着色、覆盖时也要先确定孤立顶点的处理方式。2.3 环、多重超边与简单超图普通图里有环的概念指一条边的两个端点相同。超图里的环定义稍有不同一条超边如果只包含一个顶点即 (e \lbrace v \rbrace)就称为环loop。这里要注意普通图的环是一个顶点自己连自己本质上也是二元关系 ((v,v))超图的环是只包含一个顶点的集合不存在“自环”的歧义。多重超边也很好理解如果两条不同的超边包含完全相同的顶点集合即 (e_i e_j) 且 (i \neq j)就说这两条超边是多重超边。包含多重超边的超图叫多重超图。那么不包含环、不包含多重超边的超图就叫简单超图。简单超图的定义可以从两个方向理解一是每条超边的基数至少为 2没有单顶点超边二是任意两条超边都不相同。我第一次看到“简单超图”的完整定义时有点意外因为它还要求每条超边的基数至少为 2也就是说简单超图里连环都不允许存在。这和普通图里“简单图不允许有环”的直觉一致挺好记的。3. 超图的种类一上来就给我这么多名词3.1 k-一致超图所有超边大小一样如果超图的所有超边都包含恰好 (k) 个顶点就称为 (k)-一致超图(k)-uniform hypergraph。这个定义是最容易和普通图建立联系的。普通无向图可以看成 2-一致超图因为每条边恰好连接两个顶点。这样一来普通图理论就变成了超图理论的一个特例。这个视角在学问上很有价值很多普通图的结论放到 2-一致超图里可能不成立反过来很多超图的定理如果限制在 2-一致超图上就能推论出普通图的经典性质。但要注意(k)-一致超图并不是说所有超边的基数都正好是 (k)而是每个 (e \in E) 都有 (|e| k)。如果顶点数 (n) 小于 (k)那这个图上根本没法存在一条大小为 (k) 的超边此时 (E) 只能为空集。这种空边集的 (k)-一致超图在某些构造题里会出现处理时要小心。3-一致超图在应用里非常常见。比如三个研究者合作一篇论文、三种物质参与一个化学反应、三个人发生过一次群聊这些都能自然地建模为 3-一致超图的超边。更通用的 (k)-一致超图则是众多算法在理论分析时的标准设定因为“所有超边大小一致”会让复杂度分析大大简化。3.2 完全超图、空超图和其他极端情况完全超图complete hypergraph定义为包含所有可能的非空子集作为超边的超图。对 (n) 个顶点来说完全超图总共有 (2^n - 1) 条超边排除空集。这个数量比普通完全图的 (n(n-1)/2) 条边大得多差距是指数级的。说到完全超图我自然而然地想了想完全 2-一致超图也就是所有大小为 2 的顶点子集都作为超边的超图。这个完全 2-一致超图恰好就是普通完全图 (K_n)。所以你看普通完全图也是完全超图的一个特例。空超图的定义有两个容易混淆的版本。一个版本是顶点集为空超边集也为空这没什么好说的。另一个版本是顶点集非空但超边集为空这种超图只有顶点没有任何关系本质上就是一大堆孤立顶点这种结构也叫无边超图。两种虽然都叫“空”但性质差别很大建议在笔记里特别标注。还有一种极端情况是顶点只有一个的问题。如果 (V \lbrace v \rbrace)这时只可能有一条超边 (\lbrace v \rbrace)也可能一条超边都没有。这个小例子看起来简单但在验证某些定理是否对平凡情况也成立时非常有用。3.3 子超图与部分超图别搞混了子超图的情况稍微复杂一点。子超图subhypergraph的定义是给定 (H (V, E))如果 (V’ \subseteq V)且 (E’ \subseteq E)并且 (E’) 中每条超边的所有顶点都在 (V’) 里那么 (H’ (V’, E’)) 就是 (H) 的一个子超图。注意“每条超边的所有顶点都在 (V’) 里”这个条件它意味着在取子超图时超边不能“截断”或“漏掉”一部分顶点。要么整条超边都在子图里要么不在。这一点和普通子图完全一致普通图里的子图也不会在选边的时候只选边的一个端点。部分超图partial hypergraph是另一个概念它只要求 (E’ \subseteq E)顶点集可以不变也就是说 (H’ (V, E’))。这个概念更接近我们平时说的“边的子集”。子超图和部分超图的最大区别在于子超图可以删掉一些顶点而部分超图只删边不删点。实际证明中这两个概念经常混着用但正式书写时一定要分清楚。我读第一章时花了挺久才把这两个定义完全区分开。3.4 超图与普通图包含关系的一个关键观察这一章一个特别重要的观察是普通图跟超图并不是并列关系而是包含关系。普通图就是 2-一致超图是超图的一个特例。这个观察让我重新审视了很多已知概念。比如匹配matching的概念在普通图里就是一组两两不相邻的边在超图里匹配就是一组两两不相交的超边。两个定义的形式几乎一样只是“不相交”的判断从“没有公共端点”变成了“没有公共顶点”。再比如点覆盖和独立集在超图和普通图里的形式也很接近只是约束条件变成了超边层面的。这个“特例”认知之所以重要是因为它决定了学习的顺序和深度。如果只把超图当普通图的延伸那很多新的定理、新的证明思路就很难真正掌握如果把超图当成更general的框架反过来再看普通图的结论很多以前觉得精巧的证明会突然变得容易理解因为它只是一个更宏大框架下的一个特例。4. 超图的三种重要变形4.1 关联图把超图翻译回普通图的桥超图虽然处理多对多关系很方便但很多成熟的算法和图论工具只适用于普通图直接套不上。所以“把超图翻译回普通图”就成为一个非常自然的操作最常见的一种翻译方式就是关联图incidence graph。给定超图 (H (V, E))它的关联图是一个二分图 (G (V \cup E, I))其中左边是原超图的顶点集合右边是原超图的超边集合如果原超图里顶点 (v) 属于超边 (e)则在 (v) 和 (e) 之间连一条边。这个构造非常优美。它把两种不同类型的对象顶点和超边变成了二分图两侧的同质节点然后用普通图的边来编码“属于”关系。关联图的一个直接好处是超图的很多性质可以等价地转化为关联图的性质来分析。比如超图里的一条路径对应到关联图里就是从超图顶点节点出发经过超边节点再到超图顶点节点这样交替走的一条路径。超图的连通性也就等价于关联图的连通性。我第一次画关联图时印象很深一个超图只有几条超边但画成关联图后左边一排点、右边一排点中间交叉连满了线完全就是一张二分网络。这个视角在处理大规模超图时特别有用因为二分图的数据结构在普通图算法里已经被研究得很透了。4.2 对偶超图把顶点和超边互换对偶超图是我觉得整个第一章里最“绕”但也最精彩的概念。超图 (H (V, E)) 的对偶超图 (H^* (E, V)) 定义如下(H^) 的顶点集合就是原 (H) 的超边集合(H^) 的超边集合由原 (H) 的每个顶点 (v) 构成其中超边 (\lbrace e \in E : v \in e \rbrace)。听起来非常绕我举个例子就清楚了。假设原超图 (H) 有三个顶点 (v_1, v_2, v_3)三条超边 (e_1 \lbrace v_1, v_2 \rbrace)、(e_2 \lbrace v_2, v_3 \rbrace)、(e_3 \lbrace v_1, v_3 \rbrace)。原超图的对偶 (H^) 有三个顶点分别叫 (e_1, e_2, e_3)然后看原图每个顶点出现在哪些超边里。(v_1) 出现在 (e_1, e_3) 里所以 (H^) 里有一条超边 (\lbrace e_1, e_3 \rbrace)(v_2) 出现在 (e_1, e_2) 里所以 (H^) 里有一条超边 (\lbrace e_1, e_2 \rbrace)(v_3) 出现在 (e_2, e_3) 里所以 (H^) 里有一条超边 (\lbrace e_2, e_3 \rbrace)。对偶超图的美妙之处在于它的结构彻底颠倒了“顶点-超边”的角色但保留了原超图的全部信息。很多超图性质在原始定义里看不出端倪但一换成对偶超图就豁然开朗。对偶这个概念在普通图里也有但普通图的顶点数跟边数往往不是同一个量级互换之后很难保持对称性。超图的顶点数和超边数则比较自由互换起来反而更自然。这一点在后面学习对偶性相关定理比如匹配和覆盖的对偶关系时会非常有用。4.3 影把超图投影到更低的阶影shadow这个概念在很多中文教材里也叫“投射”或“影子”定义是给定超图 (H (V, E))它的 k-影是另一个超图 (H_k)其顶点集仍然是 (V)超边集是 (E) 中所有大小不超过 (k) 的顶点子集。换句话说就是把原来的超边“拆开”把所有大小正好为 (k) 的子集都提取出来形成新的超边。如果一个超图不是 (k)-一致的甚至可以逐条超边分解成多个 (k)-子集从而得到 (k)-影。影这个概念对我来说最开始有点抽象后来我把它理解成“降维投影”。就好比一个三维物体在墙上的影子是二维的一个高阶超图的 (k)-影就是它在“(k)-关系层”上的投影。原来由大超边表示的复杂关系投影到 (k) 维之后可能变成了一大堆小关系从而可以用更成熟的普通图或低阶超图工具来分析。影还有一个值得注意的性质一个超图的 (k)-影通常不是唯一的 (k)-一致超图。因为不同的大超边投影后可能产生相同的 (k)-子集而影的定义会去掉重复。这一点在组合设计中经常作为探索超图结构的第一步。5. 超图到底能干什么不只存在于教科书学理论最怕的就是学完之后不知道能拿来干嘛。我这一章读下来整理了三个真实场景都是我接触过的、超图比普通图建模好得多的例子。5.1 社交网络与合作网络分析社交网络上最常见的“多对多”关系就是群聊、话题标签和多人合拍内容。如果用普通图做每个群聊都得画成一个个小团非常冗余。用超图做一个群聊就是一条超边一条超边里的人的互动强度可以直接用超边权重表示。这个方法在研究合作网络时尤其明显。比如六个人共同发表了一篇论文普通图只能表示两两合作关系超图则可以直接把六个人放一条超边上保留整次合作的结构信息。在研究科学团队的结构时这种超边建模比两两合作关系图更精准能更好地反映团队的完整规模、人员组成和跨团队重叠。5.2 生物信息学中的分子相互作用生物网络里的关系结构经常是多个分子一起发生作用。一个蛋白质复合物可能由三个、四个甚至十个蛋白质亚基组成而两个蛋白质之间是否“直接结合”本身就是一个很难定义的问题。此时用超图建模每个蛋白质复合物就是一条超边蛋白质就是顶点简洁明了。在代谢网络中也是这样一种酶的反应可能涉及多个底物和多个产物用普通图表示会丢失“多底物多产物”的整体信息而超图可以把一次完整反应建模为一条超边底物和产物的角色可以在超边的内部结构中体现。5.3 供应链、排产与组合优化超图分割hypergraph partitioning在芯片设计、任务调度和供应链网络里应用非常广泛。芯片设计里一个逻辑门可能连着多条信号线一组逻辑门的集合如果想要尽可能放在同一个物理区域就得用超图来表达“哪几个节点必须放在一起”的约束。将一个大规模超图分割成若干子图目标是最小化切割掉的外部连接这种操作在生产排产里也很常用。我第一次真正理解超图分割的价值是在一个复杂项目排期里多个任务依赖同一组共享资源两个任务同时启动就会产生冲突。用普通图把任务两两连边边数爆炸把共享资源建造成超边所有需要这个资源的任务自然形成一个“超边冲突域”调度时直接以超边为单位做冲突检测就快多了。5.4 机器学习中的超图神经网络近几年超图在机器学习里出镜率也很高。超图神经网络Hypergraph Neural Networks直接把超图的拓扑结构纳入消息传递机制让每个顶点的特征更新不仅要看邻居顶点还要看它所在的所有超边。这个设计让模型能更好地捕捉多体交互信息。在这个场景里超图的价值是它能显式建模高阶依赖。比如推荐系统里用户同时购买了若干商品这些商品一起构成一条超边或者一段影像素材的多个标签组成一条超边。超图神经网络可以沿着超边同时聚合所有成员的信息而不是像普通图那样只能两两聚合后再手动拼接。6. 学完第一章我踩过的坑和给你的建议6.1 第一个坑把超边默认为二元关系这是我看定义时犯的错。一开始读“超边是顶点的子集”时我总觉得超边里的顶点数应该多于 2下意识认为超边至少包含三个顶点不然和普通图的边有什么区别后来发现完全不对超边完全可以只包含两个顶点。2-一致超图里每条超边都是两个顶点但超图的理论体系并不会因为超边大小为 2 就变成普通图它仍然有对偶、有影、有匹配只不过恰好和普通图对应。所以我的建议是讨论超图时永远不要默认“超边必须大于2”。很多时候正是那些大小为 2 的超边充当了连接高阶超边和普通图之间的桥梁。6.2 第二个坑把度数和基数搞混第一章末尾有一堆“设计一个超图使得每个顶点次数为 3且所有超边基数都不大于 4”这种题。我第一次做的时候把“每个顶点次数为 3”理解成了“每个顶点必须出现在至少 3 条不同的超边里”结果构造出来的超图每条超边基数巨大完全不符合第二个要求。后来我才意识到这两个概念是可以独立控制的顶点的次数决定一个顶点关联多少条超边超边的基数决定这条超边关联多少个顶点。设计超图时两者都要兼顾。更正式地说它们满足一个简单的关系所有顶点的次数之和等于所有超边的基数之和因为都等于“顶点-超边”关联对的总数。这个等式在做超图构造题时几乎是万能的检查工具。如果手算发现两边不相等那这个超图一定画错了。6.3 第三个建议在学习时就把关联图和对偶画出来第一章的概念在脑子里过一遍可能会觉得简单但真到做题或应用时就会混淆。我的经验是每次接触一个新超图第一件事先画出它的关联图再写出它的对偶超图。这两个操作做完你对这个超图的结构就会有一个立体印象。画关联图的另一个价值是它能直接揭示超图是否连通、有没有孤立顶点、哪些超边共享了同一个顶点。这些信息在做很多算法题时都是直接可以用的先验信息。6.4 留给自己的练习题最后分享一道我做完后很有启发的练习题你可以试着做一下。设 (H (V, E))其中 (V \lbrace 1, 2, 3, 4, 5 \rbrace)超边集 (E \lbrace \lbrace 1,2,3 \rbrace, \lbrace 2,3,4 \rbrace, \lbrace 3,4,5 \rbrace, \lbrace 1,5 \rbrace \rbrace)。请回答(1) 画出 (H) 的关联图(2) 写出 (H) 的对偶超图(3) (H) 的 2-影包含哪些超边(4) 判断 (H) 是否连通并说明理由。做完这题你就会发现关联图、对偶、影、连通性这几个概念之间的内在联系其实非常紧密。我自己的体会是超图的基本概念学起来不费劲但真正难的是在多个概念之间灵活切换视角。能够随手把一个超图从原始定义翻到关联图再从关联图理解它的对偶才算真正把这一章吃透了。接下来我准备继续往后读超图的拓扑部分到时候再把新体会整理出来。