基于Petri網(wǎng)的最大流-最小割問題建模與求解

， ，

(1.福建工程學院 信息科學與工程學院， 福建 福州 350118； 2.福建工程學院 福建省大數(shù)據(jù)挖掘與應用技術重點實驗室， 福建 福州 350118； 3.中南大學 信息科學與工程學院， 湖南 長沙 410083； 4.長沙理工大學 計算機與通信工程學院， 湖南 長沙 410076 )

圖論中有許多經(jīng)典的問題，包括最短路徑問題、最大流-最小割問題等。對于這些問題，學者們有過大量的研究并提出了一系列求解辦法。Petri網(wǎng)(PN)是一種可以用圖形表示的數(shù)學對象，具有深刻的數(shù)學內(nèi)涵基礎，這使得它在形式化和求解圖論問題時具有極大的優(yōu)勢。近年來，已

有許多將PN與圖論問題相結合的研究成果，例如：文獻[1]使用PN對代謝路徑進行建模仿真，其中應用圖的最大割來處理超過一定長度和寬度的代謝路徑；文獻[2-3]將PN應用于故障樹形圖分析中，用以實現(xiàn)系統(tǒng)最小割集的求解；文獻[4]將粗糙集理論與PN相結合進行隨機流網(wǎng)絡可靠性評價。但是國內(nèi)外基于PN的最大流-最小割問題研究并不多見，相關理論也有待完善。

最大流(max-flow)與最小割(min-cut)問題是一類典型的對偶問題，涉及計算機、圖論和運籌學，是一類經(jīng)典的組合優(yōu)化問題，也可以認為是特殊的線性規(guī)劃問題[5]。在圖形[6]、圖像分割[7-8]，交通運輸網(wǎng)絡分析[9-10]等諸多控制、決策領域有著廣泛的應用。經(jīng)典的解決方法有預流-推進法(preflow push method)、增廣路徑法(augmenting path method)等。該問題可進一步擴展到不確定圖最可靠最大流問題[11]，節(jié)點和邊都有容量的有向平面網(wǎng)絡中的最小截和最大流問題[12]等。文獻[4- 5]與本文研究工作有著較高的相關度：文獻[4]簡單描述了一種使用PN來表示流網(wǎng)絡的方法，但其研究重點在于對隨機流網(wǎng)絡可靠性進行分析，所以在有關系統(tǒng)模型的含義及系統(tǒng)模型準確性等方面并未深入研究；文獻[5]所提出的流網(wǎng)絡PN模型可以說是[4]中模型的一種改進，但為求最大流，用戶需事先確定“擁堵結點”，并進行一系列的設置，且不論其提出模型的準確性和完整性，該方法中過多的人為干預對問題的求解與表達十分不利。

本文在增廣路徑法思想的基礎上給出了最大流-最小割問題的一種PN形式化表達，通過相關分析、證明深入闡述了其中的機制與原理。該模型無需額外的控制機制，能夠有效解決最大流-最小割問題。

1 基本性質(zhì)

1.1 問題的定義

1.1.1 流網(wǎng)絡、流及流的值

定義1[13]流網(wǎng)絡G=(V,E)是一個有向圖，其中每條邊(u,v)∈E均有一非負容量c(u,v)>0。如果E包含一條邊(u,v)，則絕不會存在與其方向相反的邊(v,u)。如果(u,v)?E則c(u,v)=0。且決不允許存在自循環(huán)的邊。流網(wǎng)絡中有兩個特別的頂點：源點s和匯點t。每個頂點均處于從源點到匯點的某條路徑上。

定義2[13]設G=(V,E)是一個流網(wǎng)絡，其容量函數(shù)為c。設s為網(wǎng)絡的源點，t為匯點，則G的流是一個實值函數(shù)f:V×V→R，且滿足下列兩個性質(zhì)：

容量限制：對所有u,v∈V，要求

0≤f(u,v)≤c(u,v)

流守恒性：對所有u∈V-{s,t}，要求

非負值f(u,v)稱為從頂點u到頂點v的流。如果(u,v)?E，則從u到v沒有流，且f(u,v)=0。

定義3[13]流f的值|f|定義為

