趙星明，王 萱

(山東農(nóng)業(yè)大學(xué)水利土木工程學(xué)院，山東 泰安 271018)

城鎮(zhèn)給水管網(wǎng)的投資占整個(gè)給水工程比例較大，因此其最優(yōu)化設(shè)計(jì)一直受到重視。最優(yōu)化設(shè)計(jì)的前提是對(duì)環(huán)狀給水管網(wǎng)的管段流量確定初分配方案，若給水管網(wǎng)的規(guī)模較小，可通過分析控制點(diǎn)位置以及大用戶的分布，確定主干管供水路線，較合理地分配管段流量。對(duì)于中等以上的城市，僅依靠主觀判斷分配給水管網(wǎng)的管段流量會(huì)造成較大誤差，不能滿足用戶的實(shí)際用水量，也不能實(shí)現(xiàn)最優(yōu)化設(shè)計(jì)。

初始流量分配可以采用最小平方和的流量分配法和截面法等，最小平方和法分配的管段流量比較均勻而使管道主次不分，截面法分配的管段流量不能滿足節(jié)點(diǎn)流量平衡的條件。若采用圖論理論把環(huán)狀給水管網(wǎng)中的若干條管段刪除，生成樹后再進(jìn)行初始流量分配，可符合節(jié)點(diǎn)流量連續(xù)性方程。把管網(wǎng)圖化為生成樹，須按照歐拉公式刪除與基環(huán)數(shù)一樣多的管段來(lái)破壞所有的環(huán)，并保持原管網(wǎng)的連通性，對(duì)一個(gè)規(guī)模較大的環(huán)狀給水管網(wǎng)，僅靠主觀判斷生成樹需花費(fèi)很多時(shí)間。

本文根據(jù)Kruskal算法對(duì)環(huán)狀管網(wǎng)生成樹問題進(jìn)行研究，利用帶權(quán)重的鄰接矩陣得到了最小生成樹，并在AutoCAD平臺(tái)上運(yùn)用深度優(yōu)化搜索方法，實(shí)現(xiàn)了刪除連枝自動(dòng)生成樹，可方便管段初始流量的計(jì)算，提高環(huán)狀給水管網(wǎng)的設(shè)計(jì)計(jì)算效率和準(zhǔn)確度。同時(shí)，通過人工干預(yù)保留一些管段流量易確定的連枝，以優(yōu)化環(huán)狀給水管網(wǎng)布局。

1 環(huán)狀給水管網(wǎng)生成樹的方法

一個(gè)連通管網(wǎng)圖G(V，E)，由N節(jié)點(diǎn)和M管段構(gòu)成，V和E為節(jié)點(diǎn)和管段的集合，根據(jù)圖論理論計(jì)算其內(nèi)環(huán)數(shù)L=M-N+1。若想把G(V，E)生成一棵樹需刪除與內(nèi)環(huán)數(shù)相等的L條管段，刪除的管段稱為連枝，保留下來(lái)的管段稱為樹枝。在環(huán)狀給水管網(wǎng)的工程設(shè)計(jì)中，連接管和末端管主要承擔(dān)本段沿線流量的分配，流量容易確定，可作為連枝刪除掉，一部分管段流量不易確定的主干管和轉(zhuǎn)輸管等作為樹枝保留下來(lái)，這些樹枝的管段流量可在生成樹管網(wǎng)圖上通過節(jié)點(diǎn)連續(xù)性方程求出。為了保留重要的主干管和轉(zhuǎn)輸管，把管網(wǎng)圖G(V，E)轉(zhuǎn)化為一個(gè)加權(quán)圖G(V，E，W)，W為管段權(quán)重Wij的集合，在此假設(shè)想保留下來(lái)管道的Wij=1，其權(quán)重最小，而其他管道的Wij>1，管道的權(quán)重越大越容易被刪除。需注意的是權(quán)重大于1的管道比需刪除的管段數(shù)L要多，所以權(quán)重大于1的管道不會(huì)全部刪除，也要保留一部分，哪些管道保留下來(lái)或被刪除掉是根據(jù)Kruskal算法確定的。

設(shè)T為G的一棵生成樹，管段eij的權(quán)為Wij，則T的權(quán)定義為:

(1)

