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

基本解釋

量變引起質(zhì)變的臨界點(diǎn)。是兩個(gè)不同質(zhì)的事物的界限，事物的度的邊緣。

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

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

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