岳延兵，范 敏

（山西水利職業(yè)技術(shù)學(xué)院，山西 運(yùn)城 044004）

圖論是組合數(shù)學(xué)的一個(gè)分支，也是近幾十年來最活躍的數(shù)學(xué)分支之一，具有以下特點(diǎn)：蘊(yùn)含了豐富的思想、漂亮的圖形和巧妙的證明；涉及的問題多且廣泛，問題外表簡單樸素，本質(zhì)上卻十分復(fù)雜深刻；解決問題的方法千變?nèi)f化，非常靈活，常常是一種問題一種解法。圖論研究的內(nèi)容非常廣泛，如圖的連通性、遍歷性、圖的計(jì)數(shù)、圖的著色、圖的極值問題、圖的可平面性等。下面具體研究圖論在農(nóng)村自來水管網(wǎng)設(shè)計(jì)方面的應(yīng)用。

1 農(nóng)村自來水管網(wǎng)優(yōu)化設(shè)計(jì)指標(biāo)

農(nóng)村自來水管網(wǎng)優(yōu)化設(shè)計(jì)的指標(biāo)主要有可靠性、水壓水量的保證性和經(jīng)濟(jì)性。

1.1 可靠性

可靠性是指在規(guī)定的使用狀態(tài)下、規(guī)定的時(shí)間內(nèi)完成預(yù)定功能的性能。對(duì)農(nóng)村飲水工程供水管網(wǎng)而言，預(yù)定功能是指在正常工作條件下，保證給水栓所需的水量和水壓。在工程設(shè)計(jì)中考慮到可靠性，就有可能減少因故障引起的損失和維修費(fèi)用。在管網(wǎng)優(yōu)化設(shè)計(jì)時(shí)，其可靠性應(yīng)達(dá)到在發(fā)生事故的情況下，水量和水壓不低于規(guī)定的限度，而在時(shí)間上不超過允許減少水量和降低水壓的時(shí)間。

1.2 水壓水量的保證性

在正常工作時(shí)，各個(gè)給水栓的水壓、水量要達(dá)到設(shè)計(jì)要求，以免水壓過高引起水量和能量的浪費(fèi)，防止下游因水壓降低導(dǎo)致水壓和水量的不足。

1.3 經(jīng)濟(jì)性

在農(nóng)村飲水供水工程中，經(jīng)濟(jì)性是在進(jìn)行管網(wǎng)優(yōu)化設(shè)計(jì)時(shí)所要考慮的一個(gè)重要指標(biāo)。管線的費(fèi)用主要與水管材料、長度和直徑等有關(guān)，因此，在管網(wǎng)設(shè)計(jì)時(shí)應(yīng)根據(jù)給水栓的布置確定最優(yōu)的管網(wǎng)布置方案，減小管網(wǎng)的長度;在此基礎(chǔ)上，確定管網(wǎng)的最優(yōu)管徑組合，以期達(dá)到整個(gè)管網(wǎng)的經(jīng)濟(jì)性。

以上設(shè)計(jì)目標(biāo)除了經(jīng)濟(jì)性外，其他方面都不易進(jìn)行定量評(píng)價(jià)。如用水量變化和管道損壞等原因使計(jì)算流量不同于實(shí)際流量，泵站的運(yùn)行方式、管理水平等也會(huì)影響管網(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)。

2 應(yīng)用圖論優(yōu)化自來水管網(wǎng)布置

在圖論中，圖是頂點(diǎn)與連接這些點(diǎn)的邊的集合，表示為G=（V，E），其中V是頂點(diǎn)的集合，E表示邊的集合。在管網(wǎng)的優(yōu)化布置中，將每個(gè)給水栓或配水水源看成是圖上的一個(gè)頂點(diǎn)，給水栓之間的連接管看作是邊，從而形成圖。通常以邊的長度或造價(jià)為邊的權(quán)重，它與兩給水栓之間的連接順序無關(guān)，因此稱之為賦權(quán)無向圖。當(dāng)圖G有n個(gè)頂點(diǎn)時(shí)，邊的數(shù)目為n（n-1）/2條，稱為無向完全圖。如果圖G中有兩個(gè)頂點(diǎn)U和V二者之間存在一條道路，則稱U和V是連通的，若圖G中任意兩頂點(diǎn)連通，則稱圖是連通的，否則稱為非連通的。

連通的沒有回路的圖稱為樹。它是圖的一種特殊形式，其數(shù)據(jù)元素（即給水栓的序號(hào)）有層次關(guān)系，某一層上的元素與上一層的一個(gè)元素聯(lián)結(jié)，與下一層的多個(gè)元素聯(lián)結(jié)。n個(gè)頂點(diǎn)時(shí)，只有n-1條邊，如多加一條邊即形成回路，成為環(huán)狀網(wǎng)，所以樹是無向圖中的非完全圖，且是極小連通子圖。若圖G的樹包含圖G的所有頂點(diǎn)，則稱為圖G的一棵生成樹或支撐樹。如果T=（V，E）是G的一個(gè)支撐樹，則稱E中所有邊的權(quán)之和為支撐樹T的權(quán)，記為W（T），如果支撐樹T的權(quán)W（T）是G的所有支撐樹的權(quán)中最小的，則稱T是G的最小生成樹。

2.1 最小生成樹法