所有生成樹中權(quán)重最小的是G的一棵最小生成樹，可以采用Kruskal等算法求得，剪枝環(huán)狀管網(wǎng)生成一棵最小樹。

2 Kruskal算法生成樹的實(shí)現(xiàn)

2.1 Kruskal算法的基本思想

含有n個(gè)節(jié)點(diǎn)的管網(wǎng)連通圖G(V，E，W)和其生成樹T的節(jié)點(diǎn)V集合相同，定義生成樹T(V，E，W)的初態(tài)為空集，即生成樹只是由n個(gè)節(jié)點(diǎn)構(gòu)成而無(wú)任何邊的n個(gè)非連通圖T=(V，{φ}，{φ})，因節(jié)點(diǎn)之間沒有管段，故每個(gè)節(jié)點(diǎn)自成1個(gè)連通分量。先對(duì)環(huán)狀管網(wǎng)圖G中的管段進(jìn)行分析和分類，人工賦予不同的權(quán)重。對(duì)管網(wǎng)圖G中的所有管段進(jìn)行第1次遍歷，若遍歷到的管段的權(quán)重最小，即為保留管段，則將此管段直接加入到最小生成樹T中的E集合。再對(duì)權(quán)重較大的管段進(jìn)行第2次遍歷，如果管段的2個(gè)節(jié)點(diǎn)依附于T的2個(gè)不同的連通分量，則將此管段加入最小生成樹T中的E集合，同時(shí)把2個(gè)連通分量連接為1個(gè)連通分量；若被遍歷到的2個(gè)節(jié)點(diǎn)同屬1個(gè)連通分量，說明連接此管段后會(huì)造成回路，故不連接這2個(gè)節(jié)點(diǎn)。遍歷所有管段后，可使T只有1個(gè)連通分量，便構(gòu)建了1棵連通的生成樹，可用于管段流量的初分配。

2.2 Kruskal算法的實(shí)現(xiàn)方法

根據(jù)環(huán)狀給水管網(wǎng)圖構(gòu)建帶權(quán)的鄰接矩陣M，鄰接矩陣M由4個(gè)元素組成，其格式為：

管段編號(hào)，管段的起點(diǎn)，終點(diǎn)，管段權(quán)值

以圖1的環(huán)狀給水管網(wǎng)為例，其鄰接矩陣保存格式及數(shù)據(jù)如表1所示，管段1、2、3、10和12的權(quán)值最小，屬保留的管段，其他管段按照Kruskal算法刪除連枝以生成樹。

圖1 環(huán)狀給水管網(wǎng)圖Fig.1 The looped pipe network of water supply

在使用Kruskal算法對(duì)環(huán)狀連通管網(wǎng)圖生成樹的實(shí)現(xiàn)過程中，根據(jù)鄰接矩陣的格式，構(gòu)建一個(gè)加權(quán)的2維管段數(shù)組Looped(Edge, 4)，分別儲(chǔ)存每個(gè)管段的編號(hào)、起點(diǎn)、終點(diǎn)和權(quán)值這4個(gè)元素，Edge為環(huán)狀管網(wǎng)的管段編號(hào)。還設(shè)置一個(gè)Root(VertexNum)數(shù)組，使用自定義函數(shù)Search搜索每個(gè)管段的起

表1 鄰接矩陣格式及數(shù)據(jù)Tab.1 Fortmat and data of adjacency matrix

點(diǎn)和終點(diǎn)所屬的連通分量，VertexNum為節(jié)點(diǎn)編號(hào)。Root(VertexNum)數(shù)組中每個(gè)節(jié)點(diǎn)VertexNum的初值為0，表示管網(wǎng)的各個(gè)節(jié)點(diǎn)在不同的連通分量上，遍歷到一條管段后，讀取管段的起點(diǎn)(StartVertex)和終點(diǎn)編號(hào)(EndVertex)，用Search自定義函數(shù)搜索2個(gè)節(jié)點(diǎn)所在樹的根結(jié)點(diǎn)，也就是在Root(VertexNum)數(shù)組中的序號(hào)。若StartVertex和EndVertex的根結(jié)點(diǎn)不同，表示所對(duì)應(yīng)的管段不在同一連通分量上，則將這條管段存儲(chǔ)在生成樹Tree數(shù)組中，并把StartVertex的值賦給終點(diǎn)數(shù)組Root(EndVertex)，合并2個(gè)節(jié)點(diǎn)所屬的連通分量為1個(gè)連通分量。