一般來說，一個流網(wǎng)絡中進入源點的總流為0，因此流的值為從源點出發(fā)的總流，也等于進入?yún)R點的總流。

1.1.2 最大流問題

通過上述定義可以引出最大流問題的描述：給出一個具有源點s和匯點t的流網(wǎng)絡G，希望找出從s到t的最大值流。在某些應用中，也許僅僅知道最大流就滿足要求了，但一般情況下，希望知道達到該值的流(邊流量值)[14]。

圖1(a)是文獻[13]中關于流網(wǎng)絡所舉的一個例子，簡單來說其模型化描述了這么一個實際問題：Lucky Puck公司需要將他們所制造的冰球通過卡車從生產(chǎn)地s運送到倉庫所在地t。因為卡車按指定路線(邊)在兩城市(頂點)間行駛且其容量有限，所以每天在每城市u和v之間至多裝運c(u,v)箱產(chǎn)品(用數(shù)字標識于有向邊上)。他們的目標是確定每天所能運輸?shù)淖畲笙鋽?shù)，并按這一數(shù)量進行生產(chǎn)。

文獻[15]指出：Petri網(wǎng)不僅僅是一種可以用圖形表示的數(shù)學對象，它首先是一種物理對象，因為它把尊重自然規(guī)律作為第一要義。一個好的系統(tǒng)模型不能只存在于紙面上，活躍于論文中。它必須能夠用來描述物理世界的客觀存在，使客觀存在成為論文的研究對象。下節(jié)將介紹使用PN對上述實際問題的形式化描述。

1.2 Petri網(wǎng)

有關PN的基礎概念詳見文獻[15]，本節(jié)只對本文涉及到的性質(zhì)及主要概念進行介紹。令N=(P,T;F)是一個Petri網(wǎng)(簡稱為網(wǎng))，P、T及F分別指代庫所、變遷和有向弧。Σ=(N,K,W,M0)是一個網(wǎng)系統(tǒng)，其中K，W和M0依次是N上的容量函數(shù)、權函數(shù)和標識。M0稱為Σ的初始標識。

(a)文獻[13]中關于Lucky Puck公司卡車運輸問題的流網(wǎng)絡f； (b),(c) 本文所提出的關于f的兩種PN形式化描述圖1 一個流網(wǎng)絡的實例Fig.1 Demonstration of the flow network

為應用系統(tǒng)建立PN模型，首要需決定什么是系統(tǒng)的變遷，什么是系統(tǒng)的庫所。流網(wǎng)絡中具有頂點、邊及邊上的容量等元素，而PN中的庫所可以用來表示存放資源的場所，變遷則可以代表某種行為的發(fā)生過程。

因此使用PN來形式化流網(wǎng)絡的一種方法是使用變遷和有向弧來表示流網(wǎng)絡的邊和資源流動的行為；用一類庫所(圖1(b)中的s，v1等)來表示流網(wǎng)絡中的頂點，另一類庫所(圖1(b)中的P)來表示邊上的容量限制。那么，網(wǎng)絡中的流對應著資源托肯按照變遷規(guī)則從一個頂點庫所轉移至另一頂點庫所。依照該思想可以將圖1(a)問題轉換為圖1(b)中的PN模型。

圖1(c)展示了流網(wǎng)絡的另一種PN形式化表示，仍使用庫所表示頂點，變遷代表資源流動的過程，與圖1(b)中不同的是這里使用弧上的權函數(shù)W(可以是標量或者如圖1(c)中m01等所標識的變量，但權值不大于邊容量)來表示流網(wǎng)絡邊上的實際流量。本文將采用圖1(c)中的方法來表示流網(wǎng)絡，關于權函數(shù)W的設置將在第3節(jié)進行相應的陳述。

2 最大流-最小割問題建模與分析

L R Ford和 D R Fulkerson在 1962年提出了解決最大流問題的一種有效途徑。這是一種沿著從源點到匯點的路徑上不斷增加流量的通用方法，它是許多算法的基礎。在一般文獻中稱之為Ford-Fulkerson方法，即增廣路徑方法。

