畢業(yè)論文---圖論在農(nóng)村自來水管網(wǎng)設計中的應用

1、<p>　　圖論在農(nóng)村自來水管網(wǎng)設計中的應用</p><p><b>　　畢業(yè)論文任務書</b></p><p>　　論文題目： 圖論在農(nóng)村自來水管網(wǎng)設計中的應用 </p><p>　　接受任務時間： 2011年3月10日 </p><p&g

2、t;　?。ㄏ担┙萄惺抑魅?（簽名） 理學院院長 （簽名）</p><p>　　1畢業(yè)論文的主要內(nèi)容及基本要求</p><p>　?、挪殚喯嚓P文獻資料，了解課題研究現(xiàn)狀；</p><p>　?、拼_定并理清課題寫作思路；</p><p>　?、菍ふ覉D論算法中的分析方法；</p>

3、<p>　?、冉鉀Q問題，提出用最短路徑解決水管網(wǎng)的安排；</p><p>　?、蓪懗鏊悸非逦壿嫼侠淼恼撐?。</p><p>　　2指定查閱的主要參考文獻及說明</p><p>　　[1]耿素云.離散數(shù)學[M].北京:高等教育出版社,2009:273—291.</p><p>　　[2]孫惠泉.圖論及其應用[M].北京:科學出

4、版社,2004:1—92.</p><p>　　[3]岳延兵.圖論在農(nóng)村自來水管網(wǎng)設計中的應用[J],山西水利技術與應用,2010年,第5期.</p><p>　　[4]管志忠.圖論中最短路問題在MATLAB程序?qū)崿F(xiàn)[J],安慶師范學院學報（自然科學報）第13卷第1期:2007.</p><p><b>　　3.進度安排</b></p&g

5、t;<p><b>　　摘 要</b></p><p>　　圖論具有設計巧妙，靈活多樣，應用廣泛的特點，結(jié)合農(nóng)村自來水管網(wǎng)優(yōu)化設計指標，應用圖論的最優(yōu)樹生成法等分析自來水管網(wǎng)優(yōu)化設計方案，應用圖論的最短路徑等方法分析水源的建設地理位置，結(jié)果顯示圖論方法在農(nóng)村自來水管網(wǎng)設計中具有很好的應用優(yōu)勢。</p><p>　　關鍵詞：圖論，水管網(wǎng)，最短路徑<

6、/p><p><b>　　ABSTRACT</b></p><p>　　Graph theory has many distinguishing features, such as clever design, diversity and widespread application. Combining optimization design indexes of ru

7、ral water pipe network, we analyse optimization design scheme of water pipe network in term of most superior spanning tree on graph. Furthermore, we discuss the construction position of water source by the shortest path

8、method of graph. The results show that graph theory method has very good advantages in rural water pipe design.</p><p>　　Keywords：Graph ，Water pipe network ，Shortest path.</p><p><b>　　目 錄

9、</b></p><p><b>　　前 言1</b></p><p>　　第一章 農(nóng)村自來水管網(wǎng)優(yōu)化設計指標3</p><p><b>　　1.1 可靠性3</b></p><p>　　1.2 水壓水量的保證性3</p><p><b>　

10、　1.3 經(jīng)濟性3</b></p><p>　　第二章 圖論的應用以及算法在MATLAB中的實現(xiàn)4</p><p>　　2.1 圖的一些基本概念4</p><p>　　2.2 圖論中的樹6</p><p>　　2.2.1 圖論中生成最小樹的Kruskal算法7</p><p>　　2.2.2 圖

11、論中生成最小樹的Prim算法8</p><p>　　2.3 圖論中的最短路問題8</p><p>　　2.4 算法在MATLAB中的實現(xiàn)10</p><p>　　2.4.1 圖論與矩陣的的定義10</p><p>　　2.4.2 最短路Floyd算法在MATLAB中的實現(xiàn)11</p><p>　　2.4.3

12、最短路Dijkstra算法在Matlab中的實現(xiàn)12</p><p>　　2.4.4 Kruskal算法在MATLAB中的實現(xiàn)12</p><p>　　第三章 圖論在水管網(wǎng)中的算例13</p><p>　　3.1 把實際問題轉(zhuǎn)化成圖論問題13</p><p>　　3.2 運用Kruskal算法生成最小樹13</p>

13、<p>　　3.3 用最短路徑法找水源建設地15</p><p>　　3.4 問題解決的最后結(jié)果16</p><p><b>　　結(jié)束語17</b></p><p><b>　　參考文獻18</b></p><p><b>　　致 謝19</b></

14、p><p><b>　　附 錄20</b></p><p><b>　　文獻綜述26</b></p><p><b>　　前 言</b></p><p>　　圖論起源于舉世聞名的柯尼斯堡七橋問題。在柯尼斯堡的普萊格爾河上面有七座橋?qū)⒑又械膷u及島與河岸是連接起來的,有一個問題

15、是要從這四塊陸地中任何一塊開始，通過每一座橋而且正好只能一次，再回到起點。然而許多人經(jīng)過無數(shù)次的嘗試都沒有成功。在1736年歐拉神奇般的解決了這個問題，他用抽像分析法將這個問題化為第一個圖論問題：即用點來代替每一塊陸地，將每一座橋用聯(lián)接相應的兩個點的一條線來代替，所以相當于得到一個“圖”（如下圖）。</p><p>　　柯尼斯堡七橋圖 橋轉(zhuǎn)換成圖</p>

