《運(yùn)籌學(xué)》 第八章圖與網(wǎng)絡(luò)分析習(xí)題及 答案.doc

運(yùn)籌學(xué)第八章圖與網(wǎng)絡(luò)分析習(xí)題1.思考題() 解釋下列名詞，并說明相互之間的區(qū)別與聯(lián)系：頂點(diǎn)，相鄰，關(guān)聯(lián)邊；環(huán)，多重邊，簡單圖；鏈，初等鏈；圈，初等圈，簡單拳；回路，初等路；節(jié)點(diǎn)的次，懸掛點(diǎn)，孤立點(diǎn)；）連通圖，連同分圖，支撐子圖；有向圖，基礎(chǔ)圖，賦權(quán)圖。子圖，部分圖，真子圖() 通常用記號(hào)（，）表示一個(gè)圖，解釋及的涵義及這個(gè)表達(dá)式的涵義() 通常用記號(hào)（，）表示一個(gè)有向圖，解釋及的涵義及這個(gè)表達(dá)式的涵義() 圖論中的圖與一般幾何圖形的主要區(qū)別是什么？() 試述樹與圖的區(qū)別與聯(lián)系() 試述 求最短路問題的ijkstra算法的基本思想及其計(jì)算步驟() 試述尋求最大流的標(biāo)號(hào)法的步驟與方法() 簡述最小費(fèi)用最大流的概念及其求解的基本思想和方法() 通常用記號(hào)（，）表示一個(gè)網(wǎng)絡(luò)，試解釋這個(gè)表達(dá)式的涵義(10) 在最大流問題中，為什么當(dāng)存在增廣鏈時(shí)，可行流不是最大流？(11) 試敘述最小支撐樹、最大流、最短路等問題能解決那些實(shí)際問題。2.判斷下列說法是否正確(1) 圖論中的圖是為了研究問題中有哪些對(duì)象及對(duì)象之間的關(guān)系，它與圖的幾何形狀無關(guān)。(2) 一個(gè)圖G 是樹的充分必要條件是邊數(shù)最少的無孤立點(diǎn)的圖。(3) 如果一個(gè)圖G從V1到各點(diǎn)的最短路是唯一的，則連接V1到各點(diǎn)的最短路，再去掉重復(fù)邊，得到的圖即為最小支撐樹。(4 )圖G的最小支撐樹中從V1到Vn的通路一定是圖G從V1到Vn的最短路。(5) fij=0總是最大流問題的一個(gè)可行流。(6 )無孤立點(diǎn)的圖一定是連通圖。(7) 圖中任意兩點(diǎn)之間都有一條簡單鏈，則該圖是一棵樹。(8) 求網(wǎng)絡(luò)最大流的問題總可以歸結(jié)為求解一個(gè)線性規(guī)劃問題。(9)在圖中求一點(diǎn)到另一點(diǎn)n的最短路問題總可以歸結(jié)為一個(gè)整數(shù)規(guī)劃問題(10) 圖G中的一個(gè)點(diǎn)V1總可以看成是G的一個(gè)子圖。3.證明：在人數(shù)超過2的人群中，總有兩個(gè)人在這群人中恰有相同的朋友數(shù)。4.已知九個(gè)人，和兩個(gè)人握過手，各和四個(gè)人握過手，各和五個(gè)人握過手，各和六個(gè)人握過手。證明這九個(gè)人中，一定可以找出三個(gè)人互相握過手。C7V1V2V3V4V5V6V7V8V9C1C2C3C4C5C6C8C9C10C11C12C13C145用破圈法和避圈法求下圖的部分樹V1V2V3V4V5V6(1)6寫出下面各圖中的頂點(diǎn)數(shù)、邊數(shù)及頂點(diǎn)的次數(shù)，哪些是簡單圖。V1V2V3V4V5(2) 7完全圖n 有多少條邊？8求下列各圖的最小樹（）（）（）（）9.用標(biāo)號(hào)法求下圖中從到各頂點(diǎn)的最短距離V1V2V3V4V5V6V7V8V9V10V11263575213723414316738410在下圖中用標(biāo)號(hào)法求（）從到各頂點(diǎn)的最短距離；（）若從到，走哪一條路最短。V1V2V3V4V5V6V7V8V9433243831232111已知8個(gè)村鎮(zhèn)，相互間距離如下表所示,已知1號(hào)村鎮(zhèn)離水源最近，為5公里，問從水源經(jīng)1號(hào)村鎮(zhèn)鋪設(shè)輸水管道將各村鎮(zhèn)連接起來，應(yīng)如何鋪設(shè)使輸水管道最短（為便于管理和維修，水管要求在各村鎮(zhèn)處分開）。 各村鎮(zhèn)間距離 （單位：公里） 到從234567811.52.51.02.02.53.51.521.02.01.03.02.51.832.52.02.52.01.042.51.51.51.053.01.81.560.81.070.51215V1Vt8106108491014181281315612.用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流.13. 用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流.V1Vt4453342535823 V1Vt(5,6)(9,2)(3,2)(4,1)(3,4)(4,19)(2,3)(1,1)(2)V1Vt(6,6)(10,5)(5,1)(2,3)(7,4)(8,2)(1)14.求下列網(wǎng)絡(luò)的最小費(fèi)用最大流.括號(hào)內(nèi)的兩個(gè)數(shù)字,前一個(gè)是單位流量的費(fèi)用,后一個(gè)是該弧的流量. 運(yùn)籌學(xué)第八章圖與網(wǎng)絡(luò)分析習(xí)題解答2（1） （2）X（3） （4）X（5） （6）X（7）X（8）（9）（10）6解：圖（）頂點(diǎn)數(shù)個(gè)；邊數(shù)條；每個(gè)頂點(diǎn)的次數(shù)都為次，是簡單圖。圖（）頂點(diǎn)數(shù)個(gè)；邊數(shù)條；每個(gè)頂點(diǎn)的次數(shù)v4 ,v5 次，其它各頂點(diǎn)都為次，是簡單圖。7解：完全圖的邊數(shù)為條。V1V2V3V4V5V6V7V8V9V10V11（o,0）(v1,2)(v1,6)(v1,3)(v2,7)(v5,8)(v9,14)(V9,12)(v4,10)(v7,11)(v10,15)9解：10解：從到的最短路 V1V2V3V4V5V6V7V8V91（o,0）(v1,4)(v2,7)(V1,3)(V2,6)(V2,7)(V5,6)(V7,8)(V7