本文采用與增廣路徑方法類似的思想來構造流網(wǎng)絡的殘留網(wǎng)絡PN模型，并求解最大流-最小割問題。為了便于類比，首先給出增廣路徑方法的偽代碼。

算法1 FORD-FULKERSON-METHORD.

輸入：流網(wǎng)絡G，源點s，匯點t

輸出：流f

1 BEGIN流f為0

2 WHILE殘留網(wǎng)絡Gf中存在一條增廣路徑p

3 DO 沿路徑p增加流f

4 END

2.1 基于PN的殘留網(wǎng)絡建模

本節(jié)討論對流網(wǎng)絡G所對應的殘留網(wǎng)絡Gf建模。由于Gf不僅包含原網(wǎng)絡中的邊，還包含其反向邊，因此可以通過修改圖1(b)中模型來構造流網(wǎng)絡的殘留網(wǎng)絡模型。其詳細過程如下：

(1)對于流網(wǎng)絡G=(V,E)，對其任意頂點v∈V，構造所對應的庫所Pv；對于u,v∈V且(u,v)∈E，構造變遷和弧連通庫所Pu，Pv，弧的方向與(u,v)方向一致，將該類變遷統(tǒng)一記作T。

(2)為每個T構造一個前集庫所，統(tǒng)一記作P，代表邊上的容量，且初始化資源數(shù)為所對應邊上的容量數(shù)；為每個T構造一個后繼庫所，統(tǒng)一記作P′，初始化資源數(shù)為0。圖2(a)所示為(u,v)∈E且v=t的情況。

(3)進一步構造除包含匯點t外的所有邊所對應的反向邊模型。對所有(u,v)∈E∧v≠t，添加變遷T′使得·T′={Pv,P′}，T′·={Pu,P}，如圖2(b)所示。其中·T′和T′·分別代表T′的前集和后集。

(a)兩鄰接頂點之一是匯點的情況

(b)其他情況圖2 殘留網(wǎng)絡PN模型中兩鄰接頂點之間的關系圖Fig.2 Two cases of two neighbouring vertexes in the residual network PN Model

因此，在殘留網(wǎng)絡Petri網(wǎng)模型中，任意邊的兩端頂點有且僅有2種關系：要么如圖2(a)所示(兩個頂點其中一個為匯點t)，要么如圖2(b)所示(其他情況)。值得注意的是，庫所P與P′有多重含義：以圖2(b)為例，P中資源數(shù)目既標識了邊(u,v)上的殘留容量(residual capacity)又可看作邊(v,u)上的流。P′中資源數(shù)目在標識邊(u,v)上流的同時又可表示邊(v,u)上的殘留容量。另外，從PN原理角度來看，P與P′互為補庫所，從而避免了沖撞的發(fā)生，為系統(tǒng)的安全性提供了保障[16]。按照上述構造規(guī)則，圖3(a)展示了圖1(a)中流網(wǎng)絡所對應的殘留網(wǎng)絡在某一狀態(tài)標識下的PN模型。為了模擬資源的流動，給予s對應庫所初始狀態(tài)標識為一遠大于最大流的數(shù)，這里取值100。

2.2 模型分析及證明

本文給出了流網(wǎng)絡及其殘留網(wǎng)絡的PN模型，以描述物理世界的客觀存在，即系統(tǒng)模型的仿真性。下面通過相關的分析及證明來確保所給模型的正確性。

按照資源在PN中流動的法則，在不受任何外部因素控制下，殘留網(wǎng)絡PN系統(tǒng)最終可以達到并總是處于一系列狀態(tài)，這類狀態(tài)的一個共同特點是系統(tǒng)的一些頂點庫所中不會再有資源流動，這為尋找最大流和最小割提供了幫助。后面將證明，對于流網(wǎng)絡G=(V,E)，如果其殘留網(wǎng)絡PN模型中一些頂點庫所中不再有資源流動，則意味著已經(jīng)找不到任何路徑使得資源從s到t。這些資源不再流經(jīng)的頂點(例如圖3(a)中的v3)與匯點t組成一個集合Ct，其余頂點為另一個集合Cs=V-Ct，則Ct、Cs是G的一個最小割集。