16、<p>　　歐拉證明了這個問題是沒有解的，并且推廣了這個問題，給出了對于一個給定的圖可以某種方式走遍的判定法則。這項工作使得歐拉成為圖論〔及拓撲學〕的創(chuàng)始人。</p><p>　　圖論其實也是一門應用數(shù)學，它的概念和結(jié)果來源非常廣泛，既有來自生產(chǎn)實踐的問題，也有來自理論研究的問題。它具有以下特點：蘊含了豐富的思想、漂亮的圖形以及巧妙的證明；涉及的問題很多而且廣泛，問題外表簡單樸素，本質(zhì)上卻十分復雜深

17、刻；解決問題的方法是千變?nèi)f化，非常靈活，常常是一種問題就有一種解法。圖論研究的內(nèi)容非常廣泛，如圖的連通性、遍歷性、圖的計數(shù)、圖的著色、圖的極值問題、圖的可平面性等。歷史上參與研究圖論問題的人既有許多天才的數(shù)學家，也有不少的業(yè)余愛好者。</p><p>　　那么什么是圖論中的圖呢？在日常生活、生產(chǎn)活動以及科學研究中，人們常用點表示事物，用點與點之間是否有連線表示事物之間是否是有某種關系，這樣構(gòu)成的圖形就是圖論中的圖

18、。其實，集合論中的二元關系的關系圖都是圖論中的圖，在這些圖中，人們只關心點與點之間是否有連線，而不關心點的位置，以及連線的曲直。這就是圖論中的圖與幾何中的圖形的本質(zhì)區(qū)別。</p><p>　　因此在現(xiàn)實世界中，事物的許多狀態(tài)可以由圖形來描述，使其簡單直觀，便于理解，幫助思維，易于記憶，同時還可以根據(jù)圖的特點，從不同角度來擴展討論范圍。</p><p>　　構(gòu)成圖論中的圖有三個要素[1]：&

19、lt;/p><p>　　點————抽象表示具體事物，既沒有大小，又沒有位置區(qū)別</p><p>　　邊————反映事物之間有聯(lián)系，不考慮長度和形狀</p><p>　　方向————指明起點及終點，表示事物間的關系特征</p><p><b>　　圖論的定義[1] </b></p><p>　　設是有序

20、二元組，如果滿足以下條件：</p><p>　?。?）是非空有限集；</p><p>　?。?）是中不同元素的非有序?qū)ε冀M成的集合；</p><p>　　則稱G為一個簡單的無向圖。</p><p>　　因此本文打算結(jié)合農(nóng)村自來水管網(wǎng)優(yōu)化設計指標把農(nóng)村供水處看著點，把水管看著線，把所有的點連接成一個n階無向完全圖，再根據(jù)實際情況給每條無向邊附以

21、權(quán)重，再根據(jù)圖論的性質(zhì)和MATLAB軟件找到水塔在農(nóng)村何處建立，從而達到農(nóng)村自來水管網(wǎng)最優(yōu)化達到可靠性，水壓水量保證性以及經(jīng)濟性的效果，為新農(nóng)村的建設節(jié)約資金和環(huán)境的美化。</p><p>　　第一章 農(nóng)村自來水管網(wǎng)優(yōu)化設計指標</p><p>　　農(nóng)村自來水管網(wǎng)優(yōu)化設計的指標主要有可靠性、水壓水量的保證性和經(jīng)濟性。</p><p><b>　　1.1

22、可靠性</b></p><p>　　計流量和布置在給水系統(tǒng)工程中，輸水管分原水輸水管和凈水輸水管，前者是指從水源地到水廠的輸水管線。后者是指當水廠距供水區(qū)域較遠時，從水廠到區(qū)域配水管網(wǎng)的輸水管線。當無有利地形可供利用，無條件采用重力輸水時，一般均采用密閉管道進行壓力輸水。輸水管通常沿線無流量變化，其獨立管段內(nèi)的流量是沿程不變的。原水輸水管的設計流量，應按照對水廠最高日平可靠性是指在規(guī)定的使用狀態(tài)下、規(guī)

23、定的時間內(nèi)完成預定功能的性能。輸水管的設均需水量計算確定，一般包括綜合生活用水量(包括居民生活用水和公共建筑用水)，對農(nóng)村飲水工程供水管網(wǎng)而言，預定功能是指在正常工作條件下，保證給水栓所需要的水量以及水壓。在工程設計中我們必須考慮到可靠性，有可能減少因為故障引起的損失和維修資金。管網(wǎng)優(yōu)化設計時候，其可靠性就應該達到在發(fā)生事故的可能下，水量和水壓不能低于規(guī)定的限度，在時間上也不超過允許減少水量和降低水壓的時間。</p>&l

24、t;p>　　1.2 水壓水量的保證性</p><p>　　在輸水正常工作時，根據(jù)人們平時生活用水量，即生產(chǎn)用水量和消防用水量，各個給水栓的水壓、水量必須要達到設計要求，以免水壓過的高引起水量以及能量的浪費，防止下游因水壓降低導致水壓和水量的不足。</p><p><b>　　1.3 經(jīng)濟性</b></p><p>　　在農(nóng)村飲水供水工程中

25、，經(jīng)濟性是在進行管網(wǎng)優(yōu)化設計時所要考慮的一個重要指標。管線的費用主要是與水管的材料和長度及其直徑等有關，在管網(wǎng)設計時應由給水栓的布置確定最優(yōu)化的管網(wǎng)布置方案，減小管網(wǎng)的長度；從而減少資金的浪費，因此，確定管網(wǎng)的最優(yōu)管徑組合是以期達到整個管網(wǎng)的經(jīng)濟性。</p><p>　　另外除了經(jīng)濟性外，其他方面都有有一定難度進行定量評價。如用水量變化以及管道的損壞原因使計算流量很難等同于實際流量，泵站的運行方式和管理水平也會影

