关节点
- 拼音
- 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关 [ guān ] 1. 闭,合拢。 如 关门。关闭。关张。关停并转(zhǎn)。 2. 拘禁。 如 关押。关禁。 3. 古代在险要地方或国界设立的守卫处所。 如 关口。关隘。关卡(qiǎ)。关塞(sài)。关津。嘉峪关。 4. 征收进出口货税的机构。 如 海关。关税。 5. 重要的转折点,不易度过的时机。 如 关节。难关。年关。 6. 牵连,联属。 如 关连。关联。关心。关涉。关乎。关注。关于。有关。 7. 旧指发给或支领薪饷。 如 关饷。 8. 姓。 [更多解释]
节
拼音 jié,jiē 部首 艸 总笔画 5节 [ jié ] 1. 竹子或草木茎分枝长叶的部分。 如 竹节。节外生枝。 2. 物体的分段或两段之间连接的部分。 如 关节。两节车厢。 3. 段落,事项。 如 节节(一段一段地,逐步)。节目。 4. 中国历法把一年分为二十四段,每段开始的名称。 如 节气。节令。 5. 纪念日或庆祝宴乐的日子。 如 节日。 6. 礼度。 如 礼节。 7. 音调高低缓急的限度。 如 节奏。节拍。节律。 8. 操守。 如 节操。晚节。变节。高风亮节(高尚的品德和节操)。 9. 省减,限制。 如 节省。节制。开源节流。 10. 略去,简略。 如 节选。节录。 11. 古代出使外国所待的凭证。 如 符节。使节。 12. 姓。 节 [ jiē ] 1. 〔~骨眼儿〕喻关键的,能起决定性作用的环节或时机(“骨”读轻声)。 [更多解释]
点
拼音 diǎn 部首 火 总笔画 9点 [ diǎn ] 1. 细小的痕迹或物体。 如 点滴。斑点。点子(➊液体的小滴,如“水点点”;➋小的痕迹,如“油点点”;➌打击乐器演奏时的节拍,如“鼓点点”;➍主意,办法,如“请大家出点点”;➎最能说明问题的关键地方,如“话没有说到点点上”)。 2. 几何学上指没有长、宽、厚而只有位置的几何图形;两条线相交处或线段的两端。 3. 数学上表示小数部分开始的符号(.),称“小数点”,如“231.4”。 4. 量词,用于小的或少的。 如 两三点雨。几点泪水。 5. 一定的位置或限度。 如 地点。起点。极点。居民点。 6. 项,部分,方面。 如 优点。要点。特点。 7. 汉字笔形之一(丶)。 如 点画。三点水。 8. 加上点子,引申为修饰。 如 标点。评点。点缀。画龙点睛。 9. 使一点一滴地落下或发出。 如 点种。点射(自动武器有间歇的射击)。点眼药。 10. 一落一起或一触即离的动作。 如 点头。点穴。 11. 引火。 如 点火(亦喻挑起是非,制造事端)。 12. 查对。 如 点数。点名。点卯(旧时称官衙、军伍卯时开始办公、操练,官员查点人数)。 13. 指定,选派。 如 点菜。点将(jiàng )。听众点播。 14. 指示,启发。 如 指点。点拨。 15. 计时的单位。 如 更点(分为五更,一更又分五点)。三更三点。钟点。 16. 污。 如 点污。点辱(使受污辱)。 17. 指正餐以外的暂时充饥,亦指糕饼一类的食物。 如 点心(“心”读轻声)。点补(吃少量的食品解饿。“补”读轻声)。 18. 同“踮”。 [更多解释]
关节点的分字组词
关节点的相关词语
【关节点】的常见问题
-
关节点的拼音是什么?关节点怎么读?
答:关节点的拼音是:guān jié diăn
点击 图标播放关节点的发音。 -
关节点是什么意思?
答:关节点的意思是:量变引起质变的临界点。是两个不同质的事物的界限,事物的度的边缘。