关节点
- 拼音
- 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
点击 图标播放关节点的发音。关节点是什么意思?
关节点的意思是:量变引起质变的临界点。是两个不同质的事物的界限,事物的度的边缘。