26、響到管網(wǎng)設計目標的實現(xiàn)。因此在管網(wǎng)設計中，主要是對管網(wǎng)的布置和管徑的選擇進行優(yōu)化（本文注重的是布置方面），選出最佳方案，盡量達到設計目標。</p><p>　　第二章 圖論的應用以及算法在MATLAB中的實現(xiàn)</p><p>　　本章首先介紹了圖論中圖的一些基本概念，然后在此基礎上給出了圖論中的樹的定義與最短路徑的算法以及算法在MATLAB中的實現(xiàn)。</p><p&g

27、t;　　2.1 圖的一些基本概念</p><p>　　我們從這些形形色色的具體的圖中, 取出它們共同性的東西, 抽象出一般的圖的概念。圖的最基本要素是點, 以及點與點之間的連線! 通常用點表示我們所要研究的對象(如城市、運動隊、狀態(tài)等)用連線表示對象之間的某種特定的關系(如兩城市之間有鐵路線、兩個運動隊之間比賽過等)。因此, 可以說圖是反映對象之間關系的一種工具! 如果兩個對象之間有這種關系, 那么就用一條線連接

28、這兩個點, 由此可見, 對我們來說, 重要的是哪些點之間有線相連, 而點的相對位置、線的長短曲直, 則往往不是重要的。</p><p>　　如果給了一些點, 并己知點與點之間的連接情況, 也就給出了一個圖。我們把給定的點的全體稱為點集合, 用表示, 把給定的連線的全體稱為線集合, 用E表示! 如果圖用G表示, 我們可以把圖記成，我們記，總用,分別表示圖的點數(shù)和線數(shù)! 如果線是連接點和的, 可以把記為（也可以記為）

29、。</p><p>　　給出圖形（如下圖2-1-1）</p><p>　　圖 2-1-1 圖論中的圖</p><p><b>　　這個圖中，</b></p><p><b>　??；</b></p><p><b>　　；</b></p>&

30、lt;p><b>　??；</b></p><p><b>　　;</b></p><p>　　按照以上所說的線的記法，也可以記為：</p><p>　　根據(jù)對圖論中的圖的定義,除了給出上面一個具體的例子外，與它有關的還有下面的一些概念和規(guī)定[1]。</p><p>　　設為無向圖，，稱為的端點

31、，與關聯(lián)，若，則稱與的關聯(lián)次數(shù)為1；若，則稱與的關聯(lián)次數(shù)為2，并稱為環(huán)。</p><p>　　在無向圖中，如果關聯(lián)一對頂點的無向邊多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)。如果關聯(lián)一對頂點的有向邊多于1條，并且這些邊的始點和終點相同（也就是它們的方向相同），則稱這些邊為平行邊。含平行邊的圖形為多重圖，既不含平行邊也不含環(huán)的圖稱為簡單圖。</p><p>　　設為無向圖，,稱作為邊

32、的端點的次數(shù)為的度數(shù)，簡稱度。</p><p>　　在任何無向圖中，所有的頂點的度數(shù)之和等于邊數(shù)的2倍。</p><p>　　在任何有向圖中，所有的頂點的度數(shù)之和等于邊數(shù)的2倍；所有的頂點的入度之和等于所有頂點的出度之和等于邊數(shù)。</p><p>　　任何圖無論是有向圖還是無向圖中，奇度頂點的個數(shù)是偶數(shù)。</p><p>　　非負整數(shù)列是可圖

33、化的當且僅當為偶數(shù)。</p><p>　　設為兩個無向圖（兩個有向圖），若存在雙射函數(shù)使得，當且僅當 (當且僅當），并且與 （與）的重數(shù)相同，則稱與同構(gòu)。</p><p>　　圖論的定理證明難度高低不等，有的簡單易懂，有的難于理解，但其每一步證明都需要技巧，每一個定理都像藝術平一樣值得品味與推敲。因此，盡管本文介紹的是較為基礎的圖論內(nèi)容，但閱讀理解與完成習題是學習圖論必不可少的步驟。<

34、;/p><p><b>　　2.2 圖論中的樹</b></p><p>　　在各種各樣的圖中, 有一類簡單而重要的圖, 即所謂“ 樹” 。樹之所以重要, 不僅在于它在許多不同領域中應用, 而且也在于圖論本身。在圖論中, 解決許多懸而未決的問題往往是從樹這一類圖著手。很多問題對一般圖未能解決或者沒有簡便的方法, 而對樹則完滿解決, 方法極其簡單。</p>&l

35、t;p>　　樹的定義[2] 給定無向圖,如果圖是連通，并且不含圈，則稱為樹。通常用來表示。</p><p>　　本文要用到生成最小樹的知識，所以提起樹，還得著重介紹下圖的樹：</p><p>　　設給定圖,圖，是它的一個部分圖，如果是樹，則稱是的一個部分樹。</p><p>　　如下圖2-2-1，圖中由粗線所示的圖是它的一個部分樹。</p>&l

36、t;p>　　圖2-2-1 圖論中的樹</p><p>　　值得說的是，每一個完全無向圖圖中都有一部分樹。下面再給出一些關于圖論中的樹的推論[2]：</p><p>　　設是一棵樹，則樹中的線條總數(shù)=樹中的點的總數(shù)-1，即有</p><p><b>　　下述論斷是等價的</b></p><p>　　<a>

37、;圖是連通的無圈圖；</p><p>　　<b>圖中無圈，并且；</p><p>　　<c>圖是連通的，并且。</p><p><b>　　若是樹，則</b></p><p>　　<a>連通，但丟去任何一條線, 圖便斷成兩個且僅僅兩個連通片；</p><p>　

38、　<b>無圈, 但添加任何一條線, 圖便含有一個且僅僅一個圈。</p><p>　　每棵非平凡樹至少有兩個度為為1的頂點</p><p>　　了解這些定理對于下第三章提到到生成最小樹的Kruskal算法和Prim算法有著很大的幫助。</p><p>　　2.2.1 圖論中生成最小樹的Kruskal算法</p><p>　　如果在圖

39、的每條邊上，都賦予一個非實數(shù)，則稱為一賦權(quán)圖（weitghed graph);稱為邊的權(quán)（weighted）。因此，是定義在上的一個非負實數(shù)。</p><p>　　對于一個賦權(quán)圖中必然包含了一個賦權(quán)的樹，稱中所有邊的權(quán)的和</p><p><b>　　,</b></p><p>　　而利用Kruskal算法可以找到圖中包含的樹中最小值，即使最小

