1、已知帶權(quán)連通無向圖G=（V，E），其中V={，,,,,,}，E={(,)10,(,)2,(,)2,(,)11,(,)1,(,)4,(,)6,(,)7,(,)3}（注：頂點(diǎn)偶對括號外的數(shù)據(jù)表示邊上的權(quán)值），從源點(diǎn)到頂點(diǎn)的最短路徑上經(jīng)過的頂點(diǎn)序列是（）。

• A：,,,
• B：,,,,
• C：,,,,
• D：,,,,,

解析

在這里插入圖片描述

題干內(nèi)容所述的圖G如上圖所示。A，B，C，D對應(yīng)的路徑長度分別為18，13，15，24。應(yīng)用Dijkstra算法求出最短路徑為B所示路徑。

答案：B

2、下面的（）方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）。

Ⅰ、深度優(yōu)先遍歷
Ⅱ、拓?fù)渑判?br> Ⅲ、求最短路徑
Ⅳ、求關(guān)鍵路徑

• A：Ⅰ、Ⅱ、Ⅳ
• B：Ⅰ、Ⅲ、Ⅳ
• C：Ⅰ、Ⅱ、Ⅲ
• D：全部可以

解析

使用深度優(yōu)先遍歷，若從有向圖上的某個(gè)頂點(diǎn)u出發(fā)，在DFS(u)結(jié)束之前出現(xiàn)一條從頂點(diǎn)v到u的邊，由于v在生成樹上是u的子孫，則圖中必定存在包含u和v的環(huán)，因此深度優(yōu)先遍歷可以檢測一個(gè)有向圖是否有環(huán)。

拓?fù)渑判驎r(shí)，當(dāng)某頂點(diǎn)不為任何邊的頭時(shí)才能加入序列，存在環(huán)時(shí)環(huán)中的頂點(diǎn)一直是某條邊的頭，不能加入拓?fù)湫蛄?。也就是說，還存在無法找到下一個(gè)可以加入拓?fù)湫蛄械捻旤c(diǎn)，則說明此圖存在回路。

求最短路徑是允許圖有環(huán)的。

關(guān)鍵路徑能否判斷一個(gè)圖有環(huán)，則存在一些爭議。關(guān)鍵路徑本身雖然不允許有環(huán)，但求關(guān)鍵路徑的算法本身無法判斷是否有環(huán)，判斷是否有環(huán)是求關(guān)鍵路徑的第一步——拓?fù)渑判颉?/p>

答案：A

3、若一個(gè)有向圖的頂點(diǎn)不能排在一個(gè)拓?fù)湫蛄兄?，則可判定該有向圖（）。

• A：是一個(gè)有根的有向圖
• B：是一個(gè)強(qiáng)連通圖
• C：含有多個(gè)入度為0的頂點(diǎn)
• D：含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量

解析

若不存在拓?fù)渑判?，則表示圖中必定存在回路，該回路構(gòu)成一個(gè)強(qiáng)連通分量（頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量中必然存在回路）。

答案：D

4、以下關(guān)于拓?fù)渑判虻恼f法中，錯(cuò)誤的是（）。

Ⅰ、若某有向圖存在環(huán)路，則該有向圖一定不存在拓?fù)渑判?br> Ⅱ、在拓?fù)渑判蛩惴ㄖ袨闀捍嫒攵葹榱愕捻旤c(diǎn)，可以使用棧，也可以使用隊(duì)列
Ⅲ、若有向圖的拓?fù)溆行蛐蛄形ㄒ唬瑒t圖中每個(gè)頂點(diǎn)的入度和出度最多為1

• A：Ⅰ、Ⅲ
• B：Ⅱ、Ⅲ
• C：Ⅱ
• D：Ⅲ

解析

Ⅰ中，對于一個(gè)存在環(huán)路的有向圖，使用拓?fù)渑判蛩惴ㄟ\(yùn)行后，肯定會出現(xiàn)有環(huán)的子圖，在此環(huán)中無法再找到入度為0的結(jié)點(diǎn)，拓?fù)渑判蛞簿瓦M(jìn)行不下去。

Ⅱ中，注意，若兩個(gè)結(jié)點(diǎn)之間不存在祖先或子孫關(guān)系，則它們在拓?fù)湫蛄兄械年P(guān)系是任意的（即前后關(guān)系任意），因此使用棧和隊(duì)列都可以，因?yàn)檫M(jìn)棧或隊(duì)列的都是入度為0的結(jié)點(diǎn)，此時(shí)入度為0的所有結(jié)點(diǎn)是沒有關(guān)系的。

Ⅲ中，若拓?fù)溆行蛐蛄形ㄒ?，則很自然地讓人聯(lián)想到一個(gè)線性的有向圖（錯(cuò)誤），下圖的拓?fù)湫蛄幸彩俏ㄒ坏?，但度卻不滿足條件。

