浅谈 SPQ Tree

jerry3128 · 2021-07-12 21:36:42 · 个人记录

零. 前言

• 本文会介绍关于二端串并联图的树形结构工具：SPQ Tree。

一. 二端串并联图

• 我们先给出二端串并联图的定义：仅使用串联和并联连接而成，并且带有源点和汇点的电阻网络无向图。
• 构建也十分简单，我们首先定义由两个节点一条边构成的图为二端串并联图。由两个二段串并联图首尾相接串联或者收尾各自合并串联形成的图也为二端串并联图。
• 如右图，源汇点会影响一个图是否为二端串并联图。
• 可以发现它有如下性质：
  • 二端串并联图是平面图，点和边数量级同阶。
  • 可以通过“缩二度点，消重边”收缩至只有源汇点。
• 考虑如下构建方法：

  从仅含一条边的图开始，执行若干次操作，操作有下列两种：

  1. （串联）选择一条边 u - v，增加一个新点 x，将原来的边 u - v 替换为 u - x - v。
  2. （并联）选择一条边 u - v，增加一条重边 u - v。

二. 二端串并联图的判定

• 我们可以根据逆推构建方式的方法来判定一个图是否为二端串并联图。

• 首先找到源汇点 S 和 T。

• 我们判定是否存在一条割边 u --> v 满足 S 与 u 连通且 T 与 v 连通。那么原图就可以分治为两个子问题判定，删去边 u --> v 判定 (S,u) (v,T) 是否分别为二端串并联图。

• 我们判定是否存在路径集合 Se , e \in Se 构成连通 S,T 的路径且 \forall e_{x,y}\in Se ,x\neq S\ or\ T , e_{x, * } \in Se。则我们可以将原图 G 拆分为 Se \ and \ \complement_{G}Se 两个图的源汇点仍然是 S,T ，分治为更小的问题。

三. 扩展定义

• 严格来讲，有些电阻网络中，我们可以发现有些地方没有电流流过，那么不论这些地方的电阻如何摆放，都不会影响电阻的大小。
• 所以判定的时候我们需要取出 S,T 间有电流经过的节点的导出子图进行判定。

四. 数据结构维护 —— SPQ Tree

• 我们考虑将一个串并联图由串并联拆解递归的过程。

• 自上而下去拆每个子图，或者自下而上的进行串并联图合并都可以构造 SPQ Tree。

• 值得注意的是串联节点的父亲肯定是并联节点，并联节点的父亲肯定是串联节点，以及所有边节点都是叶子节点。此外，如果图中没有割点，根节点就必为并联节点，否则为串联节点。

五. 统计二端串并联图的个数

给定一张 n 个点 m 条边的无向图，问有多少种选择端点的方法，使得这张图是扩展二端串并联图。

n,m \leq 10^{5}

• 首先可以发现，如果两个点处于相同的点双连通分量，那么这两个节点以外的点双中是没有电流的。否则我们判定两个点分别到自己点双的端点是否为二端串并联图，并判断端点间的路径上的点双是否全为二端串并联图。
• 现在问题转化为了：快速判定点双图中的二端串并联图。
• 在 SPQ Tree 的构建中，缩点时避免对给定的端点执行操作，如果最后能得到一条边则为串并联图。结构树实际上保存了缩点算法的整个过程，因此可以考虑用这棵树来加速。

假设现在得到了结构树，对于树上任意一棵子树，这棵子树以及删去该子树得到的树均可以分别缩为一条边。那么对于端点 a 和 b，不难发现如果 a 和 b 可以放到某条串联路径上，则这对端点是合法的。其它情况下，我们将会逐一验证为不合法。考虑 a 和 b 处于两个不同的串联路径上，分别对应 u 和 v 两个串联节点。设 p 为 u 和 v 在结构树上的最近公共祖先，假设 p 不是根节点，分以下几种情况考虑：

• 当两个在同一点双节点能够构成二端串并联图当且仅当两个节点在结构树上在同时出现在同一串联节点上。
• 之所以要求 p 不是根节点，是因为上图 (c) 这种情况中，若 p 为根节点且只有两个分岔，则给定的端点是合法的。为了避免，我们首先特判掉简单的环状图，这样保证图中存在度数大于 2 的节点。然后在缩点算法中，优先缩原图中度数为 2 的点，这样就可以保证根节点的分岔数至少为 3。综上，我们可以得出，一对端点合法的充要条件是这对端点可以放在同一条串联路径上。
• 我们令 f[x] 表示节点 x 在点双上 x 的端点向下到子树内的二端串并联图个数，在 tarjan 过后原图为一个树不难发现可以做到线性 DP 解决。

六. 后记

• 嘛，不过，总而言之：

• 手抖地连字都打不清了（

upd：一年后

以上学术图片摘自：二端串并联图相关

upd：什么情况？一群完全没这个水平的人来要代码。代码去某完全学术 OJ 扒，刷到这个水平的人我不信不知道。