關(guān)節(jié)點(diǎn)與重連通圖(共13張PPT)精選

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

遍歷，每個(gè)頂點(diǎn)的DFN[i]

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

遍歷，每個(gè)頂點(diǎn)的DFN[i]

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

遍歷，每個(gè)頂點(diǎn)的DFN[i]

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

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

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

輸入文件第一行為n，表示有n個(gè)頂點(diǎn)，接下來(lái)是個(gè)n×n的矩陣

輸