【学习笔记】耳分解与无向图的双连通性

2024-04-18 03:28
文章标签 学习 笔记 分解 连通性

本文主要是介绍【学习笔记】耳分解与无向图的双连通性,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

感觉之前对于这方面的理解还是不够深入。

1.1 1.1 1.1 在无向图 G = ( V , E ) G=(V,E) G=(V,E)中,有一个子图 G ′ = ( V ′ , E ′ ) G'=(V',E') G=(V,E)(不一定是导出子图,其实只看 V ′ V' V就好了),若简单路径或简单环 P : x 1 → x 2 → . . . → x k P:x_1\to x_2\to ...\to x_k P:x1x2...xk满足: x 1 , x k ∈ V ′ , x 2 , . . . , x k − 1 ∉ V ′ x_1,x_k\in V',x_2,...,x_{k-1}\notin V' x1,xkV,x2,...,xk1/V,则称 P P P G G G关于 G ′ G' G的耳。若 P P P是简单路径,则称 P P P G G G关于 G ′ G' G的开耳。

简单说明一下,这里不讨论自环,但是有重边。简单环必须满足经过的边也不同,经过的点只有起点和终点相同。

1.2 1.2 1.2 对于无向连通图 G G G,若连通图序列 ( G 0 , G 1 , . . . , G k ) (G_0,G_1,...,G_k) (G0,G1,...,Gk)满足:

  • G 0 G_0 G0是一个简单环(可以只有一个点), G k = G G_k=G Gk=G
  • G i − 1 G_{i-1} Gi1 G i G_{i} Gi的子图
  • G i = ( V i , E i ) G_i=(V_i,E_i) Gi=(Vi,Ei),则 E i \ E i − 1 E_i\backslash E_{i-1} Ei\Ei1构成 G i − 1 G_{i-1} Gi1的一个耳(开耳)

则称 ( G 0 , G 1 , . . . , G k ) (G_0,G_1,...,G_k) (G0,G1,...,Gk) G G G的一个耳分解(开耳分解)。

1.3 1.3 1.3 无向连通图 G G G存在耳分解当且仅当 G G G边双联通。

必要性:若 G G G有耳分解 ( G 0 , . . . , G k ) (G_0,...,G_k) (G0,...,Gk),则由于 G 0 G_0 G0是简单环,所以 G 0 G_0 G0是边双联通的。加入一个耳过后显然还是边双联通的,归纳即可。

充分性:考虑求出以 1 1 1为根的一颗DFS树,然后按照以下方法得到 G G G的一个耳分解:

  • 找到一条以 1 1 1为端点的非树边 1 → x 1\to x 1x,令 G 0 G_0 G0是由树上路径 1 → x 1\to x 1x加上这条非树边形成的简单环
  • 如果 G i G_i Gi的点集不为 V V V,找到一个不属于 G i G_i Gi的点 x x x满足 x x x的父亲 y y y属于 G i G_i Gi,则由边双连通性知存在一条返祖边,两端点分别是 y y y的祖先(包括自己) u u u x x x的后代 v v v,考虑树上路径 y → v y\to v yv并上边 ( u , v ) (u,v) (u,v),这是 G i G_i Gi的一个耳,令 G i + 1 G_{i+1} Gi+1 G i G_i Gi并上这个耳。
  • 直到 G i G_i Gi的点集为 V V V,这个时候如果还有 G G G中的边未加入,则可以每条边都作为一个耳依次加入。

因为始终保证 G i G_i Gi的点集是一个包含 1 1 1的树上连通块,所以总能找到这样的 x x x

1.4 1.4 1.4 至少存在 3 3 3个点的无向连通图存在开耳分解当且仅当 G G G点双联通。

1.5 1.5 1.5 (双极定向)给定无向图 G = ( V , E ) G=(V,E) G=(V,E)和不同的两个节点 s , t s,t s,t,则四个命题等价:

  1. 在添加无向边 ( s , t ) (s,t) (s,t)后, G G G点双联通
  2. G G G的圆方树中所有方点构成一条链, s → t s\to t st是圆方树的一条直径
  3. 存在一种对 G G G的边进行定向的方法,得到一个有向无环图,且 s s s入度为零, t t t出度为零,其余点出入度都不为零
  4. 存在一个所有点的排列 p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p1,p2,...,pn,使得 p 1 = s , p n = t p_1=s,p_n=t p1=s,pn=t,且任意前缀和后缀的导出子图都是联通的。

证明:

