關(guān)節(jié)點

詞語解釋

1. 量變引起質(zhì)變的臨界點。是兩個不同質(zhì)的事物的界限，事物的度的邊緣。

網(wǎng)絡(luò)解釋

1. 關(guān)節(jié)點
   1. articulation point;articulare;
   2. 在某圖中，若刪除頂點V以及V相關(guān)的邊后，圖的一個連通分量分割為兩個或兩個以上的連通分量，則稱頂點V為該圖的一個關(guān)節(jié)點。一個沒有關(guān)節(jié)點的連通圖稱為重連通圖。
   3. 在重連通圖中，任意一對頂點之間至少存在兩條路徑，則再刪去某個頂點即相關(guān)各邊后也不破壞圖的連通性。若在圖的連通圖上刪去k個節(jié)點才能破壞圖的連通性，則稱K為此圖的連通度。
   4. 他們常常在通信網(wǎng)絡(luò)的圖或航空網(wǎng)中應(yīng)用，K越大，系統(tǒng)越穩(wěn)定，反之，戰(zhàn)爭中若要摧毀敵方的運輸線，只須破壞其運輸網(wǎng)中的關(guān)節(jié)點即可。
   5. 利用深度優(yōu)先搜索便可以求的圖的關(guān)節(jié)點，本由此可判別圖是否重連通。
   6. 從任一點出發(fā)深度優(yōu)先遍歷得到優(yōu)先生成樹，對于樹中任一頂點V而言，其孩子節(jié)點為鄰接點。由深度優(yōu)先生成樹可得出兩類關(guān)節(jié)點的特性：
   7. （1）若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關(guān)節(jié)點。因為圖中不存在連接不同子樹頂點的邊，若刪除此節(jié)點，則樹便成為森林。
   8. （2）若生成樹中某個非葉子節(jié)點V，其某棵子樹與V的祖先節(jié)點無連接，則V為關(guān)節(jié)點。因為刪去v，則其子樹和圖的其它部分被分割開來
   9. low[v] 設(shè)對連通圖G=（V,E）進行先深搜索的先深編號為dfn[v]，產(chǎn)生的先深生成樹為S=（V,T），B是回退邊之集。對每個頂點v，low[v]定義如下
   10. low[v]=Min{dfn[v],Min{low[w]|w是v的一個子女}，Min{dfn[x]|（v，x）是一條回邊}}//dfn數(shù)組記錄頂點的深度優(yōu)先數(shù)
   11. 算法： 求無向圖的雙連通分量
   12. 輸入：連通的無向圖G=( V, E )。L[v]表示關(guān)于v的鄰接表
   13. 輸出：G的所有雙連通分量，每個連通分量由一序列的邊組成。
   14. 1.計算先深編號：對圖進行先深搜索，計算每個結(jié)點v的先深編號dnf[v]，形成先深生成樹S=（V,T）。
   15. 2.計算low[v]：在先深生成樹上按后根順序進行計算每個頂點v的 low[v]， low[v]取下述三個結(jié)點中的最小者：
   16. (1) dfn[v]；
   17. (2) dfn[w]，凡是有回退邊（v,w）的任何結(jié)點w；
   18. (3) low[y]，對v的任何兒子y。
   19. 3.求關(guān)節(jié)點：
   20. (1)樹根是關(guān)節(jié)點，當(dāng)且僅當(dāng)它有兩個或兩個以上的兒子（第一類關(guān)節(jié)點）；
   21. (2)非樹根結(jié)點v是關(guān)節(jié)點當(dāng)且僅當(dāng)v有某個兒子y，使low[y]≥dnf[v]（第二類關(guān)節(jié)點）。
   22. 求雙連通分量的算法――同先深搜索算法（略）