眾所周知，一個最大流量經(jīng)常對應著多個最大流分布。事實上，如果上述集合Cs中資源全部回流至源點，則該過程中不同的返回路徑選擇將對應不同的最大流分布。例如，當圖3(a)所示頂點v1，v2，v4中資源全部流回至s中，則只可能存在3種可能性(使用箭頭代表資源流向)：(1)1個資源v4→v2，2個資源v2→s，1個資源v1→s；(2)1個資源v4→v2，1個資源v2→s，1個資源v2→v1，2個資源v1→s；(3)1個資源v4→v2，2個資源v2→v1，3個資源v1→s。他們分別對應于圖3(b、c、d)所示的流網(wǎng)絡中3種最大流分布。因此，特定的最大流分布可以通過特定回流路徑的決策選擇進行獲取。

前面從直觀分析的角度闡述了一些觀點，下面通過證明來進行論述。

首先需要關注的是PN模型中元素在實際問題中的意義，關于P′及P類庫所中資源數(shù)的含義在2.1節(jié)已經(jīng)詳細論述過，為了方便引用，將其表述為性質(zhì)1。其正確性從殘留網(wǎng)絡PN模型的構造規(guī)則及定義2易得。

引理1殘留網(wǎng)絡的PN模型中，資源托肯從s到t的所經(jīng)過的路徑等價于一條增廣路徑。

證明 不妨令殘留網(wǎng)絡的PN模型中，資源托肯從s到t有一條路徑p′，則總可以找到一條從s到t簡單路徑p，使得p與p′等價：

如果p′是一條簡單路徑，那么p=p′。

如果p′是含有一條環(huán)路的路徑，不妨設vi處存在環(huán)路vi→vj→vi(如圖4所示)，首先根據(jù)殘留網(wǎng)絡構造規(guī)則，vi必不等于t(因為t處不會存在環(huán)路)。由構造規(guī)則(3)易知，資源從vi出發(fā)經(jīng)由環(huán)路再回到自身前后，環(huán)路上的資源狀態(tài)不會發(fā)生改變。因此刪除環(huán)路后的簡單路徑p與原路

圖3 基于殘留網(wǎng)絡PN模型的最大流求解Fig.3 Residual network PN model based maximum flow solution

徑p′等價。

如果p′是含有多條環(huán)路的路徑，則刪除所有環(huán)路后的簡單路徑p與p′等價。

增廣路徑定義為殘留網(wǎng)絡中從s到t的一條簡單路徑。因此，綜上所述，殘留網(wǎng)絡的PN模型中，資源托肯從s到t的所經(jīng)過的路徑等價于一條增廣路徑。證畢。

圖4 殘留網(wǎng)絡中從s到t的某條包含環(huán)路的路徑Fig.4 A case of a path from s to t with loops in the residual network

引理2殘留網(wǎng)絡的PN模型中，每單位資源托肯從s到達t等價于在對應的增廣路徑上增加一個單位的流。

因此，每個單位資源托肯從s到達t，等價于其所確定的一條增廣路徑上相應的P類或者P′類庫所中增加一個托肯，即路徑的邊上增加一個單位流。證畢。

定理1當殘留網(wǎng)絡PN模型找不到任何路徑聯(lián)通s與t時，網(wǎng)絡達到最大流，t中的資源數(shù)等于最大流值。

分析 可以通過證明該方法與算法1所示增廣路徑方法等價來求證。

證明 由引理1和2可知，殘留網(wǎng)絡中單位資源從s到達t等價于找到了一條增廣路徑，并沿該路徑增加了一個單位的流。隨著從s出發(fā)的資源逐步流入t中，最終將找不到這樣的一條路徑。因此該方法與增廣路徑方法等價。

增廣路徑方法中找不到任何從s到t的增廣路徑時，網(wǎng)絡達到最大流。相應的，殘留網(wǎng)絡PN模型找不到任何路徑聯(lián)通s與t時，網(wǎng)絡達到最大流。根據(jù)定義3，最大流值等于所有進入?yún)R點的流，即殘留網(wǎng)絡PN模型中t對應庫所中的資源數(shù)。證畢。

