1、精選優質文檔-傾情為你奉上運籌學第八章圖與網絡分析習題1.思考題() 解釋下列名詞，并說明相互之間的區別與聯系：頂點，相鄰，關聯邊；環，多重邊，簡單圖；鏈，初等鏈；圈，初等圈，簡單拳；回路，初等路；節點的次，懸掛點，孤立點；）連通圖，連同分圖，支撐子圖；有向圖，基礎圖，賦權圖。子圖，部分圖，真子圖() 通常用記號（，）表示一個圖，解釋及的涵義及這個表達式的涵義() 通常用記號（，）表示一個有向圖，解釋及的涵義及這個表達式的涵義() 圖論中的圖與一般幾何圖形的主要區別是什么？() 試述樹與圖的區別與聯系() 試述 求最短路問題的ijkstra算法的基本思想及其計算步驟() 試述尋求最大流的標號法

2、的步驟與方法() 簡述最小費用最大流的概念及其求解的基本思想和方法() 通常用記號（，）表示一個網絡，試解釋這個表達式的涵義(10) 在最大流問題中，為什么當存在增廣鏈時，可行流不是最大流？(11) 試敘述最小支撐樹、最大流、最短路等問題能解決那些實際問題。2.判斷下列說法是否正確(1) 圖論中的圖是為了研究問題中有哪些對象及對象之間的關系，它與圖的幾何形狀無關。(2) 一個圖G 是樹的充分必要條件是邊數最少的無孤立點的圖。(3) 如果一個圖G從V1到各點的最短路是唯一的，則連接V1到各點的最短路，再去掉重復邊，得到的圖即為最小支撐樹。(4 )圖G的最小支撐樹中從V1到Vn的通路一定是圖G從V

3、1到Vn的最短路。(5) fij=0總是最大流問題的一個可行流。(6 )無孤立點的圖一定是連通圖。(7) 圖中任意兩點之間都有一條簡單鏈，則該圖是一棵樹。(8) 求網絡最大流的問題總可以歸結為求解一個線性規劃問題。(9)在圖中求一點到另一點n的最短路問題總可以歸結為一個整數規劃問題(10) 圖G中的一個點V1總可以看成是G的一個子圖。3.證明：在人數超過2的人群中，總有兩個人在這群人中恰有相同的朋友數。4.已知九個人，和兩個人握過手，各和四個人握過手，各和五個人握過手，各和六個人握過手。證明這九個人中，一定可以找出三個人互相握過手。C7V1V2V3V4V5V6V7V8V9C1C2C3C4C5C

4、6C8C9C10C11C12C13C145用破圈法和避圈法求下圖的部分樹V1V2V3V4V5V6(1)6寫出下面各圖中的頂點數、邊數及頂點的次數，哪些是簡單圖。V1V2V3V4V5(2) 7完全圖n 有多少條邊？8求下列各圖的最小樹（）（）（）（）9.用標號法求下圖中從到各頂點的最短距離V1V2V3V4V5V6V7V8V9V10V11263575213723414316738410在下圖中用標號法求（）從到各頂點的最短距離；（）若從到，走哪一條路最短。V1V2V3V4V5V6V7V8V9433243831232111已知8個村鎮，相互間距離如下表所示,已知1號村鎮離水源最近，為5公里，問從水源

5、經1號村鎮鋪設輸水管道將各村鎮連接起來，應如何鋪設使輸水管道最短（為便于管理和維修，水管要求在各村鎮處分開）。 各村鎮間距離 （單位：公里） 到從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.用標號法求下面網絡的最大流.13. 用標號法求下面網絡的最大流.V1Vt4453342535823 V1Vt(5,6)(9,2)(3,2)(4,1)(3,4)(4,19)(2,3)(1,1)

6、(2)V1Vt(6,6)(10,5)(5,1)(2,3)(7,4)(8,2)(1)14.求下列網絡的最小費用最大流.括號內的兩個數字,前一個是單位流量的費用,后一個是該弧的流量. 運籌學第八章圖與網絡分析習題解答2（1） （2）X（3） （4）X（5） （6）X（7）X（8）（9）（10）6解：圖（）頂點數個；邊數條；每個頂點的次數都為次，是簡單圖。圖（）頂點數個；邊數條；每個頂點的次數v4 ,v5 次，其它各頂點都為次，是簡單圖。7解：完全圖的邊數為條。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,8)為。11