Dominator Tree

前言

前不久我花了较长的一段时间看了李煜东的《图连通性若干拓展问题探讨》。
里面提到了一个比较冷门而非常经典的问题——必经点问题。
但问题是,里面的命题错漏百出(求不鄙视...)。
许多读者望而却步,而我在一位北大神牛师兄的帮助下完成了学习。
下面我将用比较简洁易懂的语言完成这篇文章,也当作我学习的一个总结。

几个关键词

Flow Graph
若有向图G中存在一点r,从r出发可以到达G中所有的点
则称G是Flow Graph,记为(G,r)。

搜索树(Dfs Tree)
从r出发对G进行深度优先遍历,递归时经过的有向边构成一棵树,称为G以r为根的搜索树。

时间戳(Dfn)
遍历过程中,按照节点经过的时间先后顺序给每个节点一个标号——时间戳,记为dfn[x]。
时间戳为x的节点的原编号记为id[x],即id[dfn[x]]=x。

对边进行分类

若(G,r)是一个Flow Graph,T是其Dfs Tree
则G中的每条边(x,y)必属于以下四类之一:

树枝边 (tree arcs): 边(x,y)在搜索树T中;

前向边 (forward arcs):在T中存在一条从x到y的路径;

后向边 (cycle arcs) :在T中存在一条从y到x的路径;

横叉边 (cross arcs):在T中既没有x到y的路径,也没有y到x的路径,并且dfn[y]< dfn[x]。
图片1.png

必经点、最近必经点与半必经点

必经点(dom)
若在(G,r)中从r到y的路径一定经过点x
则称x是从r到达y的必经点,记为x dom y。

从r出发到达y的所有必经点构成的集合记为dom(y)

最近必经点(idom)
节点y的必经点集合dom(y)中dfn值最大的点x称为y的最近必经点。
最近必经点是唯一的,因此可以记x=idom(y)。

半必经点(semi)
在搜索树T上,若y的一个祖先x满足:

在原图G中存在一条从x到y的路径与搜索树T上x到y的路径的交集为空集
且x是满足条件的点中dfn值最小的一个点
则称x是y的半必经点。

半必经点也是唯一的,记x=semi(y)。

半必经点定理

对于G中的一点y
考虑所有x∈y的前驱结点(pre)

定义一个临时变量temp=+∞。
若dfn[x] < dfn[y] , 则(x,y)为树枝边或前向边。
此时temp←min(temp,dfn[x])。

若dfn[x]>dfn[y],则(x,y)为横叉边或后向边。
此时 z∈x在T中的祖先满足dfn[z]>dfn[y]时
temp←min(temp,dfn[semi[z]])

semi[y]=id[temp]
即在上述所有情况中取dfn值最小的一个作为y的半必经点。

有了这个,我们就可以在接近线性的时间内求出每个点的semi值。
(用到的算法:并查集)

半必经点一定是必经点吗?

图片2.png

必经点定理(本校北大神牛自己yy的)

定义path为T中semi(y)到y的路径经过的点的集合(不包括端点)

也就是semi[x]到x路径中dfn值最小的idom。
有了这个,我们就可以在nlogn的时间内求出所有点的最近必经点。
(用到的算法:倍增算法)

该算法常数比较大,代码量也比较高
貌似有复杂度接近线性的Lengauer-Tarjan算法,但我也不知道怎么做。

Dominator Tree

设有向图G=(V,E),(G,r)是一个FlowGraph。

称(G,r)的子图为(G,r)的Dominator Tree

换句话来说,就是以r为根,(idom(x),x)为边的一棵树。
性质:显而易见的,xdomy当且仅当x为y的一个祖先。

经典应用

求有向图的割点 SPOJ BIA
求最远必经点 SPOJ EN
求必经点集 HDU 4694

comments powered by Disqus