40、樹即，Kruskal算法[2]如下；</p><p>　?。?）選棱（link），使最小。</p><p>　　（2）若已選定，則從中選取棱使</p><p><b>　　（a）無圈</b></p><p>　?。╞）是滿足（a）之最小者</p><p>　?。?）若（2）不能再進行下去時，停止。

41、否則回到（2）。</p><p>　　下面簡單證明下用此算法求出來的的生成樹是最優(yōu)樹。</p><p>　　反正法，假設不是的最優(yōu)樹。取的一最優(yōu)樹。令為中（按其順序）第一個不屬于的邊，且令為最優(yōu)樹中使為最大者。</p><p>　　由于無圈，中唯一的圈中一定包含。又由于樹不包含圈，中必含一條邊不屬于，所以可知的圈中的邊不是的割邊，因此</p><

42、p>　　乃連通，且邊數(shù)等于，從而也是的生成樹。</p><p><b>　　又由算法知，是使</b></p><p>　　為無圈的邊中權(quán)最小的，而的子圖</p><p>　　也不含圈，因此，從而</p><p>　　即也是的最優(yōu)樹，且中第一個不屬于的邊的下標大于k，這就與的取法相矛盾。</p><

43、;p>　　2.2.2 圖論中生成最小樹的Prim算法</p><p>　?。?）作為開始 令，并對每個令標號</p><p>　?。?）如果停止；否則求一頂點使</p><p>　　并記達到上述最小值的到的伴隨邊為。</p><p><b>　?。?）令</b></p><p><b

44、>　　通過新頂點更新。</b></p><p><b>　?。?）轉(zhuǎn)到（2）。</b></p><p>　　2.3 圖論中的最短路問題</p><p>　　路的定義[2] 設為無向標定圖，中頂點與邊的交替序列</p><p>　　稱為到的通路，其中，為的端點，分別稱為始點與終點，中的邊的條數(shù)稱為它的長度

45、，若又有，則稱為回路。若的所有邊各異，則稱為簡單通路。若又有，則稱為簡單回路，若所有的頂點（除與可能相同外）各異，所有的邊也各異，則稱為初級通路或路徑，若又有，則為初級回路或圈，將長度為奇數(shù)的圈成為奇圈，長度為偶數(shù)的圈為偶圈。</p><p>　　本文要考慮的問題是對任意給定的一個賦權(quán)圖,及中兩個指點的頂點與，求出其最短（-路。易見。只要考慮簡單連通圖的情形就夠了。這里我們假設每邊的權(quán)都是大于0的實數(shù)。因為當一條

46、邊的權(quán)為0時。我們可以把和合并成一個頂點。又，我們約定邊當且僅當。</p><p>　　下面將要提到的Dijkstra（1959）算法，將求出從一指定頂點到的其余所有頂點的最短路。而不是最短-路。</p><p>　　對的頂點真子集,及,將到的距離定義為</p><p>　　設頂點使，而為最短-路，則易見：</p><p><b>

47、　　。</b></p><p>　　是一最短-路 </p><p>　　算法的原理是逐步求出頂點序列</p><p><b>　　使</b></p><p><b>　　記</b></p><p><b>　　為最短-路，</b&

48、gt;</p><p><b>　?。?）求;使得</b></p><p><b>　　。</b></p><p>　?。?）若已求得；；及最短-路如圖2-3-1</p><p>　　圖2-3-1 最短路示意圖</p><p><b>　　求使</b>

49、</p><p><b>　　其中</b></p><p>　　即，首先對中每個，按（*）式求出。使達到最小的就是，且這時有。至此，得；，某，就是當時使（*）式右邊達到最小的。</p><p>　　當進行下一步時，易見，對每一個，我無需再直接用（*）式，重復通過中的每個去求，只要通過更新（updata）即可</p><p&g

50、t;　　下面的算法只求出從到其他各頂點之間的距離。若想求出從到其他各頂點之間的最短路，只需要按上述作一些改動即可。</p><p>　　Dijkstra算法[2]：</p><p>　?。?）作為開始： ；</p><p>　?。?）（這時已求出，且對每個，有） </p><p><b>　　，</b><

51、/p><p>　　再計算，設其最小值點為，令</p><p>　?。?)若，停止；不然，令，并回到（2）。</p><p>　　2.4 算法在MATLAB中的實現(xiàn)</p><p>　　2.4.1 圖論與矩陣的的定義</p><p>　　關聯(lián)矩陣[7] 設有向圖G=(V,E), V={v1,v2,…, vn},E = {e1

52、,e2,…,em}。 構(gòu)造矩陣B =(bij)n?m，稱之為G的關聯(lián)矩陣，其中</p><p><b>　　關聯(lián)矩陣的列舉</b></p><p>　　權(quán)矩陣[7] 對帶權(quán)圖 G=(V, R)， n=|V|，構(gòu)造矩陣，其中</p><p>　　稱為圖G的權(quán)矩陣。</p><p>　　2.4.2 最短路Floyd算法在M

