| 【图论】无向图的连通性 | 您所在的位置：网站首页 › 图论的公式 › 【图论】无向图的连通性 |
【图论】无向图的连通性
|
割点和割边 在无向图中，所有能互通的点组成了一个“连通分量”。在一个连通分量中有一些关键的点，如果删除它，会把这个连通分量分成两个或多个，这种点称为割点(Cut vertex)。在一个连通分量中，如果删除一个边，把这个连通分量分成了两个，这个边称为割边(Cut edge)。 思考一个基本问题：在一个无向连通图G中有多少个割点？ 一种暴力方法是：删除每个点，然后用DFS求连通性，如果连通分量变多，那么就是割点。其复杂度为 O(V(V+E)) ，不是好算法。下面用DFS，即利用“深搜优先生成树”求割点。 在一个连通分量G中，对任意一个点s做DFS，能访问到所有点，产生一棵“深度优先生成树”T。有以下定理： 定理1：T的根节点s是割点，当且仅当s有两个或更多的子结点。定理2：T的非根结点u是割点，当且仅当u存在一个子结点v，v及其后代都没有回退边连回u的祖先。编程实现以上定理：设u的一个直接后代是v，定义num[u]记录DFS对每个点的访问顺序，num值随着递推深度增大而变大；定义low[v]记录v和v的后代能连回到的祖先的num，只要low[v]>=num[u]就说明在v这个支路上没有回退边连回u的祖先，最多退到u本身。 例如 poj 1144 “network” 输入一个无向图，求割点的数量。 一个电话线公司正在建立一个电话线缆网络。他们用线缆连接了若干个地点，这些线是双向的，每个地点都有一个电话交换机。从每个地点都能通过线缆到达其他任意的地点，并不一定直接连接，可以通过若干个交换机来到达目的地。有时候某个地点供电出现问题，交换机会停止工作。工作人员意识到，除非这个地点是不可达的，否则它还会导致一些其他的地点不能相互通信。称这个地点为关键点。工作人员想要写一个程序找到所有关键点的数量。const int N = 109; int low[N], num[N], dfn; // dfn记录递归的顺序，用于给num赋值 bool iscut[N]; vector G[N]; // 存图 void dfs(int u, int fa) { low[u] = num[u] = ++dfn; // 初始值 int child = 0; // 孩子数目 for (int i = 0; i = num[u] && u != 1) iscut[u] = true; // 标记割点 } else if (num[v] = 2) // 根结点，有两个以上不相连的子树 iscut[1] = true; } int main() { int ans, n; // 输入图 memset(low, 0, sizeof(low)); memset(num, 0, sizeof(num)); dfn = 0; memset(iscut, false, sizeof(iscut)); ans = 0; dfs(1, -1); for (int i = 1; i = num[u] && u != 1)改为if (low[v] > num[u] && u != 1)，其他不变，就是求割边的数量。双连通分量在一个连通图中选任意两点，如果它们之间至少存在两条“点不重复”的路径，称为点双连通。即，点双连通分量中没有割点。类似地有边双连通分量，在边双连通图中去掉任意一个边，图仍然是连通的，也即边双连通图中没有割边。 计算点双连通分量一般用Tarjan算法：用DFS找到一个割点的时候已经完成了一次对某个极大点双连通子图的访问，那么，在进行DFS的过程中，把遍历过的点保存起来，就可以得到这个点双连通分量。在求解割点的过程中，用一个栈保存遍历过的边（因为一个边只属于一个点连通分量，而一个割点属于多个点连通分量），然后每当找到一个割点，即满足low[v]>=num[u]的点u，就将栈里的边拿出来。 给定一个无向图G，图中没有重边。问添加几条边才能使无向图变成双连通图。边双连通分量的计算用到了“缩点”的技术。 首先找到图G中的所有边双连通分量。在DFS过程中，图G所有的点都生成一个low值，low值相同的点必定在同一个边双连通分量中。DFS结束后，有多少low值就有多少个边双连通分量。把每一个边双连通分量都看作一个点，即把那些low值相同的点合并为一个“缩点”。这些缩点形成了一棵树。 3. 这样问题就转换为：至少在缩点树上增加多少条边才能使这棵树变为一个边双连通图。答案很简单， 至少增加的边数=(总度数为1的结点数+1)/2 。例如上图(b)有A、C两个度数为1的节点，至少增加的边数=(2+1)/2=1。 #include #include #include using namespace std; const int N = 1005; int n, m, low[N], dfn; vector G[N]; // 存图 void dfs(int u, int fa) // 计算每个结点的low值 { low[u] = ++dfn; for (int i = 0; i |
【本文地址】