1、WinQSB軟件應(yīng)用,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,網(wǎng)絡(luò)中的服務(wù)設(shè)施布局 長虹街道近年新建了11個居民小區(qū)，各小區(qū)的大致位置及相互間的道路距離（單位：100m）如右圖所示，各居民小區(qū)居民數(shù)為：1(3000),2(3500),3(3700),4(5000),5(3000),6(2500),7(2800),8(4500),9(3300),10(4000),11(3500)。試幫助決策：,1,7,10,2,4,8,11,3,5,6,9,4,8,5,5,6,6,4,5,6,6,5,5,4,7,6,8,4,6,7,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,（1）在11個小區(qū)內(nèi)準(zhǔn)備共建一套醫(yī)務(wù)所、郵局、儲蓄所

2、、綜合超市等服務(wù)設(shè)施，應(yīng)建于哪一居民小區(qū)，使對居民總體來說感到方便； 求解問題： 明確目標(biāo)（對居民總體來說感到方便）。即使所有人到服務(wù)設(shè)施設(shè)置小區(qū)走的距離和為最小。 求出所有人到服務(wù)設(shè)施設(shè)置小區(qū)走的距離和的所有可能值 首先求出任意兩點之間的最短距離,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,WINQSB求解最短路問題 新建問題界面,問題類型,網(wǎng)絡(luò)圖節(jié)點 個數(shù),弧的權(quán)數(shù) 是否對稱 （是否是無向圖）,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,網(wǎng)路圖輸入界面,根據(jù)原圖將節(jié)點 放置到適當(dāng)?shù)奈恢?節(jié)點之間連線 并輸入權(quán)數(shù),實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,求解結(jié)果界面,1-9的最短距離,1到其他節(jié)點 的最短距離,實驗三

3、：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,任意兩節(jié)點之間的最短距離表格,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,將上表中的每行數(shù)字分別乘以各小區(qū)人數(shù)得各小區(qū)之間的人數(shù)距離和,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,按列相加得下表求出以各小區(qū)為服務(wù)點的人數(shù)和距離數(shù)乘積之和 其中最小的為285700，所以在小區(qū)8設(shè)置服務(wù)點總體感到滿意,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,(2)電信部門擬將寬帶網(wǎng)鋪設(shè)到各小區(qū)，應(yīng)如何鋪設(shè)最為經(jīng)濟 鋪設(shè)的要求：連通各小區(qū) 如何鋪設(shè)最為經(jīng)濟：經(jīng)過的距離最小 部分圖：圖G1=V1,E1和圖G2=V2,E2,如果V1=V2,E1包含于E2，則稱G1是G2的一個部分圖 樹圖：無圈的連通圖 部分樹：如果G

4、1是G2的部分圖，又是樹圖，則稱G1是G2的部分樹 所以問題實際就是從小區(qū)網(wǎng)絡(luò)圖中找出一個使各小區(qū)連通的部分圖，并且使該部分圖的邊權(quán)數(shù)之和最小-即最小部分樹問題(minimum spanning tree),實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,WINQSB求解最小部分樹問題 新建問題,問題類型,網(wǎng)絡(luò)圖節(jié)點 個數(shù),弧的權(quán)數(shù) 是否對稱 （是否是無向圖）,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,網(wǎng)路圖輸入界面,根據(jù)原圖將節(jié)點 放置到適當(dāng)?shù)奈恢?節(jié)點之間連線 并輸入權(quán)數(shù),實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,求解結(jié)果界面（表格）,最小部分樹的 權(quán)數(shù)之和,最小部分樹的 各條邊,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,求解結(jié)果（圖形）,1,7,10,2,4,8,11,3,5,6,9,4,5,5,6,4,5,5,5,4,4,最小距離總和：4700m,實驗三：圖和網(wǎng)絡(luò)相關(guān)問題分析求解,課堂練習(xí)： 已知有6個村子，相互間道路的距離如下圖所示。擬合建一所小學(xué)，已知A處有小學(xué)生50人，B處40人，C處60人，D處70人，E處70人，F(xiàn)處90人。問小學(xué)應(yīng)建在哪一個村子