鄰接矩陣的排列順序影響著生成樹過程中連枝的選擇，可以對(duì)鄰接矩陣的權(quán)值從小到大進(jìn)行排序，僅遍歷一次便可構(gòu)建最小生成樹。因在環(huán)狀管網(wǎng)生成樹過程中，只有人工干預(yù)保留部分管段，所以管段的權(quán)值只有1和2，權(quán)值為1的管段優(yōu)先保留下來(lái)，權(quán)值為2的管段根據(jù)生成樹的算法再確定是否保留或刪除，為此可以對(duì)鄰接矩陣的權(quán)值不進(jìn)行排序，只是對(duì)管段進(jìn)行2次遍歷，第1次遍歷只把權(quán)值為1的管段直接存儲(chǔ)到Tree數(shù)組中，然后進(jìn)行第2遍歷，把權(quán)值為2的管段根據(jù)Kruskal算法存儲(chǔ)到Tree數(shù)組。

用Kruskal算法實(shí)現(xiàn)的過程中，首先把鄰接矩陣的元素以文本文件形式保存，程序讀取所有管段的編號(hào)、起點(diǎn)、終點(diǎn)和權(quán)值到Looped(Edge, 4) 數(shù)組，然后根據(jù)優(yōu)化搜索算法判斷每個(gè)管段是否在同一連通分量上，最后得到環(huán)狀管網(wǎng)圖的最小生成樹，以數(shù)組Tree(Edge, 4)的形式存儲(chǔ)并寫入交換格式文件中。

對(duì)于圖1管網(wǎng)圖按照表1的鄰接矩陣，用Kruskal算法構(gòu)建最小生成樹T，則會(huì)完全保留權(quán)重為1的管段1、2、3、10和12，刪除權(quán)重為2的部分管段6、7、9、11。得到的生成樹T的管段集合M={1，2，3，10，12，4，5，8}，節(jié)點(diǎn)集合V與管網(wǎng)圖G相同。若對(duì)得到的生成樹不是很滿意，可修改管段的權(quán)重，也可增加管段權(quán)重的級(jí)數(shù)為3級(jí)或更多，權(quán)值改為1、2和3，把最想刪除的管段權(quán)重設(shè)置為3，再通過程序生成最小樹。Kruskal算法的主程序代碼如下：

Option Base 1

Sub main()

Dim Root() As Integer

Dim i As Integer, j As Integer, k As Integer

Dim StartVertex As Integer, EndVertex As Integer

Dim VertexNum As Integer, Edge As Integer

Dim Looped() As Integer, Tree() As Integer

Open ActiveDocument.Path & "in.csv" For Input As #1

Input #1, VertexNum, Edge ‘讀取管網(wǎng)圖的節(jié)點(diǎn)總數(shù)和管段總數(shù)

ReDim Root(VertexNum)

ReDim Looped(Edge, 4)

ReDim Tree(Edge, 4)

For i = 1 To Edge

Input #1, Looped(i, 1), Looped(i, 2), Looped(i, 3), Looped(i, 4)

Next i

Close #1

For i = 1 To VertexNum

Root(i) = 0

Next i

Open ActiveDocument.Path & "out.csv" For Output As #2

Write #2, "管段編號(hào)", "起始節(jié)點(diǎn)", "終止節(jié)點(diǎn)", "管段權(quán)重"

For k = 1 To 2

For i = 1 To Edge

StartVertex = Search(Root, Looped(i, 2))

EndVertex = Search(Root, Looped(i, 3))

If (StartVertex = EndVertex) And Looped(i, 4) = 2 Then

Debug.Print Looped(i, 1) '刪除的連枝

End If

If (StartVertex <> EndVertex) And Looped(i, 4) = k Then

Root(EndVertex) = StartVertex

For j = 1 To 4

Tree(i, j) = Looped(i, j)

Write #2, Tree(i, j),

Next j

Print #2,

End If

Next i, k

Close #2

End Sub

自定義函數(shù)Search的代碼：

