拼音：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]（第二類關節點）。

求雙連通分量的算法――同先深搜索算法（略）