圖習(xí)題及參考

1、第7章習(xí)題一、單項(xiàng)選擇題1.在無向圖中定義極點(diǎn)的度為與它有關(guān)系的（）的數(shù)量。A.極點(diǎn)B.邊C.權(quán)D.權(quán)值2.在無向圖中定義極點(diǎn)vi與vj之間的路徑為從vi抵達(dá)vj的一個(gè)（）。A.極點(diǎn)序列B.邊序列C.權(quán)值總和D.邊的條數(shù)3.圖的簡單路徑是指（）不重復(fù)的路徑。A.權(quán)值B.極點(diǎn)C.邊D.邊與極點(diǎn)均4.設(shè)無向圖的極點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)5.n個(gè)極點(diǎn)的連通圖起碼有（）條邊。A.n-1B.nC.n+1D.06.在一個(gè)無向圖中，全部極點(diǎn)的度數(shù)之和等于全部邊數(shù)的()倍。A.3B.2C.1D.1/27.若采納毗鄰矩陣法儲(chǔ)存一個(gè)n個(gè)極

2、點(diǎn)的無向圖，則該毗鄰矩陣是一個(gè)()。A.上三角矩陣B.稀少矩陣C.對(duì)角矩陣D.對(duì)稱矩陣8.圖的深度優(yōu)先搜尋近似于樹的（）序次遍歷。A.先根B.中根C.后根D.層次9.圖的廣度優(yōu)先搜尋近似于樹的（）序次遍歷。A.先根B.中根C.后根D.層次10.在用Kruskal算法求解帶權(quán)連通圖的最?。ù鷥r(jià)）生成樹時(shí)，選擇權(quán)值最小的邊的原則是該邊不可以在圖中構(gòu)成（）。A.重邊B.有向環(huán)C.回路D.權(quán)值重復(fù)的邊11.在用Dijkstra算法求解帶權(quán)有向圖的最短路徑問題時(shí)，要求圖中每條邊所帶的權(quán)值一定是（）。A.非零B.非整C.非負(fù)D.非正12.設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個(gè)圖，假如V1V2，

3、E1E2，則稱（）。A.G1是G2的子圖B.G2是G1的子圖C.G是G的連通重量D.G是G的連通重量122113.有向圖的一個(gè)極點(diǎn)的度為該極點(diǎn)的（）。A.入度B.出度C.入度與出度之和D.(入度出度)214.一個(gè)連通圖的生成樹是包括圖中全部極點(diǎn)的一個(gè)（）子圖。A.極小B.連通C.極小連通D.無環(huán)15.n(n1)個(gè)極點(diǎn)的強(qiáng)連通圖中起碼含有（）條有向邊。A.n-1B.nn(n-1)/2D.n(n-1)16.在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊必定包括在G的（）生成樹中。A.某個(gè)最小B.任何最小C.廣度優(yōu)先D.深度優(yōu)先17.關(guān)于擁有e條邊的無向圖，它的毗鄰表中有（）個(gè)結(jié)點(diǎn)。A.e-1B.eC.2(e-

4、1)D.2e18.關(guān)于以下圖的帶權(quán)有向圖，從極點(diǎn)1到極點(diǎn)5的最短路徑為（）。,4,5B.1,2,3,5C.1,4,3,5D.1,2,4,3,516492315283519.一個(gè)有n個(gè)極點(diǎn)和n條邊的無向圖必定是（）。A.連通的B.不連通的C.無環(huán)的D.有環(huán)的20.關(guān)于有向圖，其毗鄰矩陣表示比毗鄰表表示更易于（）。A.求一個(gè)極點(diǎn)的度B.求一個(gè)極點(diǎn)的毗鄰點(diǎn)C.進(jìn)行圖的深度優(yōu)先遍歷D.進(jìn)行圖的廣度優(yōu)先遍歷21.與毗鄰矩陣對(duì)比，毗鄰表更合適于儲(chǔ)存（）圖。A.無向B.連通C.稀少D.濃密圖22.為了實(shí)現(xiàn)圖的廣度優(yōu)先遍歷，BFS算法使用的一個(gè)協(xié)助數(shù)據(jù)結(jié)構(gòu)是（）。A.棧B.行列C.二叉樹D.樹二、填空題1.用