53、ATLAB中的實現(xiàn)</p><p>　　求n個頂點的連通圖G上任意兩點間的最短路長的算法(它是下面要講的Floyd(1962)算法的改進，但它只適用于非負權(quán)的最短路問題）。設為頂點到的距離，令圖的權(quán)矩陣為</p><p>　　算法的基本步驟[7]</p><p><b>　　（1）輸入權(quán)矩陣。</b></p><p>　

54、?。?）計算，其中表示從點到的距離，或者經(jīng)過某一個中間點到達點的最短路。</p><p>　　（3）若，則就是到的最短路長，不然，取，轉(zhuǎn)（2）。</p><p>　　2.4.3 最短路Dijkstra算法在Matlab中的實現(xiàn)</p><p>　　Dijkstra算法的基本思想是：按距離由近及遠的順序，依次求得到的各頂點的最短路和距離，直至（或直至的所有頂點），算法

55、結(jié)束。為避免重復并保留每一步的計算信息，采用了標號算法。</p><p>　　Dijkstra算法步驟[7]如下</p><p>　?。?）令，對于，令，</p><p>　?。?）對每個，用代替，當不相鄰時，。計算，把達到這個最小值的一個頂點記為，令。</p><p>　?。?）若，則停止，若，則用代替，轉(zhuǎn)至（2）。</p>

56、<p>　　2.4.4 Kruskal算法在MATLAB中的實現(xiàn)</p><p>　　Kruskal算法的基本思想是：設無向連通網(wǎng)為G=（V，E），令G的最小生成樹為T=（U，TE），其初始狀態(tài)為U=V，TE={},這樣T中各頂點各自構(gòu)成一個連通分量。然后按照邊的權(quán)值由小到大的順序，依次考察邊集E中的各條邊。若被考察的邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊加入到TE中去，同時把兩個連通分量連接

57、成一個連通分量；若被考察邊的兩個結(jié)點屬于同一個連通分量，則舍去此邊，以免造成回路，如此下去，當T中的連通分量個數(shù)為1時，此連通分量便為G的一棵最小生成樹。</p><p>　　Kruskal程序流程圖為[11]：</p><p>　　相關變量初始化工作，將原圖的鄰接矩陣拷貝到temp矩陣中，避免程序?qū)υ仃囍苯舆M行修改；</p><p>　　找最小生成樹（采用whi

58、le循環(huán)，因為循環(huán)次數(shù)事先并不確定）循環(huán)結(jié)束條件為找到了頂點數(shù)-1條最優(yōu)邊；</p><p>　　求最小生成樹的總代價并顯示，并顯示最小生成樹的邊，及其權(quán)值。</p><p>　　第三章 圖論在水管網(wǎng)中的算例</p><p>　　3.1 把實際問題轉(zhuǎn)化成圖論問題</p><p>　　我們把一個縣的八個村看成是八個點，用線段把每一個點與其相鄰

59、的點連接起來，從而形成一個無向圖。再根據(jù)實際情況：村與村的水管長短問題；防腐程度深淺問題；水管安置工程的難易問題；水管的維修以及管線的費用問題等給相應的邊賦上權(quán)值，最后得出一個賦權(quán)圖，如圖3-1-1：</p><p>　　圖3-1-1農(nóng)村地圖轉(zhuǎn)換成圖論中的圖</p><p>　　圖中：1代表新萬發(fā)鎮(zhèn)新農(nóng)村村：2代表林海鎮(zhèn)交通村，3代表官屯村，4代表鳳凰鄉(xiāng)濟公村，5代表花石溝村，6代表銅礦村

60、，7代表牡丹閣村，8代表石田村。由此一來，我們就可以運用圖論的知識進行科學的解決實際問題從而帶來經(jīng)濟效益，減少不必要的支出。</p><p>　　3.2 運用Kruskal算法生成最小樹</p><p>　　值得一提的是，在Kruskal算法中要運用到權(quán)矩陣，為了簡化在Matlab中簡化程序，但此矩陣與上面的權(quán)矩陣有所不同，此矩陣一共只有三行，第三行的數(shù)是對應的第一與第二行數(shù)之間的賦權(quán)值，

61、如下</p><p>　　經(jīng)過程序在Matlab中運行后得到了以下結(jié)果，（詳細程序見附錄一）</p><p><b>　　T =</b></p><p>　　4 5 6 8 7 4 4</p><p>　　2 1 4 6 3 1

62、 3</p><p><b>　　c =</b></p><p><b>　　240</b></p><p>　　這就說明以4為起點以2為終點的邊保留，以5為起點以1為終點的邊保留，以6為起點以4為終點的邊保留，以8為起點以6為終點的邊保留，以7為起點以3為終點的邊保留，以4為起點以1為終點的邊保留，以4為起點以3為終點

63、的邊保留，其這些邊的權(quán)值和為240（應為最小值）。詳看下圖3-2-1</p><p>　　圖3-2-1 生成最小樹后的圖</p><p>　　3.3 用最短路徑法找水源建設地</p><p>　　相對于圖論，運用前面所介紹的生成最小樹的Kruskal法可以找到每個問題的最小解，但對于管網(wǎng)的優(yōu)化布置，僅僅尋求最小生成樹并不能實現(xiàn)投資最少的目標。最小生成樹僅是管網(wǎng)投資減

64、少的一個因素，它所尋求的是整個管網(wǎng)的總長度最短，即所有頂點之間的最短連接，而不是一點到其余各點之間的最短連接。在管網(wǎng)布置時，假定各個管段的直徑是均一的，但當水源位置不同時，各段管徑的大小有較大差異，因而對造價的影響較大。通過縮短流量和直徑較大的管段長度，同時增加流量較小的直徑較小的管道長度，使管網(wǎng)的總投資進一步降低。這一問題可采用最短路徑法得以解決。</p><p>　　首先把那生成的最小樹飛賦權(quán)圖的權(quán)矩陣寫出來