定理2殘留網(wǎng)絡PN模型中的最大活的(live)子圖所含頂點集合Cs與其余頂點集合Ct構成了流網(wǎng)絡的最小割(Cs，Ct)。

證明 活系統(tǒng)要求每個變遷在任何可達標識下都是潛在可發(fā)生的。

當流網(wǎng)絡G對應殘留網(wǎng)絡PN模型找不到任何路徑聯(lián)通s與t時，記Cs={v∈V:殘留網(wǎng)絡PN模型中從s到v存在一條通路}并且Ct=V-Cs。由殘留網(wǎng)絡的構造規(guī)則可知，如果資源可以從s流至v，那么也可以從v流回s，因此Cs為其最大活的子圖所含頂點集合。

因為s∈Cs∧t?Cs，所以劃分(Cs，Ct)是一個割。它對應與增廣路徑法得到的一個最小割。證畢。

至此，已經(jīng)論述如何使用PN求得任意流網(wǎng)絡的最大流值和最小割集，圖3中的虛線標明了流網(wǎng)絡的一個最小割。但是實際應用中往往希望知道達到該值時各條邊上的實際流量值。性質(zhì)1表明，P′類庫所中的資源數(shù)代表了流網(wǎng)絡邊上的流。所以當網(wǎng)絡達到最大流時P′類庫所中的資源數(shù)就是該問題的解。方法是當殘留網(wǎng)絡PN模型中找不到任何從源點到匯點的路徑后，引導頂點庫所中的資源全部回流至源點，使得除s，t外的頂點庫所不再含有資源托肯。圖5給出了結合流網(wǎng)絡及其殘留網(wǎng)絡并包含資源回流機制的完整PN模型，下節(jié)將進行詳細介紹。

圖5 流網(wǎng)絡最大流-最小割問題完整的PN模型Fig.5 An integrated PN model that describes and solves the max-flow/min-cut problem for a given flow network

3 基于PN的最大流-最小割問題求解

本節(jié)將結合2.2節(jié)所提出的殘留網(wǎng)絡PN模型以及圖1(c)所示的流網(wǎng)絡PN模型對給定的流網(wǎng)絡進行仿真求解。其中，求解的過程是通過資源托肯在殘留網(wǎng)絡PN模型系統(tǒng)(即圖5上半部分)中的流動來實現(xiàn)的，而流網(wǎng)絡PN模型系統(tǒng)(即圖5下半部分)則主要用于對所求得的最大流及其分布進行展示。

以圖1(a)的流網(wǎng)絡為例，能夠求得并展示：(1)兩個最小割集；(2)流網(wǎng)絡的最大流值；(3)某一流分布。具體來說，首先在殘留網(wǎng)絡PN模型的源點庫所sf中指定足夠數(shù)量的托肯(例如圖5中所初始指定的100個托肯)，當大量托肯經(jīng)過一段時間的流動以后，模型中的頂點庫所將會分為有資源流經(jīng)和沒有資源流經(jīng)的兩類，由定理2可知，這兩個集合即為所求的兩個最小割集。其次，在獲得最小割的同時殘留網(wǎng)絡PN模型系統(tǒng)也將達到最大流狀態(tài)，為了獲得該最大流值，添加如圖5中tf所示的庫所。當達到最大流狀態(tài)時tf中的資源數(shù)將等于所有進入?yún)R點庫所tf′的資源數(shù)，即最大流值。最后，為了確定所有邊上的實際流量值(即流分布)，為源點庫所sf添加一個如圖5中T1所示的后繼變遷，從而使得所有剩余資源都經(jīng)由sf到達P1的目的。當P1中資源數(shù)達到sf中初始資源數(shù)時，所有P′類庫所中的資源數(shù)(即圖5上半部分中m01等變量所代表的數(shù)值)都將確定下來，這些數(shù)值即為最大流的分布。

通過上述殘留網(wǎng)絡PN模型系統(tǒng)獲得的數(shù)據(jù)可以在如圖5下半部分所示的流網(wǎng)絡中進行展示。例如最大流的值被作為源點庫所s的初始資源數(shù)，m01、m02等流分布值將被指定為對應邊的權值。另外，新添加的變遷T2使得最大流從源點到匯點后能夠進入下一次的循環(huán)，正如Lucky Puck公司卡車運輸問題中第2天需要按照前1天相同的運輸方案繼續(xù)運送冰球一樣。

