生成树问题

Published: December 22, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 生成树
• 割点和割边
• DFS生成树
• 最小生成树
  • prim和kruskal
  • borůvka算法
  • 子图最小生成树
  • 最小瓶颈路
  • 求所有最小生成树的并集
  • 求最小生成树的数目
• 限制度数的最小生成树
  • 限制一个顶点度数的最小生成树
  • 限制$k$个顶点度数的最小生成树
• 二进制转换问题

生成树

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

割点和割边

定义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'的总权不可能大于（加入$e$删除了$e'$，$e$的权重小于等于$e'$)，因此$weight(T')\leq 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)$的权值，用最小生成树算法找到最大生成树即可。

borůvka算法

borůvka算法也可以用于求最小生成树。它的原理非常简单，假设任意不同边都有唯一权重（否则我们可以拼接边的id来获得唯一权重）。

设对于不同的顶点，记$(i,X_i)$为与$i$相关的最小权重边。记$T$为最小生成树，则对于任意$i$，$(i,X_i)$属于最小生成树。

原因非常简单。假设$(i,X_i)$不属于最小生成树$T$，则将$(i,X_i)$加入，则必定可以用$(i,X_i)$替换路径$i$和$X_i$的路径上的与$i$相关联的那条边。

因此borůvka的如下：

1. 如果已经得到生成树，生成树则一定是最小生成树，结束流程。否则进入第2步。
2. 对于任意连通块$C$，找到权重最小的边$(u,v)$，其中$u\in C$，且$v\notin C$。并将$(u,v)$加入到最小生成树（需要去重）。回到步骤1。

由于每次迭代都至少会减少一半的连通块，一次你迭代最多发生$\log V$次。每次迭代实际上可以$O(E)$完成，因此总的时间复杂度为$O(E\log V)$。

题目1：给定一个$N$个顶点$M$条边的无向连通图，其中前$K$个顶点是特殊的。构造新的一个包含$K$个顶点的完全图，其中边$(i,j)$的权重为原图中从$i$到$j$的最短路。要求找到新图的一个最小生成树。其中$1\leq K\leq N\leq M\leq 10^5$。

提供一道题目。

利用borůvka算法可以$O(M\log M)$的时间复杂度找到以内每个连通块（仅特殊顶点）到其它连通块（仅特殊顶点）的最短边。

因此总的时间复杂度为$O(M\log M\log N)$。

子图最小生成树

对于一个包含$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$条边的，情况，去除其中成环的情况。不同权重的边可以独立处理。

限制度数的最小生成树

限制一个顶点度数的最小生成树

给定一副图$G=(V,E)$，找到其中一株生成树，要求顶点$1$的度数正好为$k$。如果有多棵满足条件的生成树，则找到总边权最小的生成树。

有两种求解算法（都没有很严谨的证明，拿着用吧，反正这种类型的题目很少）。

记$f(k)$表示我们的答案，可以感性发现$f$是个上凸函数。因此为了强制选$k$个，可以套上WQS算法，这样时间复杂度就是$O(E\log_2E+tE)$，其中$t$为二分次数。

还有一种更好的算法，他可以帮助我们同时找到$f(1),\ldots,f(k)$（如果我们不要求度数正好为$k$，而是要求不超过$k$，这时候这种技术就非常有用了）。首先我们假设图是连通的（否则一定无解），我们先删除所有关于顶点$1$的边，之后算出最小生成森林，假设除了$1$所在连通块外，还有$m$个连通块，那么我们知道$1$至少度数为$m$，否则无法形成生成树。而得到$f(m)$，我们可以简单贪心的为每个连通块选择一条最小权重边。接下来假设我们已经找到$1$度数正好为$k-1$的最小生成树$T_{k-1}$，要求$1$度数正好为$k$的最小生成树$T_k$。这时候需要加入一条边$(1,v)$，同时假设原先$v$所在连通块中与$1$相关的边为$(1,u)$，那么还需要删除$v$到$u$路径上权重最大的一条边$e_v$，来避免出现环。可以考虑所有的$v$，而$e_v$可以通过以$u$为根dfs得到。切换的时间复杂度为$O(V)$。因此总的时间复杂度为$O(E\log_2E+kV)$。

