生成树问题

Published: by Creative Commons Licence

  • Tags:

生成树

一个无向连通图的生成树是指该图的一个连通无环子图。而最小生成树就是所有生成树中总边权最小的。

割点和割边

定义1:给定无向图,如果删除某个顶点$v$后,导致图中的连通分量增多,那么称这个点是割点。

定义2:给定无向图,如果删除某个边后,导致图中的连通分量增多,那么称这个边是割边。

割边的求法非常简单,利用tarjan算法进行缩点后得到一棵树,这棵树中的所有边都是割边。这也意味着割边最多存在$V-1$条。

割点的求法类似,先求出任意一株生成树。如果根下面挂了一颗以上子树,那么根顶点一定是割点。对于其余顶点$v$,如果$v$不能访问到比父亲顶点dfn序号更小的顶点,那么就意味着父顶点对于$v$是一个割点。

DFS生成树

一篇不错的博客

对于一个连通图图,我们可以通过DFS求出其中一个生成树,这样的生成树我们称为DFS生成树。显然只有一部分边被加入到了生成树中,加入的边我们称为生成边,其余边称为备用边(back-edge)。

DFS生成树特性:

  • 所有备用边都连接某个祖先和其后代。
  • 每条备用边的加入都会构成一个简单环。
  • 对于任意一条生成边$(u,v)$,其中$u$是$v$的父亲,$(u,v)$是割边当且仅当不存在连接$u$的祖先和$v$的后代的后备边。
  • 连通分量是强连通分量当且仅当其中不存在割边。

讨论几个DFS生成树的应用:

题目1:给定一副连通无向图,不存在自环和重边,要求将每条边转换为有向边且要求转换完成后,所有顶点对之间都存在至少一条路径。判断是否存在方案,如果存在,则输出任意一种可行方案。

由于转有向图后强连通,因此有向图中不存在割边,那么原来无向图也一定不存在割边,即原图必须是强连通的。这是必要条件。

先生成无向图的一个DFS生成树,之后我们将所有的从生成边的方向设置为祖先指向后代,而将所有备用边的方向设置为后代指向祖先。

下面我们保证上面的图是强连通的。很显然从根顶点$r$到其余顶点都存在路径,现在考虑任意顶点$v$,假设其父亲为$u$,且其父亲到根存在一条路径,那么由于$(u,v)$不是割边,因此存在一条跨越$(u,v)$的备用边$(s,t)$,其中$s$是$t$的后代。我们可以沿着路径$v..t,s..u..r$从$v$抵达$r$。利用归纳法可以证明所有顶点都可以抵达根,因此有向图是强连通的。

题目2:给定一副无向图,不存在自环和重边,且保证每个顶点的度数大于等于$k$。现在要求找到任意一个长度大于等于$k+1$的简单环(无重复顶点)。

首先生成DFS树,考虑DFS树的任意叶子顶点,与其直接相邻的生成边的数目为$1$,因此至少还有$k-1$条后备边。由于每条后备边连接不同的祖先顶点(不是父亲顶点),因此有一个祖先顶点至少距离当前顶点$k$,于是乎加上这条后备边就构成了一个长度大于等于$k+1$的简单环。

题目3:给定一副$n$个顶点的无向图,不存在自环和重边。要求要么找出一个大小为$\lceil \sqrt{n} \rceil$的独立集,要么找到一个长度至少为$\lceil \sqrt{n} \rceil$的简单环。

我们可以利用贪心算法来找独立集,每次选择度数最小的顶点,选择它并删除所有与其关联的顶点以及它,这个过程直到剩余所有顶点度数都大于等于$\lceil \sqrt{n}\rceil-1$或者没有顶点了才停止。在这个过程,由于找到的度数最小的顶点度数小于$\lceil \sqrt{n}\rceil-1$,因此每次选择最多使得$\lceil \sqrt{n}\rceil-1$个顶点不可用。如果所有顶点都被消除了,那么我们至少选择了$\lceil \sqrt{n}\rceil$轮,即我们得到了一个满足条件的独立集。否则,剩余的顶点的度数都至少为$\lceil \sqrt{n}\rceil-1$,而这保证我们一定能找到一个长度至少为$\lceil \sqrt{n}\rceil$的简单环。

提供一道题目

题目4:给定一副$n$个顶点$m$条边的简单无向连通图(无自环重边),保证每个顶点度数都至少为$3$。给定某个数$k$,现在要求找到找到一条长度为$\lceil \frac{n}{k}\rceil$的简单路径(无重复顶点);或者找到$k$条长度至少为$3$,且长度不能被$3$整除的环,且每个环都至少有一个独属于自己的顶点。