65、，如下</p><p>　　現(xiàn)在利用求最短路的dijkstra思想編輯Matlab程序可以求解出一點使得其余七點到達這點的所要經(jīng)過的邊的賦權(quán)值之和，在Matlab中運行程序后得到如下結(jié)果：。（詳細程序見附錄二）</p><p>　　0 130 190 90 60 150 260 210</p><p>　　130 0 14

66、0 40 190 100 210 160</p><p>　　190 140 0 100 250 160 70 220</p><p>　　90 40 100 0 150 60 170 120</p><p>　　60 190 250 150 0 21

67、0 320 270</p><p>　　150 100 160 60 210 0 230 60</p><p>　　260 210 70 170 320 230 0 290</p><p>　　210 160 220 120 270 60 290 0<

68、;/p><p>　　現(xiàn)在我們可以利用這個矩陣在matlab中編輯一個簡單的程序求出這八個點中的一點，使得這點到其余七點的最短路徑最短，而這點就是水源建設點，因為水源建設在這里，它提供的水壓是最低的，而且在水壓方面選擇水管材料時，又可以節(jié)約一筆資金。下面簡單的介紹下這程序的理論：</p><p>　　我們已經(jīng)知道了點ii到點jj之間的最短距離的矩陣D（D矩陣為對稱矩陣，詳看上圖），點ii到點jj

69、之間來回最短距離為D2=D+D'=2*D，其中D'為D的轉(zhuǎn)置，行向量far=max（D)的第jj個元素表示若水源建設在jj點，最遠的點到水源的來回距離，[m,ii]=min(far)就獲得水源應建設在ii點，最遠的點到水源的來回距離為m。在Matlab中運行后的結(jié)果為（詳細程序見附錄三）</p><p>　　340 4</p><p>　　這一結(jié)果表明水源應該建設

70、在點4即代表鳳凰鄉(xiāng)濟公村，是最合理的，最優(yōu)化的最具有經(jīng)濟效益的結(jié)果。</p><p>　　3.4 問題解決的最后結(jié)果</p><p>　　本文的最終目的就是利用圖論的知識把農(nóng)村自來水管網(wǎng)設計達到最有經(jīng)濟效益的結(jié)果，經(jīng)過把實際事物轉(zhuǎn)化為點與線的關系即圖論中的圖，利用圖的一些性質(zhì)以及Matlab軟件的優(yōu)越性，經(jīng)過編輯程序求得了最終結(jié)果，如圖3-4-1</p><p>　

71、　圖3-4-1最終結(jié)果示意圖</p><p>　　圖中粗線表示應該鋪設水管，細線表示不需要鋪設水管，水源建設地在鳳凰鄉(xiāng)濟公村</p><p><b>　　結(jié)束語</b></p><p>　　圖論是一種對農(nóng)村自來水管網(wǎng)設計進行有效優(yōu)化的數(shù)學方法，是將復雜的農(nóng)村自來水管網(wǎng)處理為相應的網(wǎng)絡圖，并建立相應的數(shù)學模型，用原始數(shù)據(jù)來描述管網(wǎng)結(jié)構(gòu)，輸入的數(shù)據(jù)

72、量少，不易出錯，易于計算大型的復雜管網(wǎng)，其計算過程可同時考慮管網(wǎng)附件，如控制閥、加壓泵、逆止閥、減壓閥等，使計算結(jié)果更加符合實際，在農(nóng)村自來水管網(wǎng)設計中具有很好的應用前景。</p><p>　　由于自己的水平有限，在寫論文的過程中遇到了很多困難，所以寫的論文難免有不足之處。</p><p><b>　　參考文獻</b></p><p>　　[1

73、]耿素云.離散數(shù)學[M].北京:高等教育出版社,2009:273—291.</p><p>　　[2]孫惠泉.圖論及其應用[M].北京:科學出版社,2004:1—92.</p><p>　　[3]黃兆東.MATLAB2007科學計算與工程分析[M],北京:科學出版社,2008:231—299.</p><p>　　[4]朱天開.圖論在排水管網(wǎng)優(yōu)化方面的應用[J],中

74、國測試技術,第1期:2004.</p><p>　　[5]毛玲玲.皖江城市帶交通干線布局研究[J],樂山師范學院學報,第25卷,第12期:2010.</p><p>　　[6]艾素梅.數(shù)學建模中的圖論方法[J],滄州師范專科學校學報,第26卷,第4期:2010.</p><p>　　[7]燕子宗.圖論及其應用[J],重慶科技學院學報（自然科學版）,第9卷,第2期:2

75、007.</p><p>　　[8]岳延兵.圖論在農(nóng)村自來水管網(wǎng)設計中的應用[J],山西水利技術與應用,2010年,第5期.</p><p>　　[9]管志忠,圖論中最短路問題在MATLAB程序?qū)崿F(xiàn)[J],安慶師范學院學報（自然科學報）第13卷第1期:2007.</p><p>　　[10]姚朝灼.圖論算法的可視化操作平臺設計[J],福州大學學報（自然科學報）,第3

76、4卷第1期:2006.</p><p>　　[11]王海英,黃強,李傳濤,褚寶增.圖論算法及其MATLAB實現(xiàn)[M].北京:北京航天大學出版社,2010:12—34.</p><p><b>　　致 謝</b></p><p>　　本文是在XX老師的熱情關心和指導下完成的，他淵博的知識和嚴謹?shù)闹螌W作風使我受益匪淺，對順利完成本課題起到了極大的

77、作用。在此向他表示我最衷心的感謝！</p><p>　　最后向在百忙之中評審本文的各位專家、老師表示衷心的感謝！</p><p><b>　　附 錄</b></p><p>　　Kruskal算法生成最小樹</p><p><b>　　主要程序代碼：</b></p><p>

