Borůvka + 隐式图模型实例

Borůvka 隐式图模型的实例索引:主理想、Rectilinear MST、XOR-MST,以及通用的紧凑最值查询条件。

标签 图论 / 生成树 / Borůvka / 问题模型

本页承接 Borůvka + 隐式图模型,讨论谓词需要满足什么结构,并索引具体的最优出边 oracle 实例。

以下沿用主模型页的记号:𝑃(𝑖,𝑗) 表示边存在,𝑣𝑖 表示点权。

谓词需要什么性质?

Borůvka 本身要求边权对称且可比较、图连通(或改求最小生成森林),并且每轮能拿到每个分量的最优出边。前两条与“子集”无关;第三条是效率要求。

若 𝑃 任意,隐式图可以编码任意图,求最优出边可能和显式枚举一样难(Ω(𝑛2))。所以要让 Borůvka 在隐式图上高效,邻域族 𝑁(𝑖)(相邻节点集合。即所有满足 𝑃(𝑖,𝑗) 的 𝑗)必须具有“紧凑的最值查询表示”。本质是利用 𝑃 的结构性质设计快速回答最优出边查询的算法。

一种常见结构是:𝑁(𝑖) 是一个主理想,或少量主理想之并。此时可以用 Zeta 变换预处理,查询时读一个或合并少量表项;并数必须很小。Rectilinear MST 与 XOR-MST 不属于这一类,分别使用方向扫描和二进制 trie。

实例索引

  • 主理想类实例:布尔格(Zeta 变换 / SOS DP)、树形偏序(子树最值)、DAG 可达性(原图与反图各一个主理想)。
  • Rectilinear MST:8 个八分圆候选边 + Kruskal,或四象限 Borůvka。
  • XOR-MST:Borůvka + 可删除 二进制 trie。

其他可快速求邻居的隐式图

只要数据结构能在“排除当前分量”后返回最优邻居,就能套 Borůvka:

  • 最近邻:k-d tree、球树、Voronoi 图;
  • 区间 / 矩形查询:线段树、树状数组、二维 BIT;
  • 字符串 / 序列:后缀数组、AC 自动机;
  • 其他可合并摘要:按需设计。

本类不固定 𝑃 的具体形式;实际题目会给出 𝑃(𝑖,𝑗) 的判定方式,例如“𝑗 是 𝑖 的最近邻”“𝑗 落在某个矩形内”“𝑗 与 𝑖 的字符串匹配”。这里没有“必须是主理想”或“边权必须可分离”的限制;限制只在于 oracle 能否高效回答 query(𝑖,𝐶)。如果每次查询都要扫描整个分量,Borůvka 就退化成显式枚举。

源码位置