關(guān)節(jié)點(diǎn)與重連通圖

1、關(guān)節(jié)點(diǎn)與重連通圖1關(guān)節(jié)點(diǎn)如果一個(gè)連通圖在刪除了某個(gè)頂點(diǎn)u以及與u相連接的邊之后，變成了非連通圖，這個(gè)頂點(diǎn)u就稱為關(guān)節(jié)點(diǎn)下圖中的頂點(diǎn)2和頂點(diǎn)6就是關(guān)節(jié)點(diǎn)53421672重連通圖一個(gè)不含關(guān)節(jié)點(diǎn)的連通圖稱為重連通圖對于重連通的無向圖來說，每對頂點(diǎn)之間至少存在兩條路徑連通圖可以用來表示通信網(wǎng)絡(luò)系統(tǒng)。為了提高系統(tǒng)的穩(wěn)定性，網(wǎng)絡(luò)中不應(yīng)該有關(guān)節(jié)點(diǎn)。3關(guān)節(jié)點(diǎn)的判定如何來判定一個(gè)連通圖中是否有關(guān)節(jié)點(diǎn)呢？通過考察連通圖的深度優(yōu)先生成樹，可以得出解決此問題的一個(gè)方法4關(guān)節(jié)點(diǎn)的判定對于左上圖，若從頂點(diǎn)2開始做深度優(yōu)先遍歷，可以得到一棵深度優(yōu)先生成樹，其中的實(shí)線邊構(gòu)成這個(gè)深度優(yōu)先樹，虛線邊表示回邊53421672364

2、7515關(guān)節(jié)點(diǎn)在深度優(yōu)先生成樹中的某個(gè)頂點(diǎn)u，要么是根，要么不是根先討論頂點(diǎn)u是生成樹的根u是關(guān)節(jié)點(diǎn)的充要條件是：u有兩棵或者兩棵以上的子樹。判定方法：遍歷過程中做訪問標(biāo)記。從頂點(diǎn)u相鄰的某個(gè)頂點(diǎn)做遍歷，當(dāng)遍歷結(jié)束時(shí)，所有頂點(diǎn)都做了訪問標(biāo)記，則說明u只有一棵子樹，不是關(guān)節(jié)點(diǎn)，否則說明u至少有兩棵子樹，是關(guān)節(jié)點(diǎn)6關(guān)節(jié)點(diǎn)另一種情況，u不是深度遍歷的根結(jié)點(diǎn)假設(shè)v是u的一個(gè)孩子，則u是關(guān)節(jié)點(diǎn)的充要條件是：在v或者v的子孫結(jié)點(diǎn)和u的祖先結(jié)點(diǎn)之間不存在任何回邊如何來判定這個(gè)充要條件？引入深度優(yōu)先數(shù)和最低深度優(yōu)先數(shù)的概念7深度優(yōu)先數(shù)深度優(yōu)先數(shù)是指在按照某種深度優(yōu)先遍歷的過程中，依次給每個(gè)頂點(diǎn)標(biāo)個(gè)號，用DFN

3、u表示按照右圖從頂點(diǎn)1開始做遍歷，每個(gè)頂點(diǎn)的DFNi是多少呢？23647518最低深度優(yōu)先數(shù)最低深度優(yōu)先數(shù)用Lu表示，定義如下：DFNuminLv|在生成樹中，v是u的孩子minDFNv|在生成樹中，v是u的雙親或（u，v）是一條回邊Lu=min9關(guān)節(jié)點(diǎn)在u不是深度優(yōu)先生成樹的根的前提條件下，若u存在一個(gè)孩子v，使得DFNu=Lv成立，則u是關(guān)節(jié)點(diǎn)10練習(xí)關(guān)節(jié)點(diǎn)（key.c/key.in/key.out）在一個(gè)無向連通圖中，輸入這個(gè)連通圖的鄰接矩陣形式，判斷這個(gè)無向圖中是否存在關(guān)節(jié)點(diǎn)，如果不存在，則輸出“safe”，如果存在，則按照頂點(diǎn)編號由小到大輸出關(guān)節(jié)點(diǎn)輸入文件第一行為n，表示有n個(gè)頂點(diǎn)，接下來是個(gè)nn的矩陣輸出文件一行，如果無關(guān)節(jié)點(diǎn)，輸出“safe”，如果有，則依次輸出關(guān)節(jié)點(diǎn)編號，每個(gè)關(guān)節(jié)點(diǎn)中