5、毗鄰矩陣儲(chǔ)存圖，占用儲(chǔ)存空間數(shù)與圖中極點(diǎn)個(gè)數(shù)_關(guān)，與邊數(shù)_關(guān)。n(n0)個(gè)極點(diǎn)的無向圖最多有_條邊，最罕有_條邊。3.n(n0)個(gè)極點(diǎn)的連通無向圖最罕有_條邊。010，則圖G必定是_向圖。4.若3個(gè)極點(diǎn)的圖G的毗鄰矩陣為1000105.n(n0)個(gè)極點(diǎn)的無向圖中極點(diǎn)的度的最大值為_。(n0)個(gè)極點(diǎn)的連通無向圖的生成樹起碼有_條邊。7.在使用Kruskal算法結(jié)構(gòu)連通網(wǎng)絡(luò)的最小生成樹時(shí)，只有當(dāng)一條候選邊的兩個(gè)端點(diǎn)不在同一個(gè)上，才有可能加入到生成樹中。_求解帶權(quán)連通圖最小生成樹的Prim算法合適于_圖的情況，而Kruskal算法合適于_圖的情況。三、判斷題1.一個(gè)圖的子圖能夠是空?qǐng)D，極點(diǎn)個(gè)數(shù)為0。

6、儲(chǔ)存圖的毗鄰矩陣中，矩陣元素個(gè)數(shù)不只與圖的極點(diǎn)個(gè)數(shù)有關(guān)，并且與圖的邊數(shù)也有關(guān)。對(duì)一個(gè)連通圖進(jìn)行一次深度優(yōu)先搜尋（depthfirstsearch）能夠遍訪圖中的全部極點(diǎn)。4.有n(n1)個(gè)極點(diǎn)的無向連通圖最罕有n-1條邊。假如無向圖中各個(gè)極點(diǎn)的度都大于2，則該圖中必有回路。假如有向圖中各個(gè)極點(diǎn)的度都大于2，則該圖中必有回路。圖的廣度優(yōu)先搜尋（breadthfirstsearch）算法不是遞歸算法。8.有n個(gè)極點(diǎn)、e條邊的帶權(quán)有向圖的最小生成樹一般由n個(gè)極點(diǎn)和n-1條邊構(gòu)成。9.關(guān)于一個(gè)邊上權(quán)值隨意的帶權(quán)有向圖，使用Dijkstra算法能夠求一個(gè)極點(diǎn)到其余各個(gè)極點(diǎn)的最短路徑。有回路的有向圖不可以

7、達(dá)成拓?fù)渑判?。?duì)任何用極點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（AOV網(wǎng)）進(jìn)行拓?fù)渑判虻慕Y(jié)果都是獨(dú)一的。用邊表示活動(dòng)的網(wǎng)絡(luò)（AOE網(wǎng)）的重點(diǎn)路徑是指從源點(diǎn)到終點(diǎn)的路徑長度最長的路徑。關(guān)于AOE網(wǎng)絡(luò)，加快任一重點(diǎn)活動(dòng)就能使整個(gè)工程提早達(dá)成。關(guān)于AOE網(wǎng)絡(luò)，任一重點(diǎn)活動(dòng)延緩將致使整個(gè)工程延緩達(dá)成。在AOE網(wǎng)絡(luò)中，可能同時(shí)存在幾條重點(diǎn)路徑，稱全部重點(diǎn)路徑都需經(jīng)過的有向邊為橋。假如加快這樣的橋上的重點(diǎn)活動(dòng)就能使整個(gè)工程提早達(dá)成。用毗鄰矩陣儲(chǔ)存一個(gè)圖時(shí)，在不考慮壓縮儲(chǔ)存的狀況下，所占用的儲(chǔ)存空間大小只與圖中的極點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)沒關(guān)。毗鄰表只好用于有向圖的儲(chǔ)存，毗鄰矩陣關(guān)于有向圖和無向圖的儲(chǔ)存都合用。毗鄰矩陣只合用于濃

