资源描述：
《图论中的圈与块.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论中的圈与块绍兴县柯桥中学黄劲松基本概念圈(环)割点割边(桥)块强连通子图(强连通分量(支,块))10/1/20212浙江省2006年集训讲义圈及其相关知识MST(最小生成树)另类算法最小环问题10/1/20213浙江省2006年集训讲义MST另类算法任意构造一棵原图的生成树，然后不断的添边，并删除新生成的环上的最大边。1017253算法证明?10/1/20214浙江省2006年集训讲义水管局长(1)给定一张带权无向连通图，定义max(p)为路径p上的最大边，min(u,v)为连接u和v的所有路径中，max(p)的最小
2、值。动态的做如下两个操作：1：询问某两个点之间的min(u,v)2：删除一条边你的任务是对于每个询问，输出min(u,v)的值。(WC2006)10/1/20215浙江省2006年集训讲义水管局长(2)数据范围约定结点个数N≤1000图中的边数M≤100000询问次数Q≤100000删边次数D≤500010/1/20216浙江省2006年集训讲义水管局长(3)根据kruskal算法可以知道，最小生成树上的连接两点之间的唯一路径一定是最大边最小的那么，只要维护一棵图的最小生成树，那么就可以在O(N)的时间内回答每一个min
3、(u,v)的询问不断的删边然后维护最小生成树？10/1/20217浙江省2006年集训讲义水管局长(4)通过删边的形式我们似乎很难维护一张图的最小生成树根据刚才提到的MST的另类做法，我们反向处理它的每个操作，也就是先删除所有要删的边，然后再逆向添边并回答min(u,v)于是该问题就可以用另类MST算法解决了10/1/20218浙江省2006年集训讲义水管局长(5)这里涉及到一些图与树的存储操作，如何在O(N)的时间内找到环上最大边，并维护一棵最小生成树呢？如果采取邻接表的存储方式来记录一棵最小生成树，从添加的边的某个点
4、开始遍历整棵树，寻找出环上的最大边，虽然理论复杂度是O(N)的，但是有很多的冗余10/1/20219浙江省2006年集训讲义水管局长(6)这里我们采取父亲表示法来存储一棵最小生成树，如图所示：现在添加入一条红色的边AB我们根据被删边所在的位置来决定AB的定向如果被删边在B到LCA(A,B){A和B的最近公共祖先}的那条路径上，则定义AB的方向为B->A，即A是B的父亲，并将被删边到B的这条路径上的所有边反向(同理可得被删边在A到LCA(A,B)的那条路径上的情况)AB10/1/202110浙江省2006年集训讲义小H的聚
5、会(1)给定每个节点的度限制，求在满足所有度限制的条件下的最大生成树。(NOI2005)这是一道提交答案式的题目，对于后面的几个较大的数据，用另类MST算法对你的解进行调整也能取得不错的效果！10/1/202111浙江省2006年集训讲义最小环问题虽然涉及到要求最小环的题目并不多(Ural1004Sightseeingtrip)，但是下面介绍的一些求最小环的算法也会对你有一定的启示意义有向带权图的最小环问题(直接用floyd算法可解)无向带权图的最小环问题10/1/202112浙江省2006年集训讲义朴素算法令e(u,v
6、)表示u和v之间的连边，再令min(u,v)表示，删除u和v之间的连边之后，u和v之间的最短路最小环则是min(u,v)+e(u,v)时间复杂度是EV210/1/202113浙江省2006年集训讲义一个错误的算法预处理出任意两点之间的最短路径，记作min(u,v)枚举三个点w,u,v，最小环则是min(u,w)+min(w,v)+e(u,v)的最小值如果考虑min(u,w)包含边u-v的情况？讨论：是否有解决的方法？10/1/202114浙江省2006年集训讲义改进算法在floyd的同时，顺便算出最小环g[i][j]=i
7、,j之间的边长dist:=g;fork:=1tondobeginfori:=1tok-1doforj:=i+1tok-1doanswer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);fori:=1tondoforj:=1tondodist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);end;算法证明？10/1/202115浙江省2006年集训讲义块及其相关知识DFS算法割点(一般对于无向图而言)割边(一般对于无向图而言)块(一般对于无向图而
8、言)强连通子图(一般对于有向图而言)10/1/202116浙江省2006年集训讲义DFS算法1973年，Hopcroft和Tarjan设计了一个有效的DFS算法PROCEDUREDFS(v);begininc(sign);dfn[v]:=sign;//给v按照访问顺序的先后标号为signfor寻找一个v的相邻节点ui