Function Search(Root() As Integer, VertexNum As Integer) As Integer

Dim i As Integer

i = VertexNum

Do While Root(i) > 0

i = Root(i)

Loop

Search = i

End Function

3 在AutoCAD平臺(tái)上搜索環(huán)狀管網(wǎng)生成樹的實(shí)現(xiàn)及算例研究

3.1 工程條件

某市區(qū)供水管網(wǎng)如圖2所示。在AutoCAD平臺(tái)上，假如所有管道的圖層為“鑄鐵管”，可采用遍歷技術(shù)對(duì)管段和節(jié)點(diǎn)進(jìn)行自動(dòng)編號(hào)，形成不帶權(quán)的3元素鄰接矩陣，以.csv交換格式文件形式保存[1,5]。對(duì)需保留的管道，手動(dòng)選擇并改變其圖層為“Tree”。為表示管道的不同權(quán)重，設(shè)定“Tree”圖層的線寬為0.35 mm，定義在該圖層的管道權(quán)值為1，設(shè)定“鑄鐵管”圖層的線寬為0.2 mm，表示管道權(quán)值為2。用Excel修改3元素鄰接矩陣，增加每條管道的權(quán)重元素，形成帶權(quán)的4元素關(guān)聯(lián)矩陣，即其矩陣元素仍按表1的格式存儲(chǔ)，數(shù)據(jù)內(nèi)容見表2。

表2 某市區(qū)供水管網(wǎng)鄰接矩陣Tab.2 The adjacency matrix of water supply pipe network

圖2 某市區(qū)供水管網(wǎng)現(xiàn)狀圖Fig.2 The water supply pipe network

3.2 在AutoCAD平臺(tái)上生成樹

首先使用前面的Kruskal算法程序，讀取某市區(qū)供水管網(wǎng)的鄰接矩陣，即表2的數(shù)據(jù)，判斷管段的2個(gè)節(jié)點(diǎn)的根結(jié)點(diǎn)是否相同，若相同則為應(yīng)刪除的連枝。根據(jù)歐拉公式，本算例有18個(gè)環(huán)，所以產(chǎn)生的連枝數(shù)也為18，具體刪除的管段見表3。

表3 刪除的管段Tab.3 The deleted pipe section

然后在AutoCAD平臺(tái)上遍歷搜索環(huán)狀給水管網(wǎng)的所有管段，用選擇集的方法識(shí)別管段編號(hào)，若遍歷的管段為表3中應(yīng)刪除的管段，則修改該管段到“0”圖層，也可直接刪除，非常直觀地實(shí)現(xiàn)了把環(huán)狀管網(wǎng)自動(dòng)生成樹，生成的樹狀管網(wǎng)如圖3所示，程序代碼如下：

Sub 刪除連枝()

Dim Linea As AcadLine

Dim Obj As AcadEntity '遍歷圖形對(duì)象用

Dim SSetColl As AcadSelectionSets '定義選擇集集合

Dim ssetObj As AcadSelectionSet '選擇集對(duì)象

Dim name As String '選擇集名稱

Dim Textobj As AcadText '寫直線編號(hào)用的文字對(duì)象

Dim Sp As Variant, Ep As Variant '直線兩端點(diǎn)

Dim Cp As Variant '直線中點(diǎn)坐標(biāo)，要計(jì)算

Dim Lp As Variant, Rp As Variant '為形成一個(gè)選擇框，定義左上角和右下角坐標(biāo)

Dim TextHeight As Single '定義管段編號(hào)的文字高度

ReDim Cp(0 To 2) As Double

ReDim Lp(0 To 2) As Double

ReDim Rp(0 To 2) As Double

Dim gpCode(0) As Integer

Dim dataValue(0) As Variant

Dim groupCode As Variant, dataCode As Variant

gpCode(0) = 0

dataValue(0) = "TEXT"

圖3 某市區(qū)供水管網(wǎng)自動(dòng)生成樹Fig.3 Automatic spanning tree of the water supply pipe network

groupCode = gpCode

dataCode = dataValue

TextHeight = 100 '管段編號(hào)和節(jié)點(diǎn)編號(hào)的文字高度

name = "SSET" '選擇集名字

Set SSetColl = ThisDrawing.SelectionSets