8、密圖（邊數(shù)靠近于極點(diǎn)數(shù)的平方），毗鄰表合用于稀少圖（邊數(shù)遠(yuǎn)小于極點(diǎn)數(shù)的平方）儲(chǔ)存無向圖的毗鄰矩陣是對(duì)稱的，所以只需儲(chǔ)存毗鄰矩陣的下（上）三角部分就能夠了。連通重量是無向圖中的極小連通子圖。在AOE網(wǎng)絡(luò)中必定只有一條重點(diǎn)路徑。四、運(yùn)算題1.設(shè)連通圖G以下圖。試畫出該圖對(duì)應(yīng)的毗鄰矩陣表示，并給出對(duì)它履行從極點(diǎn)V開始的廣度優(yōu)先搜0索的結(jié)果。V0V2V1V5V4V3V7V8V62.設(shè)連通圖G以下圖。試畫出該圖及其對(duì)應(yīng)的毗鄰表表示，并給出對(duì)它履行從V開始的深度優(yōu)先搜尋0的結(jié)果。V0V2V1V5V4V3V7V8V6關(guān)于以下圖的有向圖，試寫出：從極點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜尋所獲得的深度優(yōu)先生成樹；從極點(diǎn)出發(fā)進(jìn)行

9、廣度優(yōu)先搜尋所獲得的廣度優(yōu)先生成樹4.設(shè)有向圖G以下圖。試畫出從極點(diǎn)V開始進(jìn)行深度優(yōu)先搜尋和廣度優(yōu)先搜尋獲得的DFS生成叢林和0BFS生成叢林。V0V3V12VV4V56V7V設(shè)有一個(gè)連通網(wǎng)絡(luò)以下圖。試按以下格式，應(yīng)用Kruskal算法給出在結(jié)構(gòu)最小生成樹過程中次序選出的各條邊。6061182735342645(始極點(diǎn)號(hào)，終極點(diǎn)號(hào)，權(quán)值)(,)(,)(,)(,)(,)設(shè)有一個(gè)連通網(wǎng)絡(luò)以下圖。試采納prim算法從極點(diǎn)0開始結(jié)構(gòu)最小生成樹。（寫出加入生成樹極點(diǎn)會(huì)合S和選擇邊Edge的次序）901172567114853S:極點(diǎn)號(hào)Edge:(極點(diǎn)，極點(diǎn)，權(quán)值)0(，)0(，)0(，)0(，)0(，)

10、0有八項(xiàng)活動(dòng),每項(xiàng)活動(dòng)要求的前驅(qū)以下:活動(dòng)A0A1A2A3A4A5A6A7前驅(qū)無前驅(qū)A0A0A0,A2A1A2,A4A3A5,A6試畫出相應(yīng)的AOV網(wǎng)絡(luò),并給出一個(gè)拓?fù)渑判蛐蛄小?2)試改變某些結(jié)點(diǎn)的編號(hào),使得用毗鄰矩陣表示該網(wǎng)絡(luò)時(shí)全部對(duì)角線以下的元素全為0。試對(duì)下列圖所示的AOE網(wǎng)絡(luò)這個(gè)工程最早可能在什么時(shí)間結(jié)束。確立哪些活動(dòng)是重點(diǎn)活動(dòng)。畫出由全部重點(diǎn)活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加快可使整個(gè)工程提早達(dá)成。210426141961511553設(shè)帶權(quán)有向圖以下圖。試采納Dijkstra算法求從極點(diǎn)0到其余各極點(diǎn)的最短路徑和最短路徑長度。8014147292534第7章習(xí)題參照答案一、單項(xiàng)選擇題參照

