首页汉语词典关节点关节点的意思_解释_造句

guān

jié

diǎn

关节点

拼音 guān jié diǎn 注音 ㄍㄨㄢ ㄐ一ㄝˊ ㄉ一ㄢˇ
拼音 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

    基本字义

    关(關)guān(ㄍㄨㄢ)

    ⒈  闭,合拢:关门。关闭。关张。关停并转(zhǎn)。

    ⒉  拘禁:关押。关禁。

    ⒊  古代在险要地方或国界设立的守卫处所:关口。关隘。关卡(qiǎ)。关塞(sài)。关津。嘉峪关。

    ⒋  征收进出口货税的机构:海关。关税。

    ⒌  重要的转折点,不易度过的时机:关节。难关。年关。

    ⒍  牵连,联属:关连。关联。关心。关涉。关乎。关注。关于。有关。

    ⒎  旧指发给或支领薪饷:关饷。

    ⒏  姓。

    异体字

    • ?
    • ?
    • ?
    • ?
    • ?
    • ?
    • ?
    • ?
    • ?

    汉英互译

    barrier、cut、pass、shut、turn off、close

    相关字词

    闭、合、启、开

    造字法

    形声:从门、关声

    English

    frontier pass; close; relation

    读音:jié

    基本字义

    节(節)jié(ㄐ一ㄝˊ)

    ⒈  竹子或草木茎分枝长叶的部分:竹节。节外生枝。

    ⒉  物体的分段或两段之间连接的部分:关节。两节车厢。

    ⒊  段落,事项:节节(一段一段地,逐步)。节目。

    ⒋  中国历法把一年分为二十四段,每段开始的名称:节气。节令。

    ⒌  纪念日或庆祝宴乐的日子:节日。

    ⒍  礼度:礼节。

    ⒎  音调高低缓急的限度:节奏。节拍。节律。

    ⒏  操守:节操。晚节。变节。高风亮节(高尚的品德和节操)。

    ⒐  省减,限制:节省。节制。开源节流。

    ⒑  略去,简略:节选。节录。

    ⒒  古代出使外国所待的凭证:符节。使节。

    ⒓  姓。

    其他字义

    节(節)jiē(ㄐ一ㄝ)

    ⒈  〔节骨眼儿〕喻关键的,能起决定性作用的环节或时机(“骨”读轻声)。

    异体字

    • ?
    • ?

    汉英互译

    burl、gnarl、knar、knurl、kts、node、nodosity、nodus、period、section、stanza

    造字法

    形声

    English

    knot, node, joint; section

    读音:diǎn

    基本字义

    点(點)diǎn(ㄉ一ㄢˇ)

    ⒈  细小的痕迹或物体:点滴。斑点。点子(a.液体的小滴,如“水点点”;b.小的痕迹,如“油点点”;c.打击乐器演奏时的节拍,如“鼓点点”;d.主意,办法,如“请大家出点点”;e.最能说明问题的关键地方,如“话没有说到点点上”)。

    ⒉  几何学上指没有长、宽、厚而只有位置的几何图形;两条线相交处或线段的两端。

    ⒊  数学上表示小数部分开始的符号(.),称“小数点”,如“231.4”。

    ⒋  量词,用于小的或少的:两三点雨。几点泪水。

    ⒌  一定的位置或限度:地点。起点。极点。居民点。

    ⒍  项,部分,方面:优点。要点。特点。

    ⒎  汉字笔形之一(丶):点画。三点水。

    ⒏  加上点子,引申为修饰:标点。评点。点缀。画龙点睛。

    ⒐  使一点一滴地落下或发出:点种。点射(自动武器有间歇的射击)。点眼药。

    ⒑  一落一起或一触即离的动作:点头。点穴。

    ⒒  引火:点火(亦喻挑起是非,制造事端)。

    ⒓  查对:点数。点名。点卯(旧时称官衙、军伍卯时开始办公、操练,官员查点人数)。

    ⒔  指定,选派:点菜。点将(jiàng )。听众点播。

    ⒕  指示,启发:指点。点拨。

    ⒖  计时的单位:更点(分为五更,一更又分五点)。三更三点。钟点。

    ⒗  污:点污。点辱(使受污辱)。

    ⒘  指正餐以外的暂时充饥,亦指糕饼一类的食物:点心(“心”读轻声)。点补(吃少量的食品解饿。“补”读轻声)。

    ⒙  同“踮”。

    异体字

    汉英互译

    a litter、drop、feature、dot、nod、particle、point、spot

    相关字词

    造字法

    形声:从灬、占声

    English

    dot, speck, spot; point, degree

    按照词语首拼查询
    请使用Ctrl+D进行收藏。
    确认
    请使用Ctrl+D进行收藏。
    确认
    是否确认删除?
    确定 取消