关节点
- 拼音
- 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的邻接表
1.计算先深编号：对图进行先深搜索，计算每个结点v的先深编号dnf[v]，形成先深生成树S=（V,T）。
2.计算low[v]：在先深生成树上按后根顺序进行计算每个顶点v的 low[v]， low[v]取下述三个结点中的最小者：
(1) dfn[v]；
(3) low[y]，对v的任何儿子y。
3.求关节点：
(1)树根是关节点，当且仅当它有两个或两个以上的儿子（第一类关节点）；
(2)非树根结点v是关节点当且仅当v有某个儿子y，使low[y]≥dnf[v]（第二类关节点）。
求双连通分量的算法――同先深搜索算法（略）
关节点的字义分解
-
关
拼音 guān 部首 丷 总笔画 6["①闭，合拢。如 ～门。～闭。～张。～停并转（ zhǎn ）。②拘禁。如 ～押。～禁。③古代在险要地方或国界设立的守卫处所。如 ～口。～隘。～卡（ qiǎ ）。～塞（ sài ）。～津。嘉峪～。④征收进出口货税的机构。如 海～。～税。⑤重要的转折点，不易度过的时机。如 ～节。难～。年～。⑥牵连，联属。如 ～连。～联。～心。～涉。～乎。～注。～于。有～。⑦旧指发给或支领薪饷。如 ～饷。⑧姓。"]详细解释
-
点
拼音 diǎn 部首 灬 总笔画 9["①细小的痕迹或物体。如 ～滴。斑～。～子（➊液体的小滴，如“水～～”；➋小的痕迹，如“油～～”；➌打击乐器演奏时的节拍，如“鼓～～”；➍主意，办法，如“请大家出～～”；➎最能说明问题的关键地方，如“话没有说到～～上”）。②几何学上指没有长、宽、厚而只有位置的几何图形；两条线相交处或线段的两端。③数学上表示小数部分开始的符号（。），称“小数点”，如“231。4”。④量词，用于小的或少的。如 两三～雨。几～泪水。⑤一定的位置或限度。如 地～。起～。极～。居民～。⑥项，部分，方面。如 优～。要～。特～。⑦汉字笔形之一（丶）如 ～画。三～水。⑧加上点子，引申为修饰。如 标～。评～。～缀。画龙～睛。⑨使一点一滴地落下或发出。如 ～种。～射（自动武器有间歇的射击）。～眼药。⑩一落一起或一触即离的动作。如 ～头。～穴。⑪引火。如 ～火（亦喻挑起是非，制造事端）。⑫查对。如 ～数。～名。～卯（旧时称官衙、军伍卯时开始办公、操练，官员查点人数）。⑬指定，选派。如 ～菜。～将（ jiàng ）。听众～播。⑭指示，启发。如 指～。～拨。⑮计时的单位。如 更～（分为五更，一更又分五点）。三更三～。钟～。⑯污。如 ～污。～辱（使受污辱）。⑰指正餐以外的暂时充饥，亦指糕饼一类的食物。如 ～心（“心”读轻声）。～补（吃少量的食品解饿。“补”读轻声）。⑱同“踮”。"]详细解释
-
节
拼音 jiéjiē 部首 艹 总笔画 5["①竹子或草木茎分枝长叶的部分。如 竹～。～外生枝。②物体的分段或两段之间连接的部分。如 关～。两～车厢。③段落，事项。如 ～～（一段一段地，逐步）。～目。④中国历法把一年分为二十四段，每段开始的名称。如 ～气。～令。⑤纪念日或庆祝宴乐的日子。如 ～日。⑥礼度。如 礼～。⑦音调高低缓急的限度。如 ～奏。～拍。～律。⑧操守。如 ～操。晚～。变～。高风亮～（高尚的品德和节操）。⑨省减，限制。如 ～省。～制。开源～流。⑩略去，简略。如 ～选。～录。⑪古代出使外国所待的凭证。如 符～。使～。⑫姓。","◎〔～骨眼儿〕喻关键的，能起决定性作用的环节或时机（“骨”读轻声）。"]详细解释