在這里插入圖片描述

答案：D

5、若一個(gè)有向圖的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則判定該有向圖（）。

• A：含有多個(gè)出度為0的頂點(diǎn)
• B：是個(gè)強(qiáng)連通圖
• C：含有多個(gè)入度為0的頂點(diǎn)
• D：含有頂點(diǎn)數(shù)大于1的強(qiáng)連通分量

解析

一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，表明其中存在一個(gè)頂點(diǎn)數(shù)目大于1的回路，該回路構(gòu)成一個(gè)強(qiáng)連通分量，從而答案選D。

答案：D

6、下圖所示有向圖的所有拓?fù)湫蛄泄灿校ǎ﹤€(gè)。

在這里插入圖片描述

• A：4
• B：6
• C：5
• D：7

解析

本圖的拓?fù)渑判蛐蛄杏蠥BCFDEG，ABCDFEG，ABCDEFG，ABDCFEG和ABDCEFG。

答案：C

7、若一個(gè)人有向圖具有有序的拓?fù)渑判蛐蛄?，則它的鄰接矩陣必定為（）。

• A：對稱
• B：稀疏
• C：三角
• D：一般

解析

對有向圖中的頂點(diǎn)適當(dāng)?shù)鼐幪?，使其鄰接矩陣為三角矩陣且主對角元素全為零的充分必要條件是，該有向圖可以進(jìn)行拓?fù)渑判颉?/p>

若一個(gè)有向圖的鄰接矩陣為三角矩陣（對角線上元素為0），則圖中必不存在環(huán)，因此其拓?fù)湫蛄斜厝淮嬖凇?/p>

答案：C

8、下列關(guān)于圖的說法中，正確的是（）。

Ⅰ、有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中1的個(gè)數(shù)
Ⅱ、無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣
Ⅲ、在圖G的最小生成樹中，某條邊的權(quán)值可能會超過未選邊的權(quán)值
Ⅳ、若有向無環(huán)圖的拓?fù)湫蛄形ㄒ?，則可以唯一確定該圖

• A：Ⅰ、Ⅱ和Ⅲ
• B：Ⅲ和 Ⅳ
• C：Ⅲ
• D：Ⅳ

解析

有向圖鄰接矩陣的第V行中1的個(gè)數(shù)是頂點(diǎn)V的出度，而有向圖中頂點(diǎn)的度為入度與出度之和，Ⅰ錯(cuò)。

無向圖的鄰接矩陣一定是對稱矩陣，但當(dāng)有向圖中任意兩個(gè)頂點(diǎn)之間有邊相連，且是兩條方向相反的有向邊（無向圖也可視為有兩條方向相反的有向邊的特殊有向圖）時(shí)，有向圖的鄰接矩陣也是一個(gè)對稱矩陣，Ⅱ錯(cuò)。

最小生成樹中的n-1條邊并不能保證是圖中權(quán)值最小的n-1條邊，因?yàn)闄?quán)值最小的n-1條邊并不一定能使圖連通。在下圖中，左圖的最小生成樹如右圖所示，權(quán)值為3的邊并不在其最小生成樹中。

在這里插入圖片描述

在這里插入圖片描述

答案：C

9、若某帶權(quán)圖為G=（V，E），其中V={,,,,,,,,,}，E={<,>5,<,>6,<,>3,<,>6,<,>3,<,>3,<,>1,<,>4,<,>4,<,>2,<,>4,<,>5,<,>2,<,>2}（注：邊括號外的數(shù)據(jù)表示邊上的權(quán)值），則G的關(guān)鍵路徑的長度為（）。

• A：19
• B：20
• C：21
• D：22

解析

畫出題目所表示的圖如下，可得到關(guān)鍵路徑的長度為21.圖中所示的兩條路徑都是關(guān)鍵路徑。

在這里插入圖片描述

答案：C

10、下面關(guān)于求關(guān)鍵路徑的說法中，不正確的是（）。

• A：求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的
• B：一個(gè)事件的最早發(fā)生時(shí)間與以該事件為始的弧的活動的最早開始時(shí)間相同
• C：一個(gè)事件的最遲發(fā)生時(shí)間是以該事件為尾的弧的活動的最遲開始時(shí)間與該活動的持續(xù)時(shí)間的差
• D：關(guān)鍵活動一定位于關(guān)鍵路徑上

解析

一個(gè)事件的最遲發(fā)生時(shí)間等于Min{以該事件為尾的弧的活動的最遲開始時(shí)間，最遲結(jié)束時(shí)間與該活動的持續(xù)時(shí)間的差}。

答案：C

學(xué)海無涯苦作舟