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部首 丷总笔画 6

      (1)（动）使开着的物体合拢：～窗户｜把抽屉～上。

      (2)（动）放在里面不放出来：鸟儿～在笼子里。

      (3)（动）（企业等）倒闭；歇业：解放前有一年；镇上～了好几家店铺。

      (4)（名）古代在交通险要或边境出入的地方设置的守卫处所：～口｜～东｜山海～｜嘉峪～｜我的责任就是不让废品混过～去。

      (5)“关上”的简称。参看〖关口〗。

      (6)（名）货物出口和入口收税的地方：海～｜～税。

      (7)（名）比喻重要的转折点或不容易度过的一段时间：难～｜只要突破这一～；就好办了。

      (8)（名）起转折关联作用的部分：机～｜～节｜～键。

      (9)（名）牵连；关系：这些见解至～重要｜人民来信交给有～部门去处理。

      (10)（动）发放或领取（工资）：～饷。

      (11)（Guān）姓。

      [更多解释]

    • 节

      拼音 jié,jiē部首 艹总笔画 5
      jiéjiē

      1. 竹子或草木茎分枝长叶的部分：竹节。节外生枝。

      2. 物体的分段或两段之间连接的部分：关节。两节车厢。

      3. 段落，事项：节节（一段一段地，逐步）。节目。

      4. 中国历法把一年分为二十四段，每段开始的名称：节气。节令。

      5. 纪念日或庆祝宴乐的日子：节日。

      6. 礼度：礼节。

      7. 音调高低缓急的限度：节奏。节拍。节律。

      8. 操守：节操。晚节。变节。高风亮节（高尚的品德和节操）。

      9. 省减，限制：节省。节制。开源节流。

      10. 略去，简略：节选。节录。

      11. 古代出使外国所待的凭证：符节。使节。

      12. 姓。

      1. 〔节骨眼儿〕喻关键的，能起决定性作用的环节或时机（“骨”读轻声）。

      [更多解释]

    • 点

      拼音 diǎn部首 灬总笔画 9

      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. 关节点是什么意思？

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