4 結語

本文在增廣路徑法思想基礎上給出了最大流-最小割問題的PN形式化描述及其求解方法，包括流網(wǎng)絡及其對應殘留網(wǎng)絡PN模型的構造流程，PN模型各元素在問題中代表的實際意義分析，并給出了獲取最大流各個分布的方法，證明了PN模型中達到最大流的條件和通過活性分析可以得到一個最小割的結論，最后將殘留網(wǎng)絡和流網(wǎng)絡PN模型結合起來給出最大流-最小割問題完整的解決方案。

將PN應用于最大流-最小割問題的優(yōu)越性主要體現(xiàn)在：(1)PN對實際問題形式化表述時的直觀性；(2)PN擁有S_補、活性分析等獨特的系統(tǒng)建模和分析功能支持；(3)PN仿真過程易于從局部著手表現(xiàn)所模擬對象的動態(tài)變化等。因為最大流-最小割問題可以進一步擴展為最小費用最大流問題，不確定圖最可靠最大流問題，節(jié)點和邊都有容量的有向平面網(wǎng)絡中的最小割和最大流等問題，這類問題的PN形式化建模與求解有著可觀的研究價值，也為下一步工作提供了可行的研究方向。

[1] GENRICH H, KüFFNER R, VOSS K. Executable Petri net models for the analysis of metabolic pathways[J]. International Journal on Software Tools for Technology Transfer, 2001, 3(4): 394-404.

[2] 尹延通,劉高飛,季亮.基于最小割集的光學測云系統(tǒng)故障診斷[J].延邊大學學報(自然科學版),2016,42(3):267-270.

[3] 張永發(fā),蔡琦,趙新文.應用Petri網(wǎng)模型改進最小割集的算法[J].核動力工程,2007,28(5):63-68.

[4] 劉玲艷,吳曉平,田樹新.基于粗糙集和Petri網(wǎng)的隨機流網(wǎng)絡可靠性評價方法[J].控制與決策,2010,25(8):1273-1276.

[5] 胡雄鷹,胡斌,張金隆,等.基于Petri網(wǎng)求解網(wǎng)絡最大流的并發(fā)仿真方法[J].武漢理工大學學報(信息與管理工程版),2010,32(1):27-30.

[6] FAN L, LIU K. Paint mesh cutting[J]. Computer Graphics Forum, 2011, 30(2): 603-611.

[7] 劉松濤，殷福亮.基于圖割的圖像分割方法及其新進展[J].自動化學報,2012,38(6):912-922.

[8] DELONG A, OSOKIN A, ISACK H N, et al. Fast approximate energy minimization with label costs[C]∥ IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2012: 1-27.

[9] 向紅艷,張鄰,楊波.基于最大流的路網(wǎng)結構優(yōu)化[J].西南交通大學學報,2009,44(2):284-288.

[10] 寇瑋華,李宗平.運輸網(wǎng)絡中有流量需求的轉運結點最大流分配算法[J].西南交通大學學報,2009,44(1):118-121.

[11] 蔡偉,張柏禮,呂建華.不確定圖最可靠最大流算法研究[J].計算機學報,2012,35(11):2371-2380.

[12] 張憲超,江賀,陳國良.節(jié)點和邊都有容量的有向平面網(wǎng)絡中的最小截和最大流[J].計算機學報,2006,29(4):544-551.

[13] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms, Third[M]. London: The MIT Press, 2009.

[14] SEDGEWICK R.算法:C語言實現(xiàn)(第5部分:圖算法)[M].霍紅衛(wèi)，譯.北京:機械工業(yè)出版社,2010.

[15] 袁崇義. Petri 網(wǎng)原理與應用[M].北京:電子工業(yè)出版社,2005.

[16] 劉石堅,樂曉波,鄒崢.關于 Petri 網(wǎng)系統(tǒng)S-補相關定理的補充證明及其分析[J].系統(tǒng)仿真學報,2009,40(S2):1-5.