78、;　　function [T c]=Krusf(d,flag)</p><p>　　if nargin==1</p><p>　　n=size(d,2);</p><p>　　m=sum(sum(d~=0))/2;</p><p>　　b=zeros(3,m);</p><p><b>　　k=1;</

79、b></p><p><b>　　for i=1:n</b></p><p>　　for j=(i+1):n</p><p>　　if d(i,j)~=0</p><p>　　b(1,k)=i; b(2,k)=j;</p><p>　　b(3,k)=d(i,j);k=k+1;</p&g

80、t;<p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　else</b></p><p><b>　　b=d;</b>&

81、lt;/p><p><b>　　end</b></p><p>　　n=max(max(b(1:2, : )));</p><p>　　m=size(b,2);</p><p>　　[B,i]=sortrows(b',3);</p><p><b>　　B=B';</b

82、></p><p><b>　　c=0;T=[];</b></p><p>　　k=1; t=1:m</p><p><b>　　for i=1:m</b></p><p>　　if t(B(1,i))~=t(B(2,i))</p><p>　　T(1:2,k)=B(1

83、:2,i);</p><p>　　c=c+B(3,i);</p><p><b>　　k=k+1;</b></p><p>　　tmin=min(t(B(1,i)),t(B(2,i)));</p><p>　　tmax=max(t(B(1,i)),t(B(2,i)));</p><p><b

84、>　　for j=1:n</b></p><p>　　if t(j)==tmax</p><p>　　t(j)=tmin;</p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　end&

85、lt;/b></p><p><b>　　if k==n</b></p><p><b>　　break;</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p><

86、;b>　　T;</b></p><p><b>　　c;</b></p><p>　　>> b=[2 3 4 4 4 5 5 6 6 6 7 7 8 8 8;1 2 1 2 3 1 4 3 4 5 3 6 5 6 7;65 75 45 20 50 30 45 50 30 45 35 70 70 30 80];</p>&l

87、t;p>　　>> [T c]=Krusf(b,1)</p><p><b>　　運行結(jié)果為：</b></p><p><b>　　T =</b></p><p>　　4 5 6 8 7 4 4</p><p>　　2 1

88、 4 6 3 1 3</p><p><b>　　c =</b></p><p><b>　　240</b></p><p>　　（二）dijkstra思想求最短路</p><p><b>　　主要程序代碼：</b></p>&l

89、t;p>　　function a=dijkstra(a)</p><p>　　n=length(a);</p><p><b>　　for i=2:n</b></p><p>　　for j=1:(i-1)</p><p>　　a(i,j)=a(j,i);</p><p><b>

90、　　end</b></p><p><b>　　end</b></p><p>　　for k=1:(n-1)</p><p>　　b=[1:(k-1),(k+1):n];</p><p>　　kk=length(b);</p><p><b>　　a_id=k;</b

91、></p><p>　　b1=[(k+1):n];</p><p>　　kk1=length(b1);</p><p>　　while kk>0</p><p>　　for j=1:kk1</p><p>　　te=a(k,a_id)+a(a_id,b1(j));</p><p>　

92、　if te<a(k,b1(j))</p><p>　　a(k,b1(j))=te;</p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　miid=1;</b></p><p>　　f

93、or j=2:kk</p><p>　　if a(k,b(j))<a(k,b(miid))</p><p><b>　　miid=j;</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p>

94、　　a_id=b(miid);</p><p>　　b=[b(1:(miid-1)),b((miid+1):kk)];</p><p>　　kk=length(b);</p><p><b>　　if a_id>k</b></p><p>　　miid1=find(b1==a_id);</p><

95、;p>　　b1=[b1(1:(miid1-1)),b1((miid1+1):kk1)];</p><p>　　kk1=length(b1);</p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　for j=(k+1):n</p>

96、;<p>　　a(j,k)=a(k,j);</p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　a;</b></p><p><b>　　>> n=8;</b><

97、;/p><p>　　>> a=ones(n)+inf;</p><p>　　>> for i=1:n</p><p><b>　　a(i,i)=0;</b></p><p><b>　　end</b></p><p>　　>> a(1,4)=4

98、5;</p><p>　　>> a(1,5)=30;</p><p>　　>> a(2,4)=20;</p><p>　　>> a(3,4)=50;</p><p>　　>> a(3,7)=35;</p><p>　　>> a(4,6)=30;</p&g

99、t;<p>　　>> a(6,8)=30;</p><p>　　>> dijkstra(a)；</p><p><b>　　運行結(jié)果為：</b></p><p><b>　　ans =</b></p><p>　　0 130 190 90 6

100、0 150 260 210</p><p>　　130 0 140 40 190 100 210 160</p><p>　　190 140 0 100 250 160 70 220</p><p>　　90 40 100 0 150 60 170 1

101、20</p><p>　　60 190 250 150 0 210 320 270</p><p>　　150 100 160 60 210 0 230 60</p><p>　　260 210 70 170 320 230 0 290</p><

102、;p>　　210 160 220 120 270 60 290 0</p><p>　?。ㄈふ宜唇ㄔO地</p><p><b>　　主要程序代碼；</b></p><p>　　>> a=[0 130 190 90 60 150 260 210;</p

103、><p>　　130 0 140 40 190 100 210 160;</p><p>　　190 140 0 100 250 160 70 220;</p><p>　　90 40 100 0 150 60 170 120;</p><p>

104、;　　60 190 250 150 0 210 320 270;</p><p>　　150 100 160 60 210 0 230 60;</p><p>　　260 210 70 170 320 230 0 290;</p><p>　　210 160

105、 220 120 270 60 290 0];</p><p>　　>> a=a+a';</p><p>　　>> far=max(a);</p><p>　　>> [m,ii]=min(far);</p><p><b>　　>> [m,ii]<

106、;/b></p><p><b>　　運行結(jié)果為：</b></p><p><b>　　ans =</b></p><p><b>　　340 4</b></p><p><b>　　文獻綜述</b></p><p>

107、　　圖論在農(nóng)村自來水管網(wǎng)設計中的應用</p><p>　　學生姓名 曾緒波 專業(yè) 數(shù)學與應用數(shù)學 班級 2007級1班 學號 07121020130</p><p>　　圖論其實是一門應用數(shù)學，它的概念和結(jié)果來源非常廣泛，既有來自生產(chǎn)實踐的問題，也有來自理論研究的問題。它具有以下特點：蘊含了豐富的思想、漂亮的圖形和巧妙的證明；涉及的問題多且廣泛，問題外表簡單樸素，本質(zhì)上卻十分復雜深刻；解

108、決問題的方法千變?nèi)f化。非常靈活，常常是一種問題一種解法。圖論研究的內(nèi)容非常廣泛，如圖的連通性、遍歷性、圖的計數(shù)、圖的著色、圖的極值問題、圖的可平面性等。</p><p>　　在許多文章里在談到圖論的時候，首先都會給出圖論中圖的定義，如在《離散數(shù)學》中講述了什么是圖論中的圖：它用集合的敘述方法巧妙的定義出圖論中圖的定義，從而講述了在日常生活、生產(chǎn)活動以及科學研究中，人們常用點表示事物，用點與點之間是否有連線表示事物