圖的最小生成樹可采用Kruskal法和Prim法確定。Kruskal法是按權(quán)值遞增的順序來構(gòu)造最小生成樹，又稱避圈法。先將水源至各給水栓及各給水栓之間按遞增順序排列，再選最短兩條線段連接起來，然后由小到大連接各頂點(diǎn)，但不可與已選取的邊形成“圈”，如此將所有節(jié)點(diǎn)連接起來即可得到最小生成樹。Prim法的基本思想是：從某一點(diǎn)開始設(shè)為V1，則作S←Vl，然后尋找V/S中的點(diǎn)與S中點(diǎn)距離最短者，設(shè)為（Vk，Vi），其中Vk∈S，Vi∈V/S，則將（Vk，Vi）邊收入到樹T中來，且Vi進(jìn)入S。依次反復(fù)進(jìn)行，直到n個(gè)頂點(diǎn)用n-1條邊連接起來為止。

這兩種方法都可以找到每個(gè)問題的最小解。它們是兩種不同的算法，但Prim法回避了必須檢驗(yàn)圈的要求，也回避了將所有的邊按權(quán)值排序，從而節(jié)約了時(shí)間，提高了速度，因此比Kruskal法更有效。

對(duì)于管網(wǎng)的優(yōu)化布置，僅僅尋求最小生成樹并不能實(shí)現(xiàn)投資最少的目標(biāo)。最小生成樹僅是管網(wǎng)投資減少的一個(gè)因素，它所尋求的是整個(gè)管網(wǎng)的總長度最短，即所有頂點(diǎn)之間的最短連接，而不是一點(diǎn)到其余各點(diǎn)之間的最短連接。在管網(wǎng)布置時(shí)，假定各個(gè)管段的直徑是均一的，但當(dāng)水源位置不同時(shí)，各段管徑的大小有較大差異，因而對(duì)造價(jià)的影響較大。通過縮短流量和直徑較大的管段長度，同時(shí)增加流量較小的直徑較小的管道長度，使管網(wǎng)的總投資進(jìn)一步降低。這一問題可采用最短路徑法得以解決。

2.2 最短路徑法

在圖論中，最短路徑法是由荷蘭學(xué)者Dijkstra提出的，它可用于求解一個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短路徑問題。在管網(wǎng)布置中，可用最短路徑法求出確定的單一水源至其余各節(jié)點(diǎn)均為最短距離的樹，從而優(yōu)化管道布置，節(jié)省投資。

最短路徑法的基本思想是：從水源V出發(fā)，逐步向外探尋最短路，執(zhí)行過程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄下一個(gè)數(shù)，或者是從V到該點(diǎn)的最短路的權(quán)（記入P），或者是從K到該點(diǎn)的最短路的權(quán)的上界（記入T），不斷地修改T，并且把某一個(gè)T標(biāo)號(hào)的點(diǎn)改變?yōu)镻標(biāo)號(hào)的點(diǎn)，這樣至多經(jīng)過n-1步，就可求出從K到各點(diǎn)的最短路。

從理論上而言，上述方法可對(duì)管網(wǎng)進(jìn)行優(yōu)化計(jì)算，但在農(nóng)村自來水工程管網(wǎng)優(yōu)化設(shè)計(jì)中，由于其特殊性，在應(yīng)用時(shí)必須考慮其各自工程的特殊情況。

3 算例及討論

山西省農(nóng)村飲水任務(wù)很重，近幾年投入力度不斷加大。在這方面也進(jìn)行了不懈的實(shí)踐，下面以萬榮縣農(nóng)村自來水管網(wǎng)設(shè)計(jì)為例進(jìn)行敘述，簡化為示意圖1。

圖中V點(diǎn)為水源點(diǎn)，A～F點(diǎn)為用戶節(jié)點(diǎn)，各點(diǎn)之間距離為節(jié)點(diǎn)間權(quán)重。計(jì)算過程見表1，計(jì)算結(jié)果見圖2。為了便于管網(wǎng)良好運(yùn)行，取V~B段管徑為8cm，V~C和B~D段管徑為6cm，B~A，D~E和C~F段管徑為4cm。

表1 萬榮縣農(nóng)村管網(wǎng)賦權(quán)示意圖最短路計(jì)算表

自來水管網(wǎng)的設(shè)計(jì)計(jì)算經(jīng)過了從手算到電算，從憑經(jīng)驗(yàn)設(shè)計(jì)到優(yōu)化設(shè)計(jì)階段，這一過程是與計(jì)算方法和計(jì)算工具的發(fā)展相適應(yīng)的。傳統(tǒng)方法是憑經(jīng)驗(yàn)查閱大量表格進(jìn)行設(shè)計(jì)的，過程繁瑣，計(jì)算結(jié)果不準(zhǔn)確。隨著優(yōu)化理論的發(fā)展，自來水管網(wǎng)的優(yōu)化設(shè)計(jì)也相應(yīng)開展起來。在自來水管網(wǎng)優(yōu)化設(shè)計(jì)中，特別是針對(duì)農(nóng)村自來水管網(wǎng)分布分散的特點(diǎn)，圖論將發(fā)揮越來越大的作用。

4 結(jié)語

圖論是一種對(duì)農(nóng)村自來水管網(wǎng)設(shè)計(jì)進(jìn)行有效優(yōu)化的數(shù)學(xué)方法，是將復(fù)雜的農(nóng)村自來水管網(wǎng)處理為相應(yīng)的網(wǎng)絡(luò)圖，并建立相應(yīng)的數(shù)學(xué)模型，用原始數(shù)據(jù)來描述管網(wǎng)結(jié)構(gòu)，輸入的數(shù)據(jù)量少，不易出錯(cuò)，易于計(jì)算大型的復(fù)雜管網(wǎng)，其計(jì)算過程可同時(shí)考慮管網(wǎng)附件，如控制閥、加壓泵、逆止閥、減壓閥等，使計(jì)算結(jié)果更加符合實(shí)際，在農(nóng)村自來水管網(wǎng)設(shè)計(jì)中具有很好的應(yīng)用前景。