首先1,2等价。考虑如果一个圆点 u u u连接了至少 3 3 3个方点,那么将 u u u删掉后会形成至少 3 3 3个连通块,显然只连一条 ( s , t ) (s,t) (s,t)是不行的。所以方点构成一条链,显然如果 s , t s,t s,t不是直径的两个端点那么 s , t s,t s,t之一还是会成为割点,否则显然就是点双了。

然后由3推4。容易发现取出一个拓扑排序即为满足条件的 p p p,因为正着来的时候加一个点显然仍然联通,所以任意前缀联通;反过来显然也可以说明任意后缀联通。

接下来由1推3。考虑取出 G G G的一个开耳分解,满足 G 0 G_0 G0包含边 ( s , t ) (s,t) (s,t),然后将 ( s , t ) (s,t) (s,t)之外的边都定向为从 s s s t t t。考虑每次加入一个开耳,若 G i G_i Gi的定向中 u u u可达 v v v,则令耳的方向为 u u u v v v,否则令耳的方向为 v v v u u u。(这个手段似乎在uoj的某道题中见过)。容易发现这样定向是满足条件的。

最后由4推1。假设命题1不成立,那么存在一个不同于 s , t s,t s,t的割点 u u u为割点,于是还有一个不包含 s , t s,t s,t的连通块,记作 S S S。设 S ∪ { u } S\cup \{u\} S{u}在排列 p p p中最早和最晚的点分别是 x , y x,y x,y,则 x , y x,y x,y中至少有一个不是 u u u。不妨设 x ≠ u x\ne u x=u(另一种情况取后缀即可),那么考虑前缀 p 1 , . . . , p i = x p_1,...,p_i=x p1,...,pi=x的导出子图,由于 u u u不在其中而 s , x s,x s,x都在其中,所以这张图一定不连通,矛盾。

白鹭兰

这题正常做应该能拿50,但是我是sb。

前面的部分不再赘述,需要关注的点是圆方树上的最优化问题往往可以贪心,即简单比较子树的大小,注意方点要看成0,圆点看成1。以及方点和圆点有时候都会对应大致相同的结论。这在 [省选联考 2023] 城市建造 中也有体现。

考虑构造,相当于有一个点双,固定了第一个加入的点 s s s和最后加入的点 t t t,满足每次加点后前缀和后缀的导出子图联通。

显然可以用双极定向的做法 O ( n 2 ) O(n^2) O(n2)构造。

更优秀的做法是考虑把DFS树取出来,然后每个子树只保留返祖边中深度最浅的那一条(也就是 l o w u low_u lowu),然后考虑缩二度点。 显然叶子一定是二度点,所以每次缩叶子即可。具体实现就是对每个点维护一个后继集合 L L L(有顺序),然后自底向上对于每个不再 s s s t t t路径上的 u u u,在 L f a u L_{fa_u} Lfau L l o w u L_{low_u} Llowu中插入 u u u,表示如果遍历到 f a u fa_u fau l o w u low_u lowu其中一个点则下一个遍历 u u u(注意二度点不会影响连通性)。这样就变成了直链的情形,直接遍历 s s s t t t的路径即可。

复杂度 O ( n + m ) O(n+m) O(n+m)