109、之間是否是有某種關系，這樣構(gòu)成的圖形就是圖論中的圖。其實，集合論中的二元關系的關系圖都是圖論中的圖，在這些圖中，人們只關心點與點之間是否有連線，而不關心點的位置，以及連線的曲直。這就是圖論中的圖與幾何中的圖形的本質(zhì)區(qū)別。</p><p>　　在實際生活中，圖論是有很大的利用價值的，應用的范圍也很廣泛。在《圖論及其應用》中就介紹了圖論在實際生活中各方面的應用，例如圖論解決中國郵遞員問題，圖論介紹旅行售貨員問題，圖論

110、解決婚配問題，圖論解決人員分配問題，圖論解決教師課程分配問題，圖論解決網(wǎng)絡最大流問題以及最大流的最小割問題，還有世界上具有挑戰(zhàn)性的著色問題也可以用圖論的知識進行解答。</p><p>　　只是知道圖論知識的應用還是不夠的，在圖論中很多問題都是要把圖的問題轉(zhuǎn)化成為矩陣與矩陣之間的問題。在書《圖論及其應用》以及學術報《圖論在排水管網(wǎng)優(yōu)化方面的應用》和《數(shù)學建模中的圖論方法》中都很全面的介紹了圖論中的圖與矩陣與矩陣之間

111、關系的轉(zhuǎn)化方法，圖論中的圖用矩陣來表示有多種方法，有權(quán)矩陣表示方法，有關聯(lián)矩陣表示方法也有不常用的對稱矩陣表示方法。</p><p>　　大家都知道矩陣對于人腦來說，要處理起來是很費時費力的，因此我們還的借用前輩們發(fā)明的MATLAB軟件來處理矩陣與矩陣之間的問題，從而處理實際問題，在書《圖論的算法及其MATLAB實現(xiàn)》和自然科學報中的文章《圖論中最短問題在MATLAB程序?qū)崿F(xiàn)》中很全面的介紹了一些關于圖論中常用的

112、MATLAB語言的應用程序，例如有最短路中的Dijkstra算法的MATLAB語言程序，F(xiàn)loyd矩陣算法的MATLAB語言程序，相應的還有Kruskal算法的程序和Prim算法的程序等等。這些有用的程序給后人帶來巨大的使用價值。</p><p>　　本人的畢業(yè)論文打算通過總結(jié)前人的偉大的學術報告，通過自己的一些獨特的實際應用想法來解決農(nóng)村自來水管網(wǎng)設計問題，打算結(jié)合實際的農(nóng)村自來水管網(wǎng)優(yōu)化設計的指標運用圖論方面

113、的知識把實際問題簡化成圖論問題，再經(jīng)過圖論問題轉(zhuǎn)換成矩陣與矩陣之間的問題后借助MATLAB軟件運行出農(nóng)村自來水管網(wǎng)的最佳設計方案來，這樣能更好的解決農(nóng)村水管網(wǎng)建設中資金浪費問題。從而證實數(shù)學是學科的靈魂，任何復雜的問題我們都可以通過簡單的知識無限的細分后來給出答案。</p><p>　　本文簡要總結(jié)了前人的發(fā)現(xiàn)，其他相關的知識將在畢業(yè)論文寫作過程中，一一補充列舉。</p><p><

114、b>　　參考文獻：</b></p><p>　　[1]耿素云.離散數(shù)學[M].北京:高等教育出版社,2009:273—291.</p><p>　　[2]孫惠泉.圖論及其應用[M].北京:科學出版社,2004:1—92.</p><p>　　[3]朱天開.圖論在排水管網(wǎng)優(yōu)化方面的應用[J],中國測試技術,第1期:2004.</p>&

115、lt;p>　　[4]艾素梅.數(shù)學建模中的圖論方法[J],滄州師范?？茖W校學報,第26卷,第4期:2010.</p><p>　　[5]燕子宗.圖論及其應用[J],重慶科技學院學報（自然科學版）,第9卷,第2期:2007.</p><p>　　[6]管志忠,圖論中最短路問題在MATLAB程序?qū)崿F(xiàn)[J],安慶師范學院學報（自然科學報）第13卷第1期:2007.</p>&l