很显然对于每个叶子顶点,其至少有两条备用边连向不同的祖先,而这会构成三个环,其中至少一个环不能被$3$整除。且每个环都包含这个叶子顶点,我们可以将叶子顶点作为独属的顶点。

如果有$k$个叶子顶点,那么我们就直接求出解了。否则我们记$d_i$为第$i$个叶子顶点的深度,且$c_i$为叶子数,那么一定有$\sum_{i=1}^cd_i\geq n$,因为从每个叶子向上走可以覆盖所有的顶点。之后利用鸽巢原理可以直接得出至少有一个叶子$i$深度满足$d_i\geq \lceil\frac{n}{c}\rceil \geq \lceil\frac{n}{k}\rceil$。这样我们就找到了路径了。

最小生成树

prim和kruskal

最小生成树的求法不外乎两种,prim和kruskal。两个都是贪心算法,正确性基于最小生成树类似的性质。

随意取一个顶点u,记所有与u关联的最小权边为$e=(u,v)$,其中$u\neq v$。现在我们证明e一定属于一株最小生成树,用反证法。假设最小生成树T中不包含e。我们知道e是与u关联的最小边,因此可以将e加入到T中,这样就会出现一个包含点u的环。删除环上与u相连的另外一条边e',得到了一株新的树T',而T'的总权不可能大于T(加入e删除了e',e的权重小于等于e'),因此weight(T')<=weight(T)。这样我们就得到了包含e的一株最小生成树。

由这个观察我们可以推出贪心的流程。

  1. 创建一个空集T。

  2. 任意取一个顶点u,找到与该顶点u相关联的最小权重边e=(u,v),满足$u\neq v$,从点集V中删除u、v,并将e加入到空集T中,之后合并顶点u、v,将合并后的顶点加入到V中。
  3. 如果V中只剩一个顶点了,那么就结束,此时T就是最小生成树。否则回到步骤2。

上面这个流程就是prim算法。由于并不限制步骤2的u的选择,因此你可以总是选择顶点1以及包含顶点1的合并顶点,这样整个流程就完全等价于dijkstra算法了,用最小堆优化后得到的时间复杂度为$O(\min((V+E)\log_2V, V^2))$。

prim算法是通过点去找边,也可以通过边去找点,下面的算法就是如此:

  1. 创建一个空集T。
  2. 从边集E中弹出权重最小的边e=(u,v),如果在生成树T中u、v不处于相同连通块,就将e加入T中,否则忽略e。
  3. 如果E为空集,那么就结束,此时T就是最小生成树。否则回到步骤2。

上面这个流程就是kruskal算法,我们可以提前对E进行排序,并用路径压缩并查集维护连通块,这样时间复杂度为$O(E+E\log_2E)$。

题目1:给定$n$个顶点$m$条边构成的无向连通图,第$i$个顶点的权值为$w(i)$。要求找到一组边,构成生成树,且要求$\sum_{v}deg(v)w(i)$最大

我们发现加入一条边$(u,v)$,会导致结果增大$w(u)+w(v)$。我们可以将$w(u)+w(v)$作为边$(u,v)$的权值,用最小生成树算法找到最大生成树即可。

子图最小生成树

对于一个包含$n$个顶点$m$条边的无向图,现在需要处理$q$个请求,每个请求选中一些顶点,要求输出这些顶点的最小生成树包含哪些边。这里$1\leq n\leq 20,n-1\leq m\leq {n\choose 2},1\leq q\leq 10^6$。

我们可以直接用kruskal算法$O(n^2q)$解决这个问题。但是实际上我们可以优化到$O(nq+n2^n)$。这个技术是从这里学到的。

记$k=\sqrt{n}$。记$X$为删除编号最大的$k$个顶点后的子图,记$Y$为删除编号最小的$k$个顶点后的子图。我们用上面的暴力算法分别计算$X$和$Y$的所有子集的最小生成树,这个过程时间复杂度为$O(2(n-k)^22^{n-k})\approx O(n2^n)$,空间复杂度则为$O(2^n)$。

现在考虑如何处理请求,对于某个查询的集合$S$,我们可以断言可能组成它的最小生成树的边仅来自$S\&X$和$S\&Y$的最小生成树,或者一个端点是最小的前$k$个顶点,一个端点是最大的后$k$个顶点。可以发现这时候只需要考虑最多$2n$条边,由于kruskal的算法时间复杂度是与边数目相关,因此每个请求处理的时间复杂度为$O(n)$。

