漢語國學 漢語國學
簡體 繁體

關節點

(关节点)

詞語釋義

基本解釋

關節點 · 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

  1. ①
    閉,合攏。
  2. ②
    拘禁。
  3. ③
    古代在險要地方或國界設立的守衛處所。
  4. ④
    徵收進出口貨稅的機構。
  5. ⑤
    重要的轉折點,不易度過的時機。
  6. ⑥
    牽連,聯屬。
  7. ⑦
    舊指發給或支領薪餉。
  8. ⑧
    姓。
查看詳情

jié

  1. ①
    竹子或草木莖分枝長葉的部分。
  2. ②
    物體的分段或兩段之間連接的部分。
  3. ③
    段落,事項。
  4. ④
    中國曆法把一年分爲二十四段,每段開始的名稱。
  5. ⑤
    紀念日或慶祝宴樂的日子。
  6. ⑥
    禮度。
  7. ⑦
    音調高低緩急的限度。
  8. ⑧
    操守。
  9. ⑨
    省減,限制。
  10. ⑩
    略去,簡略。
  11. ⑪
    古代出使外國所待的憑證。
  12. ⑫
    姓。
其他讀音(1)

jiē

  1. 〔~骨眼兒〕喻關鍵的,能起決定性作用的環節或時機(“骨”讀輕聲)。
查看詳情

diǎn

  1. ①
    細小的痕跡或物體。
  2. ②
    幾何學上指沒有長、寬、厚而只有位置的幾何圖形;兩條線相交處或線段的兩端。
  3. ③
    數學上表示小數部分開始的符號(。),稱“小數點”,如“231。4”。
  4. ④
    量詞,用於小的或少的。
  5. ⑤
    一定的位置或限度。
  6. ⑥
    項,部分,方面。
  7. ⑦
    漢字筆形之一(丶)。
  8. ⑧
    加上點子,引申爲修飾。
  9. ⑨
    使一點一滴地落下或發出。
  10. ⑩
    一落一起或一觸即離的動作。
  11. ⑪
    引火。
  12. ⑫
    查對。
  13. ⑬
    指定,選派。
  14. ⑭
    指示,啓發。
  15. ⑮
    計時的單位。
  16. ⑯
    污。
  17. ⑰
    指正餐以外的暫時充飢,亦指糕餅一類的食物。
  18. ⑱
    同“踮”。
其他讀音(1)

dian

  1. ①
    點 dian。
  2. ②
    ——“打點”( dǎdian ):收拾;賄賂。
  3. ③
    另見 diǎn。
查看詳情