提供一道题目。

限制$k$个顶点度数的最小生成树

给定$n$个顶点和$m$条带权无向边，现在要求为前$k$个顶点加上度数限制，第$i$个顶点的度数限制为$d_i$。要求判断是否存在一个生成树，如果存在则找到最小生成树。

其中$1\leq n\leq 50$，$0\leq k\leq 5$，$m\leq n^2$。

我们可以发现被枚举的顶点之间仅有${5\choose 2}=10$条边，只有$2^10=1024$个可能的导出子图，但是实际上只会有$300$个导出子图是无环的。

我们可以暴力枚举最小生成树的前$k$个顶点的生成子图。将剩余的边分成两类，第一类为所有一个顶点编号小于等于$k$的边，记作$A$，以及两个端点编号都大于$k$的边，记作$B$。

我们可以给每个顶点一个颜色，以及每个颜色一个数量限制。一个集合是独立集当且仅当每种颜色的元素都不超过该颜色的容量。这满足拟阵中独立集的定义。

现在我们需要找到图拟阵和颜色拟阵的一个拟阵交中的最大权最大集合。

一般最大权最大独立集可以$O(r^2x^2)$实现，其中$r$表示最大独立集的大小，而$x$表示全集大小。这里$r=O(n)$，$x=m$，总的时间复杂度为$O(n^6)$，过大了。这里我们可以考虑一个优化，就是$B$中我们只需要考虑最小生成树中出现的$O(n)$条边，而其余边是不可能被考虑的。因此总的边数减少到$O(kn)$。总的时间复杂度为$O(k^2n^4)$。配合上总共运行的轮次，时间复杂度大致为$O(300k^2n^4)$。实际时间大概在3s左右。

二进制转换问题

给定$n$和$m$，现在有$n$个二进制数$0,\ldots,2^n-1$。如果两个二进制数之间只有一位不同，则在它们之间连接一条边。接下来处理$m$个请求。请求分两类：

• 给定$l,r$，要求删除所有值在$l,r$之间的二进制数。
• 给定$a,b$，保证$a,b$不同且未被删除，要求判断是否存在一条$a$，$b$之间的路径，不经过任意一个删除过的二进制数。

其中$1\leq n\leq 60$，且$1\leq m\leq 10^5$。

讲一下具体的做法。

我们可以将每个删除操作视作一种上色操作，如果一个元素被删除多次，则仅使用第一种颜色。接下来可以发现仅存在$O(m)$个连续段拥有相同的颜色。我们接下来考虑一个分治流程。假设分治的部分为$0$到$2^k-1$，如果分治需要处理的连续段只有一个，那么可以直接返回这个连续段。否则我们按照第$k-1$位是否为$1$，分为两部分。之后递归处理两部分，之后通过双指针的技术将两部分中有重合（不考虑第$k-1$位）的连续段之间加入一条边。

接下来我们逆向处理问题，初始有些连续段不存在，之后不断插入这些连续段。插入的时候顺带尝试恢复所有相关的边，我们可以用个DSU来维护连通性。

记$N$为得到的连续段数，$M$为插入的边数，很显然最终的时间复杂度为$O(nN+M+m\log_2N)$。

其中$N=O(nm)$，$M=O(nN)=O(n^2m)$。这时候时间复杂度为$O(n^2m+m\log_2nm)$。

但是实际上我们可以压缩顶点数。具体原理是可以发现$[0,x]$中任意两个元素始终可达（先化成$0$，之后转成任意数），同理对于$[x,2^k-1]$中任意两个数也是可以互达的。具体是对于连续段$[l,r]$，如果$l=r$，则显然是一个连续段，不用分割，否则我们按照$l$，$r$的第一个不同位进行分割，划分为两个连续段。这样最后顶点数为$O(m)$，而边数为$O(nm)$（边可以用相同的分治算法来求边）。

最后总的时间复杂度为$O(nm+m\log_2m)$。