， ，

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

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

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

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

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

1 基本性質(zhì)

1.1 問題的定義

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

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

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

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

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

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

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

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

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

1.1.2 最大流問題

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

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

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

1.2 Petri網(wǎng)

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

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

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

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

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

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

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

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

算法1 FORD-FULKERSON-METHORD.

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

輸出：流f

1 BEGIN流f為0

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

3 DO 沿路徑p增加流f

4 END

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

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

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

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

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

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

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

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

2.2 模型分析及證明

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

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

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

前面從直觀分析的角度闡述了一些觀點(diǎn)，下面通過證明來進(jìn)行論述。

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

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

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

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

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

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

徑p′等價(jià)。

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

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

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

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

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

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

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

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

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

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

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

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

因?yàn)閟∈Cs∧t?Cs，所以劃分(Cs，Ct)是一個(gè)割。它對應(yīng)與增廣路徑法得到的一個(gè)最小割。證畢。

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

圖5 流網(wǎng)絡(luò)最大流-最小割問題完整的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é)將結(jié)合2.2節(jié)所提出的殘留網(wǎng)絡(luò)PN模型以及圖1(c)所示的流網(wǎng)絡(luò)PN模型對給定的流網(wǎng)絡(luò)進(jìn)行仿真求解。其中，求解的過程是通過資源托肯在殘留網(wǎng)絡(luò)PN模型系統(tǒng)(即圖5上半部分)中的流動(dòng)來實(shí)現(xiàn)的，而流網(wǎng)絡(luò)PN模型系統(tǒng)(即圖5下半部分)則主要用于對所求得的最大流及其分布進(jìn)行展示。

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

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

4 結(jié)語

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

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

[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] 尹延通,劉高飛,季亮.基于最小割集的光學(xué)測云系統(tǒng)故障診斷[J].延邊大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,42(3):267-270.

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

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

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

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

[7] 劉松濤，殷福亮.基于圖割的圖像分割方法及其新進(jìn)展[J].自動(dòng)化學(xué)報(bào),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)結(jié)構(gòu)優(yōu)化[J].西南交通大學(xué)學(xué)報(bào),2009,44(2):284-288.

[10] 寇瑋華,李宗平.運(yùn)輸網(wǎng)絡(luò)中有流量需求的轉(zhuǎn)運(yùn)結(jié)點(diǎn)最大流分配算法[J].西南交通大學(xué)學(xué)報(bào),2009,44(1):118-121.

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

[12] 張憲超,江賀,陳國良.節(jié)點(diǎn)和邊都有容量的有向平面網(wǎng)絡(luò)中的最小截和最大流[J].計(jì)算機(jī)學(xué)報(bào),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語言實(shí)現(xiàn)(第5部分:圖算法)[M].霍紅衛(wèi)，譯.北京:機(jī)械工業(yè)出版社,2010.

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

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