题目1:对于一个包含$n$个顶点$m$条边的无向连通带权图,且给定$k$张优惠券,额度分别为$d_1,\ldots,d_k$。可以用优惠券减少某条边的权重,如果在权重为$w$的边上使用第$i$张优惠券,可以将该条边的费用减少$\min(d_i,w)$。一条道路最多使用一张优惠券,一张优惠券也最多只能使用一次。接下来处理$q$次请求,请求如下:

  • 给定起点$s$和终点$t$,查询两点之间最小距离,要求返回从$s$到$t$,可以任意使用优惠券的前提下,最少的费用。

其中$1\leq n\leq 20,n-1\leq m\leq {n\choose 2},1\leq q\leq 10^6$。

问题来自: SRM795Div1 1000

我们可以发现无论优惠券怎么改变,图中的最小生成树是不变的。且两点的最小距离,实际上正好等于某个包含这两个点的子图的最小生成树。

用上面的技术我们可以$O(n2^n)$找到所有子图的最小生成树,同时用贪心的方法,较大额度的用于费用较大的路径(注意我们取出最小生成树的时候已经是排过序的了),因此时间复杂度为$O(n2^n)$预处理,之后我们可以对状态进行下推来找到所有点对的最短路径,时间复杂度为$O(n2^n)$。剩下的请求都可以$O(1)$回答。

最小瓶颈路

一条路径中,权重最大的边称为路的瓶颈,而从起点到终点的所有路径中瓶颈最小的路径称为最小瓶颈路。

对于两个不同的顶点$i$,$j$,记$f_{ij}(x)$表示只保留图中权重不超过x的边的前提下,顶点$i$与$j$是否连通(连通为$1$,不连通为$0$)。很显然这样的函数$f_{ij}$一定是非严格递增函数。假设$i$、$j$之间的最小瓶颈路的瓶颈权重为$t$,那么$t$一定是$f_{ij}$最小的能令其返回$1$的入参。

因此我们可以先对边集按照权重从小到大进行排序,之后按序将边的两个端点所在连通块合并为一个连通块。这个过程持续直到$i$和$j$处于相同的连通块中。

这个流程实际上和kruskal是如同的,因此我们可以相信最小生成树中的任意两个端点$i$、$j$之间的唯一路径就是图上的最小瓶颈路。

求所有最小生成树的并集

给定一张无向连通图,求其所有最小生成树的并集。

有两种方法。

第一种方法,就是先任意构建一个最小生成树,显然最小生成树中的所有边都要被包含进去。考虑任意未被包含进最小生成树的边$e=(a,b)$,其连通两个顶点,考虑最小生成树中从a到b的唯一路径上权重最大的边$e'$,由于最小生成树具有最小瓶颈路的性质,因此$e'$的权重不可能大于$e$。如果$e'$的权重恰好等于$e$,那么我们可以从最小生成树中删除边$e'$并加入$e$来获取一颗新的最小生成树。

上面的总的时间复杂度为$O((n+m)\log_2n)$,路径操作可以用LCT实现。

第二种方法是,考虑kruskal算法,我们将边集按照边的权重进行分组,第i组就是所有权重为i的边组成的集合。注意到我们可以通过变换同组边之间的处理顺序得到所有的最小生成树。我们可以证明不管如何打乱同一组边的处理顺序,在处理完第i组的边后,所有的连通关系都是相同的,即在一种顺序下两个顶点是连通的,那么在另外一种处理顺序下亦然。这个可以利用归纳法进行证明,假设处理完前i-1类边后连通关系相同。那么考虑以任意顺序处理第i类边,如果第i组边中所有边最后都被加入最小生成树,那么连通关系肯定相同。如果不是所有边被加入,那么考虑任意一个未被加入的边$(a,b)$,那么我们可以断定a和b一定连通(否则我们可以将$(a,b)$纳入最小生成树中)。因此当我们处理完前i类边后,对于任意前i类边$(u,v)$,$(u,v)$一定是连通的。

而一条边是否有机会组成最小生成树,假设边的权重为k,那么我们只要观察,在处理完前$k-1$类边后,这条边的两个端点是否连通即可。第二种方法的时间复杂度也是$O((n+m)\log_2n)$,但是这边不需要用到LCT,只需要用到并查集即可。

求最小生成树的数目

最小生成树的数目可以通过kruskal算法求出。在求所有最小生成树的并集这一节中,已经说过了所有kruskal算法流程中,可以通过变换边的处理顺序得到所有的最小生成树。事实上,对于固定的图,要得到最小生成树,其中所有权重为i的边选取的数量也是固定的(和边的处理顺序无关)。假设最小生成树中权重为$i$的边共选择了$c_i$个,那么我们在处理第$i$类边的时候,可以暴力枚举选取$c_i$条边的,情况,去除其中成环的情况。不同权重的边可以独立处理。