【正文】 （ 4） 再把這 n 個(gè)小樹看成 個(gè)節(jié)點(diǎn)，把（ 3）求得的兩樹之間的距離作為兩節(jié)點(diǎn)之間的權(quán)，再利用最小生成樹的算法得到最小生成樹的各邊。 用破圈法在給定的圖中尋找最小生成樹的基本步驟是： （ 1） 從網(wǎng)絡(luò)圖 N 中任取一回路 C。 圖一： 100 個(gè)可能用戶的坐標(biāo)直觀圖 由上圖 很容易觀察到，有效用戶 96 戶，無效用戶 4 戶， 4 戶無效用戶及所在障礙區(qū)域的分別為： （ 1）障礙區(qū)域 1 覆蓋了一戶用戶，該用戶的序號(hào)為 ，坐標(biāo)為（ ，）； （ 2）障礙區(qū)域 2 覆蓋了兩戶用戶，用戶序號(hào)及坐標(biāo)分別為： （ ，）， （ ， ） 4 （ 3）障礙區(qū)域 3 沒有覆蓋用戶； （ 4）障礙區(qū)域 4 覆蓋了一戶用戶，序號(hào)為 ，坐標(biāo)為（ ， ）。 （ 2）設(shè)計(jì)出一個(gè)算法將有效用戶連接起來，并且連接的距離總和最小。 對(duì)問題二：我們首先得出了任意兩用戶之間的距離，若兩點(diǎn)連線過障礙區(qū)則取無窮大。 三、模型的假設(shè) 1. 每一個(gè)有效用戶都需要鋪設(shè)天然氣管道； 2. 障礙區(qū)都只是由 表 2表 5 給出點(diǎn)，并覆蓋這些要覆蓋的點(diǎn)的最小凸集，不會(huì)出現(xiàn)其他形狀。矩陣中的元素表示對(duì)應(yīng)的兩節(jié)點(diǎn)間的權(quán)數(shù)。 權(quán)值排序法所得的有效用戶的最小距離為： 。 七、參考文獻(xiàn) [1] 楊啟帆 ,方道元 . 數(shù)學(xué)建模 .浙江：浙江大學(xué)出版社， 2020 [2] 徐玖平 ,胡知能 ,王諉 .運(yùn)籌學(xué) .北京：科學(xué)出版社， 2020 [3] 赫孝良 ,戴永紅 ,周義倉 .數(shù)學(xué)建模競(jìng)賽 .西安：西安交通大學(xué)出版社， 2020 [4] 杜端甫 .運(yùn)籌圖論 .北京 :北京航天航空出版社， 1990 八、附件 附件 [一 ]： 100 個(gè)可能用戶的可能橫縱坐標(biāo)（見下表一） 表 1： 100 個(gè)可能的用戶的橫縱坐標(biāo) 可能的用戶的序號(hào) 可能的用戶橫坐標(biāo) 可能的用戶縱坐標(biāo) 9 10 11 附件 [二 ]： 四個(gè)障礙區(qū)域必須要覆蓋的用戶點(diǎn)的坐標(biāo)（如下表二 — 表五） 表 2 障礙區(qū)域 1 必須要覆蓋的坐標(biāo) 頂點(diǎn)序號(hào) 頂點(diǎn)的橫坐標(biāo) 頂點(diǎn)的縱坐標(biāo) 1 2 3 20 表 3