guānjiédiăn

关节点

拼音
guān jié diăn
注音
ㄍㄨㄢ ㄐㄧㄝˊ ㄉㄧㄢˇ
繁体
關節點

关节点的意思

词语解释

关节点(關節點)guān jié diǎn

  1. 量变引起质变临界点。是两个不同质的事物界限,事物的度的边缘

网络解释

关节点

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 部首总笔画 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. 同“踮”。 [更多解释]

关节点的分字组词

关节点的相关词语

【关节点】的常见问题

  1. 关节点的拼音是什么?关节点怎么读?

    关节点的拼音是:guān jié diăn
    点击 图标播放关节点的发音

  2. 关节点是什么意思?

    关节点的意思是:量变引起质变的临界点。是两个不同质的事物的界限,事物的度的边缘。