課程課件作業(yè)chapter7答案

1復(fù)習題所謂簡單路徑是指_____。

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

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

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

D.這條路徑由一個邊的序列構(gòu)成，不包含頂點注釋：對于A.，考慮簡單回路中任何一條邊不重復(fù)出現(xiàn)，但簡單回路不是簡單路徑，因為前者不滿足簡單路徑中“頂點不重復(fù)出現(xiàn)”的要求。帶權(quán)有向圖G用鄰接矩陣A存儲，則vi的入度等于A中__。

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

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

D.第i列非∞和非0的元素個數(shù)注釋:

有些有向網(wǎng)的鄰接矩陣定義中，對角線的元素全部定義為0。BD2復(fù)習題在一個無向圖中，所有頂點的度之和等于邊數(shù)的_____倍。

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

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

A.完全圖 B.連通圖 C.有回路 D.一棵樹CAB3任何一個無向連通圖_____最小生成樹。

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

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

A.從源點到匯點的最長路徑

B.從源點到匯點的最短路徑

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

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

C.G’是G的子圖

D.G’是G的極小連通子圖且V’=V注釋：考慮帶環(huán)的無向連通圖。復(fù)習題AA5判斷以下敘述的正確性。

1)n個頂點的無向圖最多有n(n-1)條邊。

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

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

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

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

6)強連通圖不能進行拓撲排序。復(fù)習題()()()()()()6注釋:如果表示圖的鄰接矩陣是對稱矩陣，則該圖可以是以下類型無向圖有向完全圖或以下兩種形式的有向非完全圖，其特點是如果圖中頂點Vi到Vj有弧與之相關(guān)聯(lián)，則必有一條從Vj到Vi的弧。還可以找出其他形式的圖嗎？……0120127

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

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

9)如果表示某個圖的鄰接矩陣是對稱矩陣，則該圖一定不是無向圖。

10)最短路徑一定是簡單路徑。

11)在一個有向圖的拓撲序列中若頂點a在頂點b之前，則圖中必有一條弧<a,b>。

復(fù)習題()()()()()8注釋:對于前頁的第7、8題，可以考慮以下兩個無向網(wǎng)的例子下面無向網(wǎng)中有權(quán)值相同的邊，可以生成不同的最小生成樹。教材p.174上圖7.16中的無向網(wǎng)中有權(quán)值相同的邊，可是只能生成唯一的最小生成樹。綜合1、2的情形，可以看出可能生成不同的最小生成樹的原因是因為無向網(wǎng)中有權(quán)值相同的邊。9

12)無環(huán)有向圖才能進行拓撲排序。

13)拓撲排序算法僅能適用于有向無環(huán)圖。注釋：拓撲排序算法也可適用于有向有環(huán)圖，只是此時輸出的拓撲序列中的頂點個數(shù)小于有向有環(huán)圖中總的頂點數(shù)。

14)在表示某工程的AOE網(wǎng)中，加速其關(guān)鍵路徑上的任意關(guān)鍵活動均可以縮短整個工程的完成時間。

注釋：考慮兩條關(guān)鍵路徑。

15)在AO