圆方树 就是一种将图变成树的方法。可以把图的问题转化为树上问题。
仙人掌
定义
仙人掌(学名:Opuntia stricta (Haw.) Haw. var. dillenii (Ker-Gawl.) Benson )石竹沙漠植物,是仙人掌科缩刺仙人掌的变种。
它的图片是这样的:

才怪。
仙人掌指的是每条边在不超过一个简单环中的无向图。
下面有一些仙人掌。

圆方树
定义
圆方树是处理仙人掌上问题的一种工具,它的思想很简单,就是把图中每一个简单环变成菊花图的形状。用圆点表示原图上的点,方点表示新增的辅助点。
下面有一些示意图。
应用
圆方树可以用来处理一些简单的问题。
例题可以看我的博客。
广义圆方树
定义
广义圆方树是处理一般图上问题的一种工具,它的思想很简单,就是把图中每一个点双连通分量变成菊花图。
要介绍广义圆方树,首先要介绍点双连通分量。
一个点双连通图的一个定义是:图中任意两不同点之间都有至少两条点不重复的路径。
点不重复既指路径上点不重复(简单路径),也指两条路径的交集为空(当然,路径必然都经过出发点和到达点,这不在考虑范围内)。
可以发现对于只有一个点的图比较难定义它是不是一个点双,这里先不考虑节点数为 $1$ 的图。
一个近乎等价的定义是:不存在割点的图。
这个定义只在图中只有两个点,一条连接它们的边时失效。它没有割点,但是并不能找到两条不相交的路径,因为只有一条路径。
(也可以理解为那一条路径可以算两次,的确没有交,因为不经过其他点)
虽然原始的定义的确是前者,但是为了方便,我们规定点双图的定义采用后者。
而一个图的点双连通分量则是一个极大点双连通子图。
与强连通分量等不同,一个点可能属于多个点双,但是一条边属于恰好一个点双(如果定义采用前者则有可能不属于任何点双)。
在圆方树中,原来的每个点对应一个圆点,每一个点双对应一个方点。
所以共有 $n+c$ 个点,其中 $n$ 是原图点数,$c$ 是原图点双连通分量的个数。
而对于每一个点双连通分量,它对应的方点向这个点双连通分量中的每个点连边。
每个点双形成一个“菊花图”,多个“菊花图”通过原图中的割点连接在一起(因为点双的分隔点是割点)。
显然,圆方树中每条边连接一个圆点和一个方点。
下面有一张图,来自 WC 的 PPT,显示了一张图对应的点双和广义圆方树形态。

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