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

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

2、t;　　（系）教研室主任 （簽名） 理學(xué)院院長(zhǎng) （簽名）</p><p>　　1畢業(yè)論文的主要內(nèi)容及基本要求</p><p>　?、挪殚喯嚓P(guān)文獻(xiàn)資料，了解課題研究現(xiàn)狀；</p><p>　?、拼_定并理清課題寫作思路；</p><p>　　⑶尋找圖論算法中的分析方法；</p>

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

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

5、t;<p><b>　　摘 要</b></p><p>　　圖論具有設(shè)計(jì)巧妙，靈活多樣，應(yīng)用廣泛的特點(diǎn)，結(jié)合農(nóng)村自來(lái)水管網(wǎng)優(yōu)化設(shè)計(jì)指標(biāo)，應(yīng)用圖論的最優(yōu)樹生成法等分析自來(lái)水管網(wǎng)優(yōu)化設(shè)計(jì)方案，應(yīng)用圖論的最短路徑等方法分析水源的建設(shè)地理位置，結(jié)果顯示圖論方法在農(nóng)村自來(lái)水管網(wǎng)設(shè)計(jì)中具有很好的應(yīng)用優(yōu)勢(shì)。</p><p>　　關(guān)鍵詞：圖論，水管網(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)村自來(lái)水管網(wǎng)優(yōu)化設(shè)計(jì)指標(biāo)3</p><p><b>　　1.1 可靠性3</b></p><p>　　1.2 水壓水量的保證性3</p><p><b>　

10、　1.3 經(jīng)濟(jì)性3</b></p><p>　　第二章 圖論的應(yīng)用以及算法在MATLAB中的實(shí)現(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 圖論中的最短路問(wèn)題8</p><p>　　2.4 算法在MATLAB中的實(shí)現(xiàn)10</p><p>　　2.4.1 圖論與矩陣的的定義10</p><p>　　2.4.2 最短路Floyd算法在MATLAB中的實(shí)現(xiàn)11</p><p>　　2.4.3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、;p>　　2.2.2 圖論中生成最小樹的Prim算法</p><p>　?。?）作為開(kāi)始 令，并對(duì)每個(gè)令標(biāo)號(hào)</p><p>　?。?）如果停止；否則求一頂點(diǎn)使</p><p>　　并記達(dá)到上述最小值的到的伴隨邊為。</p><p><b>　?。?）令</b></p><p><b

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

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

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

47、　　。</b></p><p>　　是一最短-路 </p><p>　　算法的原理是逐步求出頂點(diǎn)序列</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>　　即，首先對(duì)中每個(gè)，按（*）式求出。使達(dá)到最小的就是，且這時(shí)有。至此，得；，某，就是當(dāng)時(shí)使（*）式右邊達(dá)到最小的。</p><p>　　當(dāng)進(jìn)行下一步時(shí)，易見(jiàn)，對(duì)每一個(gè)，我無(wú)需再直接用（*）式，重復(fù)通過(guò)中的每個(gè)去求，只要通過(guò)更新（updata）即可</p><p&g

50、t;　　下面的算法只求出從到其他各頂點(diǎn)之間的距離。若想求出從到其他各頂點(diǎn)之間的最短路，只需要按上述作一些改動(dòng)即可。</p><p>　　Dijkstra算法[2]：</p><p>　?。?）作為開(kāi)始： ；</p><p>　?。?）（這時(shí)已求出，且對(duì)每個(gè)，有） </p><p><b>　　，</b><

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

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

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

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

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

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

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

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

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

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

61、如下</p><p>　　經(jīng)過(guò)程序在Matlab中運(yùn)行后得到了以下結(jié)果，（詳細(xì)程序見(jiàn)附錄一）</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>　　這就說(shuō)明以4為起點(diǎn)以2為終點(diǎn)的邊保留，以5為起點(diǎn)以1為終點(diǎn)的邊保留，以6為起點(diǎn)以4為終點(diǎn)的邊保留，以8為起點(diǎn)以6為終點(diǎn)的邊保留，以7為起點(diǎn)以3為終點(diǎn)的邊保留，以4為起點(diǎn)以1為終點(diǎn)的邊保留，以4為起點(diǎn)以3為終點(diǎn)

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

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

65、，如下</p><p>　　現(xiàn)在利用求最短路的dijkstra思想編輯Matlab程序可以求解出一點(diǎn)使得其余七點(diǎn)到達(dá)這點(diǎn)的所要經(jīng)過(guò)的邊的賦權(quán)值之和，在Matlab中運(yùn)行程序后得到如下結(jié)果：。（詳細(xì)程序見(jiàn)附錄二）</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)在我們可以利用這個(gè)矩陣在matlab中編輯一個(gè)簡(jiǎn)單的程序求出這八個(gè)點(diǎn)中的一點(diǎn)，使得這點(diǎn)到其余七點(diǎn)的最短路徑最短，而這點(diǎn)就是水源建設(shè)點(diǎn)，因?yàn)樗唇ㄔO(shè)在這里，它提供的水壓是最低的，而且在水壓方面選擇水管材料時(shí)，又可以節(jié)約一筆資金。下面簡(jiǎn)單的介紹下這程序的理論：</p><p>　　我們已經(jīng)知道了點(diǎn)ii到點(diǎn)jj之間的最短距離的矩陣D（D矩陣為對(duì)稱矩陣，詳看上圖），點(diǎn)ii到點(diǎn)jj

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

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

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

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

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

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

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

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

77、作用。在此向他表示我最衷心的感謝！</p><p>　　最后向在百忙之中評(píng)審本文的各位專家、老師表示衷心的感謝！</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>　　運(yùn)行結(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>　　運(yùn)行結(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(shè)地</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>　　運(yùn)行結(jié)果為：</b></p><p><b>　　ans =</b></p><p><b>　　340 4</b></p><p><b>　　文獻(xiàn)綜述</b></p><p>

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

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

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

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

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

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

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

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

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