「OI」圆方树

圆方树 就是一种将图变成树的方法。可以把图的问题转化为树上问题。

仙人掌

定义

仙人掌(学名:Opuntia stricta (Haw.) Haw. var. dillenii (Ker-Gawl.) Benson )石竹沙漠植物,是仙人掌科缩刺仙人掌的变种。

它的图片是这样的:

普通仙人掌
圆方树 – 仙人掌

才怪。

仙人掌指的是每条边在不超过一个简单环中的无向图。

下面有一些仙人掌。

Round Square Tree Z2
一颗普通的仙人掌

圆方树

定义

圆方树是处理仙人掌上问题的一种工具,它的思想很简单,就是把图中每一个简单环变成菊花图的形状。用圆点表示原图上的点,方点表示新增的辅助点。

下面有一些示意图。

圆方树 仙人掌 Z3 树

应用

圆方树可以用来处理一些简单的问题。

例题可以看我的博客。

广义圆方树

定义

广义圆方树是处理一般图上问题的一种工具,它的思想很简单,就是把图中每一个点双连通分量变成菊花图。

要介绍广义圆方树,首先要介绍点双连通分量。

一个点双连通图的一个定义是:图中任意两不同点之间都有至少两条点不重复的路径。
点不重复既指路径上点不重复(简单路径),也指两条路径的交集为空(当然,路径必然都经过出发点和到达点,这不在考虑范围内)。

可以发现对于只有一个点的图比较难定义它是不是一个点双,这里先不考虑节点数为 $1$ 的图。

一个近乎等价的定义是:不存在割点的图。
这个定义只在图中只有两个点,一条连接它们的边时失效。它没有割点,但是并不能找到两条不相交的路径,因为只有一条路径。
(也可以理解为那一条路径可以算两次,的确没有交,因为不经过其他点)

虽然原始的定义的确是前者,但是为了方便,我们规定点双图的定义采用后者。

而一个图的点双连通分量则是一个极大点双连通子图。
与强连通分量等不同,一个点可能属于多个点双,但是一条边属于恰好一个点双(如果定义采用前者则有可能不属于任何点双)。

在圆方树中,原来的每个点对应一个圆点,每一个点双对应一个方点。
所以共有 $n+c$ 个点,其中 $n$ 是原图点数,$c$ 是原图点双连通分量的个数。

而对于每一个点双连通分量,它对应的方点向这个点双连通分量中的每个点连边。
每个点双形成一个“菊花图”,多个“菊花图”通过原图中的割点连接在一起(因为点双的分隔点是割点)。

显然,圆方树中每条边连接一个圆点和一个方点。

下面有一张图,来自 WC 的 PPT,显示了一张图对应的点双和广义圆方树形态。

图片来源于网络(WC PPT)

应用

广义圆方树的应用比较广泛,下面是相应例题。

参考资料