On Error Resume Next

For Each Obj In ThisDrawing.ModelSpace

If Obj.ObjectName = "AcDbLine" Then

Set Linea = Obj

Sp = Linea.Startpoint: Ep = Linea.Endpoint

Cp(0) = (Sp(0) + Ep(0)) / 2: Cp(1) = (Sp(1) + Ep(1)) / 2: Cp(2) = (Sp(2) + Ep(2)) / 2 '直線中點(diǎn)，即管段編號(hào)插入點(diǎn)

'以下為選擇集定義容錯(cuò)處理的代碼

If Not IsNull(SSetColl.Item(name)) Then

Set ssetObj = SSetColl.Item(name)

ssetObj.Delete

End If

Set ssetObj = SSetColl.Add(name)

Lp(0) = Cp(0) - TextHeight: Lp(1) = Cp(1) + TextHeight: Lp(2) = Cp(2) '在直線中點(diǎn)形成一個(gè)矩形選擇框

Rp(0) = Cp(0) + TextHeight: Rp(1) = Cp(1) - TextHeight: Rp(2) = Cp(2)

ssetObj.Select acSelectionSetWindow, Lp, Rp, groupCode, dataCode

If ssetObj.Count = 1 Then

Set Textobj = ssetObj.Item(0)

If InStr("[12][16][17][21][29][31][34][38][45][46][50][56][58][60][61][62][63][65]", Textobj.TextString) Then

Debug.Print Textobj.TextString

Linea.Layer = "0" '修改連枝到“0”圖層，也可直接刪除

Textobj.Layer = "0"

End If

Else

MsgBox "節(jié)點(diǎn)編號(hào)錯(cuò)誤" '可能沒有編號(hào)，或者編號(hào)字體太大或者矩形選取框太小等原因

Exit For

End If

End If

Next Obj

End Sub

4 結(jié) 語(yǔ)

本文根據(jù)Kruskal最小生成樹算法的基本思想，對(duì)環(huán)狀給水管網(wǎng)的鄰接矩陣進(jìn)行深度優(yōu)化搜索，篩選出連枝而實(shí)現(xiàn)了自動(dòng)生成樹的目的。在AutoCAD平臺(tái)上遍歷所有管段可自動(dòng)生成帶權(quán)重的鄰接矩陣，根據(jù)Kruskal算法篩選出應(yīng)刪除的管段，使環(huán)狀管網(wǎng)直觀地生成樹。程序能夠根據(jù)每個(gè)管段的權(quán)重，識(shí)別人為保留的管段，生成的樹得到優(yōu)化，有助于提高大規(guī)模環(huán)狀管網(wǎng)的設(shè)計(jì)效率。

在節(jié)點(diǎn)流量和連枝流量已知的情況下，滿足節(jié)點(diǎn)流量平衡的條件，利用Kruskal算法自動(dòng)生成樹，使管段流量初分配很容易實(shí)現(xiàn)。

□

參考文獻(xiàn)：

[1] 趙星明,王 萱.環(huán)狀給水管網(wǎng)關(guān)聯(lián)矩陣的建立[J].中國(guó)農(nóng)村水利水電,2012,(11):129-131,135.

[2] 嚴(yán)煦世,劉遂慶.給水排水管網(wǎng)系統(tǒng)[M]. 3版. 北京:中國(guó)建筑工業(yè)出版社,2014:79-80.

[3] 唐策善,李龍澍,黃劉生.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：高等教育出版社,2000:123-135.

[4] 盧有杰, 吳煒煜.C語(yǔ)言高級(jí)程序設(shè)計(jì)[M]. 北京:清華大學(xué)出版社, 1991:19-86.

[5] 趙星明,王 萱.基于擴(kuò)展數(shù)據(jù)的給排水管網(wǎng)拓?fù)潢P(guān)系的構(gòu)建[J].山東農(nóng)業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,43(4):549-554.

[6] 宋 芹,趙星明,艾典勝.輸水管道水錘分析與防護(hù)技術(shù)[J].山東農(nóng)業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,48(1):84-87.

[7] SeijiKataoka,TakeoYamada.Algorithms for the minimum spanning tree problem with resource allocation[J].Operations Research Perspectives, 2016,(3):5-13.