量变引起质变的临界点。是两个不同质的事物的界限,事物的度的边缘。
articulation point;articulare;
在某图中,若删除顶点V以及V相关的边后,图的一个连通分量分割为两个或两个以上的连通分量,则称顶点V为该图的一个关节点。一个没有关节点的连通图称为重连通图。
在重连通图中,任意一对顶点之间至少存在两条路径,则再删去某个顶点即相关各边后也不破坏图的连通性。若在图的连通图上删去k个节点才能破坏图的连通性,则称K为此图的连通度。
他们常常在通信网络的图或航空网中应用,K越大,系统越稳定,反之,战争中若要摧毁敌方的运输线,只须破坏其运输网中的关节点即可。
利用深度优先搜索便可以求的图的关节点,本由此可判别图是否重连通。
从任一点出发深度优先遍历得到优先生成树,对于树中任一顶点V而言,其孩子节点为邻接点。由深度优先生成树可得出两类关节点的特性:
(1)若生成树的根有两棵或两棵以上的子树,则此根顶点必为关节点。因为图中不存在连接不同子树顶点的边,若删除此节点,则树便成为森林。
(2)若生成树中某个非叶子节点V,其某棵子树与V的祖先节点无连接,则V为关节点。因为删去v,则其子树和图的其它部分被分割开来
low[v] 设对连通图G=(V,E)进行先深搜索的先深编号为dfn[v],产生的先深生成树为S=(V,T),B是回退边之集。对每个顶点v,low[v]定义如下
low[v]=Min{dfn[v],Min{low[w]|w是v的一个子女},Min{dfn[x]|(v,x)是一条回边}}//dfn数组记录顶点的深度优先数
算法: 求无向图的双连通分量
输入:连通的无向图G=( V, E )。L[v]表示关于v的邻接表
输出:G的所有双连通分量,每个连通分量由一序列的边组成。
1.计算先深编号:对图进行先深搜索,计算每个结点v的先深编号dnf[v],形成先深生成树S=(V,T)。
2.计算low[v]:在先深生成树上按后根顺序进行计算每个顶点v的 low[v], low[v]取下述三个结点中的最小者:
(1) dfn[v];
(2) dfn[w],凡是有回退边(v,w)的任何结点w;
(3) low[y],对v的任何儿子y。
3.求关节点:
(1)树根是关节点,当且仅当它有两个或两个以上的儿子(第一类关节点);
(2)非树根结点v是关节点当且仅当v有某个儿子y,使low[y]≥dnf[v](第二类关节点)。
求双连通分量的算法――同先深搜索算法(略)
1.构建和谐社会的关节点就是如何处理好人民内部矛盾。
2.文章对其推理的全部过程进行了较为清晰的拆解,然后主要以物质存在的层次性和层次之间“关节点”的矛盾性观点对芝诺的思想进行了破斥。
3.这些差异,是墨家逻辑研究历史转型、范式转换的标志和质变关节点。
4.司法权威具有状态、结构和要素三个层面的含义,与我国司法体制改革的目标、重点和起点三个关节点正好相互对应。
5.给定人物角色骨架后,依据人体测量学根据骨骼长度计算出关节点处的半径。
6.这些标志是劳动关系区分雇用关系、人事关系的关键,也是改革和完善救济机制的根本关节点。
7.双手握拳,以食指的掌指关节点揉脾俞、胃俞、三焦俞、肾俞,每穴各半分钟。
8.我们已经到了这样一个关节点,我不再对每个人说哈罗了。
9.着手实行是犯罪预备与犯罪未遂的关节点。
10.陈家刚的名字与中国当代艺术发展脉络中的很多关节点相连,因而他的个人经历往往比作品更加受到关注。
11.山谷词是词学研究中不能忽略的一个重要关节点。
12.同时,基于轮廓匹配来预测二维关节点的算法有效地解决了遮挡和跟踪错误积累这一关键问通。
13.城市化是解决中国当前问题的关节点。
14.到了某一个关节点,人们再也无法继续对大清洗,大饥荒和古拉格作辩解,把它们说成只是在实现他们真正的理想之前所发生的某种不幸的曲折而已。
15.省级台是中国电视业的重要力量和关节点,其中只有省级卫视具备了跨区域发展的物理基础。
16.关节点问题的研究,具有重大的理论和实践意义。
17.发散形的网络是没有中心的,它有数目不定的关节点,通过各种不同的方式联系在一起。
18.控辩双方的证明责任转换的关节点是法官证明评价的形成,这和控辩双方证明责任的性质密切相关。
19.一次整型动作即可同时完成关节点与脚背点之定型.
20.凭着不断的实验和反驳,科学的假说也不断地发生演变,最后终于使我们看到了物质的连续性不再明显的那个关节点。