guān
关
jié
节
diǎn
点
关节点
注音：ㄍㄨㄢ ㄐ一ㄝˊ ㄉ一ㄢˇ
词语解释：
量变引起质变的临界点。是两个不同质的事物的界限，事物的度的边缘。- 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]（第二类关节点）。
- 求双连通分量的算法――同先深搜索算法（略）
网络解释：
关节点
- 关读音：guān
(1)（动）使开着的物体合拢：～窗户｜把抽屉～上。
(2)（动）放在里面不放出来：鸟儿～在笼子里。
(3)（动）（企业等）倒闭；歇业：解放前有一年；镇上～了好几家店铺。
(4)（名）古代在交通险要或边境出入的地方设置的守卫处所：～口｜～东｜山海～｜嘉峪～｜我的责任就是不让废品混过～去。
(5)“关上”的简称。参看〖关口〗。
(6)（名）货物出口和入口收税的地方：海～｜～税。
(7)（名）比喻重要的转折点或不容易度过的一段时间：难～｜只要突破这一～；就好办了。
(8)（名）起转折关联作用的部分：机～｜～节｜～键。
(9)（名）牵连；关系：这些见解至～重要｜人民来信交给有～部门去处理。
(10)（动）发放或领取（工资）：～饷。
(11)（Guān）姓。
- 节读音：jié
- 点读音：diǎn
1. 细小的痕迹或物体：点滴。斑点。点子（ａ．液体的小滴，如“水点点”；ｂ．小的痕迹，如“油点点”；ｃ．打击乐器演奏时的节拍，如“鼓点点”；ｄ．主意，办法，如“请大家出点点”；ｅ．最能说明问题的关键地方，如“话没有说到点点上”）。
2. 几何学上指没有长、宽、厚而只有位置的几何图形；两条线相交处或线段的两端。
3. 数学上表示小数部分开始的符号（．），称“小数点”，如“231.4”。
4. 量词，用于小的或少的：两三点雨。几点泪水。
5. 一定的位置或限度：地点。起点。极点。居民点。
6. 项，部分，方面：优点。要点。特点。
7. 汉字笔形之一（丶）：点画。三点水。
8. 加上点子，引申为修饰：标点。评点。点缀。画龙点睛。
9. 使一点一滴地落下或发出：点种。点射（自动武器有间歇的射击）。点眼药。
10. 一落一起或一触即离的动作：点头。点穴。
11. 引火：点火（亦喻挑起是非，制造事端）。
12. 查对：点数。点名。点卯（旧时称官衙、军伍卯时开始办公、操练，官员查点人数）。
13. 指定，选派：点菜。点将（）。听众点播。
14. 指示，启发：指点。点拨。
15. 计时的单位：更点（分为五更，一更又分五点）。三更三点。钟点。
16. 污：点污。点辱（使受污辱）。
17. 指正餐以外的暂时充饥，亦指糕饼一类的食物：点心（“心”读轻声）。点补（吃少量的食品解饿。“补”读轻声）。
18. 同“踮”。