課程課件作業(yè)空chapter7

1復(fù)習(xí)題所謂簡(jiǎn)單路徑是指_____。

A.任何一條邊在這條路徑上不重復(fù)出現(xiàn)

B.任何一個(gè)頂點(diǎn)在這條路徑上不重復(fù)出現(xiàn)

C.這條路徑由一個(gè)頂點(diǎn)序列構(gòu)成，不包含邊

D.這條路徑由一個(gè)邊的序列構(gòu)成，不包含頂點(diǎn)帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則vi的入度等于A中__。

A.第i行非∞的元素之和 B.第i列非∞的元素之和

C.第i行非∞和非0的元素個(gè)數(shù)

D.第i列非∞和非0的元素個(gè)數(shù)2復(fù)習(xí)題在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的_____倍。

A.? B.1 C.2 D.4具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有____條邊才能確保是一個(gè)連通圖。

A.5 B.6 C.7 D.8如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則該圖一定是_____。

A.完全圖 B.連通圖 C.有回路 D.一棵樹(shù)3任何一個(gè)無(wú)向連通圖_____最小生成樹(shù)。

A.只有一個(gè) B.有1或多棵 C.一定有多棵D.可能不存在一個(gè)有向圖G的鄰接表存儲(chǔ)如下圖所示，現(xiàn)按深度優(yōu)先搜索遍歷，從v1出發(fā)，所得到的頂點(diǎn)序列是____。

A.12345 B.12354 C.12453 D.12534復(fù)習(xí)題12345v1v2v3v4v523435544關(guān)鍵路徑是AOE網(wǎng)中_____。

A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑

B.從源點(diǎn)到匯點(diǎn)的最短路徑

C.最長(zhǎng)的回路 D.最短的回路設(shè)有無(wú)向圖G=(V,E)和G’=(V’,E’)，如G’是G的生成樹(shù)，則下面說(shuō)法不正確的是_________。

A.G’是G的連通分量 B.G’是G的無(wú)環(huán)子圖

C.G’是G的子圖

D.G’是G的極小連通子圖且V’=V復(fù)習(xí)題5判斷以下敘述的正確性。

1)n個(gè)頂點(diǎn)的無(wú)向圖最多有n(n-1)條邊。

2)在有向圖中，各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和。

3)如果表示圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定是無(wú)向圖。

4)如果表示有向圖的鄰接矩陣是對(duì)稱矩陣，則該有向圖一定是完全有向圖。

5)從n個(gè)頂點(diǎn)的連通圖中選取n-1條權(quán)值最小的邊，即可構(gòu)成最小生成樹(shù)。

6)強(qiáng)連通圖不能進(jìn)行拓?fù)渑判?。?fù)習(xí)題(錯(cuò))(對(duì))(錯(cuò))()()()6

7)只要無(wú)向網(wǎng)中沒(méi)有權(quán)值相同的邊，其最小生成樹(shù)就是唯一的。

8)只要無(wú)向網(wǎng)中有權(quán)值相同的邊，其最小生成樹(shù)就不可能是唯一的。

9)如果表示某個(gè)圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定不是無(wú)向圖。

10)最短路徑一定是簡(jiǎn)單路徑。

11)在一個(gè)有向圖的拓?fù)湫蛄兄腥繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧<a,b>。

復(fù)習(xí)題()()()()()7

12)無(wú)環(huán)有向圖才能進(jìn)行拓?fù)渑判颉?/p>

13)拓?fù)渑判蛩惴▋H能適用于有向無(wú)環(huán)圖。14)在表示某工程的AOE網(wǎng)中，加速其關(guān)鍵路徑上的任意關(guān)鍵活動(dòng)均可以縮短整個(gè)工程的完成時(shí)間。15)在AOE網(wǎng)中，關(guān)鍵路徑上活動(dòng)的時(shí)間延長(zhǎng)多少，整個(gè)工程的時(shí)間也就隨