關節(jié)點與重連通圖(共13張PPT)精選

關節(jié)點與重連通(liántōng)圖第一頁，共13頁。關節(jié)點如果一個連通圖在刪除了某個(mǒuɡè)頂點u以及與u相連接的邊之后，變成了非連通圖，這個頂點u就稱為關節(jié)點下圖中的頂點2和頂點6就是關節(jié)點5342167第二頁，共13頁。重連通(liántōng)圖一個不含關節(jié)點的連通圖稱為重連通圖對于(duìyú)重連通的無向圖來說，每對頂點之間至少存在兩條路徑連通圖可以用來表示通信網(wǎng)絡系統(tǒng)。為了提高系統(tǒng)的穩(wěn)定性，網(wǎng)絡中不應該有關節(jié)點。第三頁，共13頁。關節(jié)點的判定(pàndìng)如何來判定一個連通圖中是否有關節(jié)點呢？通過考察連通圖的深度(shēndù)優(yōu)先生成樹，可以得出解決此問題的一個方法第四頁，共13頁。關節(jié)點的判定(pàndìng)對于左上圖，若從頂點(dǐngdiǎn)2開始做深度優(yōu)先遍歷，可以得到一棵深度優(yōu)先生成樹，其中的實線邊構成這個深度優(yōu)先樹，虛線邊表示回邊53421672364751第五頁，共13頁。關節(jié)點在深度優(yōu)先生成樹中的某個頂點u，要么是根，要么不是根先討論頂點u是生成樹的根u是關節(jié)點的充要條件是：u有兩棵或者兩棵以上的子樹。判定方法：遍歷過程中做訪問(fǎngwèn)標記。從頂點u相鄰的某個頂點做遍歷，當遍歷結束時，所有頂點都做了訪問(fǎngwèn)標記，則說明u只有一棵子樹，不是關節(jié)點，否則說明u至少有兩棵子樹，是關節(jié)點第六頁，共13頁。關節(jié)點另一種情況，u不是深度遍歷的根結點(jiédiǎn)假設v是u的一個孩子，則u是關節(jié)點的充要條件是：在v或者v的子孫結點(jiédiǎn)和u的祖先結點(jiédiǎn)之間不存在任何回邊如何來判定這個充要條件？引入深度優(yōu)先數(shù)和最低深度優(yōu)先數(shù)的概念第七頁，共13頁。深度(shēndù)優(yōu)先數(shù)深度優(yōu)先數(shù)是指在按照某種深度優(yōu)先遍歷的過程中，依次給每個頂點標個號，用DFN[u]表示按照右圖從頂點1開始(kāishǐ)做

遍歷，每個頂點的DFN[i]

是多少呢？2364751第八頁，共13頁。關節(jié)點的判定(pàndìng)深度(shēndù)優(yōu)先數(shù)一個不含關節(jié)點的連通圖稱為重連通圖先討論頂點u是生成樹的根從頂點u相鄰的某個頂點做遍歷，當遍歷結束時，所有頂點都做了訪問(fǎngwèn)標記，則說明u只有一棵子樹，不是關節(jié)點，否則說明u至少有兩棵子樹，是關節(jié)點重連通(liántōng)圖精品(jīnɡpǐn)課件！如何來判定一個連通圖中是否有關節(jié)點呢？深度優(yōu)先數(shù)是指在按照某種深度優(yōu)先遍歷的過程中，依次給每個頂點標個號，用DFN[u]表示如何來判定這個充要條件？關節(jié)點與重連通(liántōng)圖一個不含關節(jié)點的連通圖稱為重連通圖最低深度優(yōu)先數(shù)用L[u]表示，定義(dìngyì)如下：深度(shēndù)優(yōu)先數(shù)另一種情況，u不是深度遍歷的根結點(jiédiǎn)關節(jié)點與重連通(liántōng)圖深度優(yōu)先數(shù)是指在按照某種深度優(yōu)先遍歷的過程中，依次給每個頂點標個號，用DFN[u]表示先討論頂點u是生成樹的根假設v是u的一個孩子，則u是關節(jié)點的充要條件是：在v或者v的子孫結點(jiédiǎn)和u的祖先結點(jiédiǎn)之間不存在任何回邊精品(jīnɡpǐn)課件！最低深度優(yōu)先數(shù)用L[u]表示，定義(dìngyì)如下：深度(shēndù)優(yōu)先數(shù)從頂點u相鄰的某個頂點做遍歷，當遍歷結束時，所有頂點都做了訪問(fǎngwèn)標記，則說明u只有一棵子樹，不是關節(jié)點，否則說明u至少有兩棵子樹，是關節(jié)點按照右圖從頂點1開始(kāishǐ)做

遍歷，每個頂點的DFN[i]

是多少呢？按照右圖從頂點1開始(kāishǐ)做

遍歷，每個頂點的DFN[i]

是多少呢？連通圖可以用來表示通信網(wǎng)絡系統(tǒng)。從頂點u相鄰的某個頂點做遍歷，當遍歷結束時，所有頂點都做了訪問(fǎngwèn)標記，則說明u只有一棵子樹，不是關節(jié)點，否則說明u至少有兩棵子樹，是關節(jié)點在深度優(yōu)先生成樹中的某個頂點u，要么是根，要么不是根另一種情況，u不是深度遍歷的根結點(jiédiǎn)先討論頂點u是生成樹的根如何來判定這個充要條件？假設v是u的一個孩子，則u是關節(jié)點的充要條件是：在v或者v的子孫結點(jiédiǎn)和u的祖先結點(jiédiǎn)之間不存在任何回邊最低深度(shēndù)優(yōu)先數(shù)最低深度優(yōu)先數(shù)用L[u]表示，定義(dìngyì)如下：

DFN[u]min{L[v]|在生成樹中，v是u的孩子}min{DFN[v]|在生成樹中，v是u的雙親或（u，v）是一條回邊}L[u]=min第九頁，共13頁。關節(jié)點在u不是深度優(yōu)先生成樹的根的前提條件下，若u存在一個(yīɡè)孩子v，使得DFN[u]<=L[v]成立，則u是關節(jié)點第十頁，共13頁。精品(jīnɡpǐn)課件！第十一頁，共13頁。精品(jīnɡpǐn)課件！第十二頁，共13頁。練習(liànxí)關節(jié)點（key.c/key.in/key.out）

在一個無向連通圖中，輸入這個連通圖的鄰接矩陣形式，判斷這個無向圖中是否存在關節(jié)點，如果不存在，則輸出“safe”，如果存在，則按照頂點編號由小到大輸出關節(jié)點

輸入文件第一行為n，表示有n個頂點，接下來是個n×n的矩陣

輸