做网站技巧,长页在线制作网站,公众号怎么创建,上海公司变更联贝财务优势目录
无向图的割点与桥
时间戳#xff1a;
搜索树#xff1a;
追溯值#xff1a;
割边判定法则#xff1a;
割点判定法则#xff1a;
无向图的双连通分量
定理#xff1a;
边双连通分量(e-DCC)的求法#xff1a;
e-DCC的缩点#xff1a;
有向图的连通性
追…目录
无向图的割点与桥
时间戳
搜索树
追溯值
割边判定法则
割点判定法则
无向图的双连通分量
定理
边双连通分量(e-DCC)的求法
e-DCC的缩点
有向图的连通性
追溯值
Tarjan算法求强连通分量SCC: 无向图的割点与桥
无向连通图G(V,E):
若对于 x 属于 V从图中删去节点 x 以及所有与 x 关联的边之后G 分裂成两个或两个以上不相连的子图则称 x 为 G 的割点。
若对于 e 属于 E 从图中删去边 e 之后G 分裂成两个不相连的子图则称 e 为 G 的桥或割边。
一般无向图不一定连通的“割点”和“桥”就是它的各个连通块恶的“割点”和“桥”。
Tarjan算法能够求出有向图的强连通分量、必经点与必经边。Tarjan算法是基于无向图的深度优先遍历。
时间戳
在图的深度优先遍历过程中按照每个节点第一次被访问的时间顺序依次给与 N 个节点 1~N 的整数标记给标记称为“时间戳”,记为 dfn[n]。
搜索树
在无向连通图中任选一个节点出发进行深度优先遍历每个点只访问一次。所有发生递归的边xy换言之从x到y是对y的第一次访问构成一棵树我们把它称为“无向连通图的搜索树”。当然一般无向图不一定连通的各个连通块的搜索树构成无向图的“搜索森林”。
追溯值 设 subtree[x] 表示搜索树中以 x 为根的子树。low[x] 定义为以下节点的时间戳的最小值。
1subtree[x] 中的节点。
2通过1条不在搜索树上的边能够到达 subtree[x] 的节点。
根据定义为了计算 low[x],应该先令 low[x]dfn[x],然后考虑从 x 出发的每条边。
若在搜索树上 x 是 y 的父节点则令 low[x]min(low[x],low[y]).
若无向边xy不是搜索树上的边则令 low[x]min(low[x],dfn[y]).
割边判定法则
无向边xy是桥当且仅当搜索树上存在 x 的一个子节点 y 满足dfn[x]low[y].
根据定义dfn[x]low[y] 说明从 subtree[y] 出发在不经过 xy的前提下不管走那条边都无法到达 x 或比 x 更早访问的节点。若把xy删除则 subtree[y] 就好像形成了一个封闭的环境与节点 x 没有边相连图断开成了两部分因此xy是割边。
反之若不存在这样的子节点 y 使得 dfn[x]low[y],则说明每个 subtree[y] 都能绕行其他边到达 x 或比 x 更早访问的节点xy自然就不是割边。
桥一定是搜索树中的边并且一个简单环中的边一定都不是桥。
特别需要注意, 因为我们遍历的是无向图所以从每个点 x 出发总能访问到它的父节点 fa。 根据 low 的计算方法(x,fa) 属于搜索树上的边且 fa 不是 x 的子节点故不能用 fa 的时间戳来更新low[x] 。 但是如果仅记录每个节点的父节点会无法处理重边的情况——当 x 与 fa 之间有多条边时(x,fa) 一定不是桥。 在这些重复的边中, 只有一条算是“搜索树上的边” 其他的几条都不算。 故有重边时, dfn[fa] 能用来更新 low[x]。 一个好的解决方案是:改为记录“递归进入每个节点的边的编号” 。编号可认为是边在邻接表中存储的下标位置。 这里介绍“成对变换”技巧。把无向图的每一条边看作双向边, 成对存储在下标 “2和3” “4和5” “6和7”处。若沿着编号为的边递归进入了节点 x 则忽略从 x 出发的编号为 i xor 1 的边通过其他边计算 low[x] 即可。
割点判定法则
若 x 不是搜索树的根节点(深度优先遍历的起点)则 x 是割点当且仅当搜索树上存在 x 的一个子节点 y满足:dfn[x] low[y] 特别地若 x 是搜索树的根节点则 x 是割点当且仅当搜索树上存在至少两个子节点 y1y2 满足上述条件。 证明方法与割边的情形类似这里就不再赞述。 因为割点判定法则是小于等于号所以在求割点时, 不必考虑父节点和重边的问题从X出发能访问到的所有点的时间戳都可以用来更新 low[x] 。
无向图的双连通分量
若一张无向连通图不存在割点则称它为“点双连通图”。若一张无向连通图不存在桥则称它为“边双连通图”。 无向图的极大点双连通子图被称为“点双连通分量”简记为“v-DCC”。无向连通图的极大边双连通子图被称为“边双连通分量”简记为“e-DCC”。 二者统称为“双连通分量”简记为“DCC”。 在上面的定义中我们称一个双连通子图 G(V,E“极大” (其中 V 属于 V , E 属于 E )是指不存在包含 G 的更大的子图 G(V,E)满足 V 属于V属于 VE 属于 P 属于 E 并且 G 也是双连通子图。
定理
一张无向连通图是“点双连通图” 当且仅当满足下列两个条件之一。1.图的顶点数不超过2。 2.图中任意两点都同时包含在至少一个简单环中。其中“简单环”指的是不自交的环也就是我们通常画出的环。 一张无向连通图是“边双连通图” 当且仅当任意一条边都包含在至少一个简单环中。 证明 该定理给出了无向连通图是“点双连通图”或“边双连通图”的充要条件。我们以“点双连通图”为例进行证明“边双连通图”的证明类似。 对于顶点数不超过2的情况 定理显然成立, 下面假设图中顶点数不小于3。先证充分性。若任意两点 x, y 都同时包含在至少一个简单环中则 xy 之间至少有两条不相交的路径。无论从图中删除哪个节点x,y 均能通过两条路径之一相连。故图中不存在割点是点双连通图。 再证必要性。反证法假设一张无向连通图是“点双连通图” 并且存在两点 xy它们不同时处于任何一个简单环中。
如果 xy 之间仅存在1条简单路径那么路径上至少有一个割点与“点双连通”矛盾。
如果 xy 之间存在2条或2条以上的简单路径那么容易发现任意两条都至少有一个除xy之外的交点:进一步可推导出, x,y之间的所有路径必定同时交于除 xy 之外的某一点 p (不然就会存在两条没有交点的路径形成一个简单环 根据定义p是一个割点与“点双连通”矛盾。故假设不成立。证毕。
边双连通分量(e-DCC)的求法
边双连通分量的计算非常容易。只需求出无向图中所有的桥把桥都删除后无向图会分成若干个连通块每一个连通块就是一个“边双连通分量”。
在具体的程序实现中, 一般先用Tarjan算法标记出所有的桥边。然后再对整个无向图执行一次深度优先遍历(遍历的过程中不访问桥边划分出每个连通块。下面的代码在Taran求桥的参考程序基础上计算出数组cc[X]表示节点 x 所属的“边双连通分量”的编号。
e-DCC的缩点
缩点将一个强连通分量缩成一个点。
把每个 e-DCC 看作一个节点把桥边 (x,y) 看作连接编号为 c[x] 和 c[y] 的 e-DCC 对应节点的无向边会产生一棵树若原来的无向图不连则产生森林)。这种把 e-DCC 收缩为一个节点的方法就称为“缩点”。下面的代码在Tarjan求桥、求e-DCC的参考程序基础上把e-DCC缩点构成一棵新的树(或森林)存储在另一个邻接表中。
有向图的连通性
给定有向图 G(V,E)若存在 r 属于 V满足从 r 出发能够到达 V 中所有的点则称G是一个“流图”(Flow Graph)记为 (G,r)其中 r 称为流图的源点。 与无向图的深度优先通历类似我们也可以定义“流图”的搜索树和时间戳的概念。 在一个流图(G.r)上从 r 出发进行深度优先遍历每个点只访问一次。所有发生通归的边 (x,y(换言之从 x 到是对 y 的第一次访问构成一棵以 r 为根的树我们把它称为流图(G,r)的搜索树。 同时在深度优先遍历的过程中按照每个节点第一次被访问的时间顺序依次给子流图中N个节点1~N的整数标记该标记被称为时间戳记为dfn[x]。 流图中的每条有向边(x,y)必然是以下四种之一。
1.树枝边指搜索树中的边即x是y的父节点一种特殊的前向边。 2.前向边指搜索树中x是y的祖先节点。 3.后向边指搜索树中y是x的祖先节点。 4.横叉边指除了以上三种情况之外的边它一定满足 dfn[y]dfn[x] .
给定一张有向图。岩对于图中任意两个节点,y既存在从x到的路也存在从y到x的路径则称该有向图是“强连通图”。
有向图的极大强连通子图被称为“强连通分量” 简记为SCC。 此处“极大”的含义与双连通分量“极大”的含义类似。
Tarjan 算法基于有向图的深度优先遍历能够在线性时间内求出一张有向图的各个强连通分量。 一个“环” 一定是强连通图。如果既存在从x到y的路径也存在从y到的那么x,y显然在一个环中。因此Tarjan算法的基本思路就是对于每个点尽找到与它一起能构成环的所有节点。
容易发现前向边”(x,y)没有什么用处因为搜索树上本来就存在从x到y。“后向边” (x,y) 非常有用因为它可以和搜索树上从y到x的路径一起构成环。“横叉边” (x,y) 视情况而定如果从y出发能找到一条路径回到x的祖先节点那么(x,y)就是有用的。
为了找到通过“后向边”和“横叉边”构成的环,Tarjan 算法在深度优先遍历的同时维护了一个栈。当访问到节点x时栈中需要保存以下两类节点。
1.搜索树上x的祖先节点记为集合 anc(x)。 设y属于anc(x)。 若存在后向边(x,y)则(x,y) 与y到x的路径一起形成环。
2.已经访问过, 并且存在一条路径到达 anc(x) 的节点。 设z是一个这样的点从出发存在一条路径到达y属于anc(x)。 若存在横叉边(x,2), 则(x,z)、z到y的路径、y到x的路径形成一个环。
综上所述栈中的节点就是能与从x出发的“后向边”和“横叉边”形成环的节点。进而可以引入“追溯值”的概念。
追溯值
设 subtree(x) 表示流图的搜索树中以x为根的子树。x的追溯值low[x]定义为满足以下条件的节点的最小时间戳。 1.该点在栈中。 2.存在一条从 subtree(x) 出发的有向边, 以该点为终点。
根据定义, Tarjan 算法按照以下步骤计算“追溯值”
1.当节点x第一次被访问时把x入栈 初始化low[x]dfn[x]。
2.扫描从 x出发的每条边(x,y)。 (1)若y没被访问过则说明(x,y是树枝边递归访问y从回潮之后, 令low[x]min(low[xl,lowly)。 (2)若y 被访问过并且y在栈中则令lowlx] min(lowlxl.dfnly). 3.从x回溯之前判断是否有lowlx]dfn[x]。若成立则不断从栈中弹出节点直至x出栈。
__________________________________________________________________________
1.树枝边指搜索树中的边即x是y的父节点一种特殊的前向边。 2.前向边指搜索树中x是y的祖先节点。 3.后向边指搜索树中y是x的祖先节点。 4.横叉边指除了以上三种情况之外的边它一定满足 dfn[y]dfn[x] .
如何判断某一点是否在某个强连通分量内
情况一存在后向边指向祖先节点。
情况二先走到横叉边横叉边再走到祖先节点。
Tarjan算法求强连通分量SCC:
对每个点定义两个时间戳
dfn[u]表示遍历到u的时间戳
low[u]从u开始走所能遍历到的最小时间戳是什么
u是其所在的强连通分量的最高点等价于dfn[u]low[u]