显然双极定向也能这么做。(?)

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e5+5;
int n,m,dfn[N],low[N],fa[N],num,tot,sz[N];
vector<int>G[N];
stack<int>stk;
vector<int>G0[N];
vector<int>vec[N];
void add(int x,int y){G0[x].pb(y),G0[y].pb(x);//cout<<"add:"<<x<<" "<<y<<"\n";
}
void tarjan(int u){dfn[u]=low[u]=++num,stk.push(u);for(auto v:G[u]){if(!dfn[v]){tarjan(v),low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){tot++;int tmp=0;do{tmp=stk.top(),stk.pop();add(tmp,tot),vec[tot].pb(tmp);}while(tmp!=v);add(u,tot),vec[tot].pb(u);}}else low[u]=min(low[u],dfn[v]);}
}
int f[N],son[N],son0[N];
void calc(int v){int tmp=0;if(v<=n)tmp=sz[v]-sz[son[v]];else{for(auto e:G0[v]){if(e==son[v]||e==fa[v])continue;tmp=max(tmp,sz[e]);}}f[v]=max(f[son[v]],tmp);
}
int kmin=inf,rt;
void dfs(int u,int topf){sz[u]=(u<=n);for(auto v:G0[u]){if(v==topf)continue;fa[v]=u,dfs(v,u),sz[u]+=sz[v];if(sz[v]>sz[son[u]])son0[u]=son[u],son[u]=v;else if(sz[v]>sz[son0[u]])son0[u]=v;}calc(son[u]),calc(son0[u]);f[u]=f[son[u]];int tmp=0;if(u<=n)tmp=n-sz[son[u]]-sz[son0[u]];else{tmp=n-sz[u];for(auto v:G0[u]){if(v==son[u]||v==son0[u]||v==fa[u])continue;tmp=max(tmp,sz[v]);}}if((son0[u]||u==1)&&max(tmp,max(f[son[u]],f[son0[u]]))<kmin){kmin=max(tmp,max(f[son[u]],f[son0[u]]));rt=u;}
}
vector<vector<int>>opt;
vector<int>arr;
bool ban[N];
void dfs0(int u,int topf){if(u<=n)arr.pb(u);for(auto v:G0[u]){if(v==topf)continue;dfs0(v,u);}
}
vector<int>L[N];
int ban0[N],fa0[N],vs0[N],rk[N];
vector<int>G1[N],G2[N];
vector<pair<int,int>>edge0[N];
void tarjan0(int u){dfn[u]=low[u]=++num,rk[num]=u;for(auto v:G1[u]){if(!dfn[v]){fa0[v]=u,tarjan0(v),low[u]=min(low[u],low[v]);G2[u].pb(v);}else low[u]=min(low[u],dfn[v]);}
}
void dfs1(int u){for(auto v:G2[u]){dfs1(v);}if(!ban0[u]){L[fa0[u]].pb(u);L[rk[low[u]]].pb(u);}
}
void find(int u,int s,int t,int id){if(u!=s&&u!=t){arr.clear(),dfs0(u,id);opt.pb(arr);}vs0[u]=1;for(auto v:L[u]){if(!vs0[v])find(v,s,t,id);}
}
void sol(int u,int s,int t){//cout<<"sol:"<<u<<" "<<s<<" "<<t<<"\n";for(auto v:vec[u])dfn[v]=low[v]=ban0[v]=fa0[v]=vs0[v]=0,G1[v].clear(),G2[v].clear(),L[v].clear();num=0;for(auto e:edge0[u]){int x=e.fi,y=e.se;G1[x].pb(y),G1[y].pb(x);}tarjan0(s);vector<int>path;//for(auto v:vec[u])cout<<"find:"<<v<<" "<<fa0[v]<<"\n";//cout<<"path:"<<s<<" "<<t<<"\n";int x=t;while(x!=s)path.pb(x),ban0[x]=1,x=fa0[x];path.pb(x),ban0[x]=1;reverse(path.begin(),path.end());dfs1(s);for(auto e:path)find(e,s,t,u);
}
pair<int,int>edge[N];
int main(){//freopen("data.in","r",stdin);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m,tot=n;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;G[x].pb(y),G[y].pb(x),edge[i]={x,y};}tarjan(1);dfs(1,0);for(int i=1;i<=m;i++){int x=edge[i].fi,y=edge[i].se;if(fa[fa[x]]==y)edge0[fa[x]].pb({x,y});else edge0[fa[y]].pb({x,y});}int x=rt;vector<int>vec0;if(son0[rt]){x=son0[rt];while(son[x])x=son[x];while(x!=rt)vec0.pb(x),ban[x]=1,x=fa[x];}while(x)vec0.pb(x),ban[x]=1,x=son[x];// for(auto e:vec0){//     cout<<e<<" ";// }for(int i=0;i<vec0.size();i++){int u=vec0[i];if(u<=n){arr.clear(),arr.pb(u);for(auto v:G0[u])if(!ban[v])dfs0(v,u);opt.pb(arr);}else{sol(u,vec0[i-1],vec0[i+1]);}}cout<<kmin<<" "<<opt.size()<<"\n";for(int i=0;i<opt.size();i++){cout<<opt[i].size()<<" ";for(auto e:opt[i])cout<<e<<" ";cout<<"\n";}//cout<<kmin<<" "<<opt.size()<<"\n";
}

总结

感觉之前做过的很多点双和边双的题都可以用这套理论来解释,但是能直观理解显然是更好的。

发现之前总是把点双简化成一个环,显然这在仙人掌图上是对的,但是对于复杂一点的题就不能直接这么做。

这篇关于【学习笔记】耳分解与无向图的双连通性的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/913650

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

线性代数|机器学习-P36在图中找聚类

文章目录 1. 常见图结构2. 谱聚类 感觉后面几节课的内容跨越太大,需要补充太多的知识点,教授讲得内容跨越较大,一般一节课的内容是书本上的一章节内容,所以看视频比较吃力,需要先预习课本内容后才能够很好的理解教授讲解的知识点。 1. 常见图结构 假设我们有如下图结构: Adjacency Matrix:行和列表示的是节点的位置,A[i,j]表示的第 i 个节点和第 j 个

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件