11、答案：1.B5.A6.B7.D11.C15.B16.A18.D21.C22.B二、填空題參照答案：1.有,無2.n(n-1)/2,03.n-14.有5.(n-1)6.n-17.連通重量8.濃密，稀少三、判斷題參照答案：1.否2.否3.是4.是5.是6.否7.是8.否9.否10.是11.否12.是13.否14.是15.是16.是17.否18.是19.是20.否21.否四、運(yùn)算題參照答案：1.圖G對(duì)應(yīng)的毗鄰矩陣為011100000100110000100101000111000110G.Edge010000000001000000000100011000100100000000100履行廣度優(yōu)先搜

12、尋的結(jié)果為V0V1V3V2V4V7V6V5V8，搜尋結(jié)果不獨(dú)一。圖G對(duì)應(yīng)的毗鄰表為：0V01321V10312V20353V3012674V415V526V63787V7368V86履行深度優(yōu)先搜尋的結(jié)果為：V0V1V4V3V6V7V8V2V5，搜尋結(jié)果不獨(dú)一。以極點(diǎn)為根的深度優(yōu)先生成樹（不獨(dú)一）：以極點(diǎn)為根的廣度優(yōu)先生成樹：4.深度優(yōu)先生成叢林為：V0廣度優(yōu)先生成叢林為：V0V3VV2311V2VV4VV4V5V7V5VV667V應(yīng)用Kruskal算法次序選出最小生成樹的各條邊為：(始極點(diǎn)號(hào)，終極點(diǎn)號(hào)，權(quán)值)0(0,3,1)112(2,5,2)(1,4,3)35342(3,5,4)(3,4,

13、5)45采納prim算法從極點(diǎn)0開始結(jié)構(gòu)最小生成樹的過程：S:極點(diǎn)號(hào)Edge:(極點(diǎn)，極點(diǎn)，權(quán)值)0(0，1，9)0,1(1，3，5)0,1,3(1，2，7)0,1,3,2(2，4，6)0,1,3,2,4(2，5，7)0,1,3,2,4,509172567345相應(yīng)的AOV網(wǎng)絡(luò)為：A1A2A0A3A4A7A5A6一個(gè)拓?fù)渑判蛐蛄袨椋篈0,A1,A4,A2,A5,A3,A6,A7。注意：拓?fù)渑判蚪Y(jié)果不獨(dú)一。按拓?fù)溆行虻男虼螌?duì)全部極點(diǎn)重新編號(hào)：原編號(hào)A0A1A4A2A5A3A6A7新編號(hào)A0A1A2A3A4A5A6A7相應(yīng)毗鄰矩陣為：01234567010101000001000001000010

14、002Edge0000110030000000140000001050000000160000000077.針對(duì)下列圖所示的AOE網(wǎng)絡(luò)210246141961511553各極點(diǎn)（事件）的最早可能開始時(shí)間Ve(i)和最遲同意開始時(shí)間Vl(i)參看下表：極點(diǎn)123456Ve01915293843Vl01915373843各邊（活動(dòng)）的最早可能開始時(shí)間Ee(k)和最遲同意開始時(shí)間El(k)參看下表：邊Ee00151915192938El170151927273738假如活動(dòng)k的最早可能開始時(shí)間Ee(k)與最遲同意開始時(shí)間El(k)相等，則該活動(dòng)是重點(diǎn)活動(dòng)。此題的重點(diǎn)活動(dòng)為,，它們構(gòu)成重點(diǎn)路徑。這些重點(diǎn)活動(dòng)中任一個(gè)提早達(dá)成，整個(gè)工程就能提早達(dá)成。整個(gè)工程最早在43天達(dá)成。由重點(diǎn)活動(dòng)構(gòu)成的102211941511358.帶權(quán)有向圖以下圖：8014147292354AOV網(wǎng)絡(luò)以下圖。4665應(yīng)用Dijkstra算法求從極點(diǎn)V到其余各極點(diǎn)的最短路徑Path和最短路徑長度Len的步驟以下：0步驟V0V1V2V