Posted on 2010-08-01 21:24
Kevin_Zhang 阅读(258)
评论(0) 编辑 收藏 引用 所属分类:
图论
割顶：
连通图G的一个顶点子集V，如果删除这个顶点子集和它所附带的边后，图便不再连通。则称V是G的割顶集。
最小割顶集中顶点的个数，称为G的连通度。连通度等于1时，割顶集中的那个顶点叫做割顶。
注意：完全图的连通度为总顶点数－1；
牵一发而动全身的点称为割点
边连通度：
连通图G的一个边子集E，如果删除边子集的边后，图便不再连通，则称E是G的桥集。
含有最小边数的桥集的边数|E|称为G的边连通度。|E|＝1时，E中的边叫做桥。
注意：规定不连通图的边连通度为0；完全图的边连通度为总顶点数－1；
连通图的两个特征：
1 连通度<=边连通度<=顶点数
2 顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上.(没搞明白)
块的概念：
没有割点的连通子图，这个子图中的任何一对顶点之间至少存在两条不相交的路径，或者说要使两个站点同时发生故障
至少两个站点同时发生故障，这种二连通分支称为块．
显然各个块之间的关系有如下两种：
1 互不连接
2 通过割顶连接(割顶可以属于不同的块，也可以两个块公有一个割顶)
引申：无向图寻找块，关键是找割顶．
满足是割顶的条件：
1 如果u不是根，u成为割顶的充要条件：当且仅当存在u的一个儿子顶点s,从s或者s的后代点到u的祖先点之间不存在后向边．
2 如果u是根，则u成为割顶当且仅当它不止有一个儿子点．
怎样求割顶：
引入一个标号函数：
low(u)=min{dfn(u),low(s),dfn(w)}; s是u的一个儿子，(u,w)是后向边
显然low(u)值是u或者u的后代所能追溯到的最早(序号小)的祖先序号．
利用标号函数low，分析求割顶的步骤：
顶点u不为根且为割顶的条件是当且仅当u有一个儿子s，使得low(s)>=dfn(u),即s和s的后代不会追溯到比
u更早的祖先点．
low(u)的计算步骤：
1 low(u)=dfn(u);
//u在dfs过程中首次被访问
2 low(u)=min{low(u),dfn(w)}
//检查后向边(u,w)时
3 low(u)=min{low(u),low(s)}
//u的儿子s的关联边被检查时
注意：对任何顶点u计算low(u)的值是不断修改的，只有当以U为根的dfs子树和后代的low值,dfn值全部出现以后才停止.