運(yùn)籌學(xué)——圖與網(wǎng)絡(luò)分析(參考版)
2025-05-18 22:11本頁面
【正文】 OR3 42 舉例 1：解水網(wǎng)最大流問題 。 ?fij39。 OR3 41 調(diào)整過程 ? 1）按上一步的第一個標(biāo)號用反向追蹤法找出增廣鏈。若收點(diǎn)得到標(biāo)號，說明存在增廣鏈，轉(zhuǎn)調(diào)整過程。 ? 若?。? vj ， vi ）上 , fji＞ 0 ，則令 l(vj)＝min[l(vi), fji]并給 vj以標(biāo)號（ － vi ， l(vj) ）。 OR3 40 標(biāo)號過程 ? 1）給發(fā)點(diǎn)以標(biāo)號（ 0， +∞） 。 ? 第一步 標(biāo)號過程，通過標(biāo)號來尋找可增廣鏈； ? 第二步 調(diào)整過程，沿可增廣鏈調(diào)整 f，以增加流量。于是）（所以，）（）（顯然有：）于是得截集（記的增廣鏈，故因?yàn)椴淮嬖陉P(guān)于則令且若則令且若令fVVfVVvvVVvvcfVVVVVvfVvfVvVvcfVVvcvVjijiijijtjjiijijijs**1*1**1*1*1*1**1*1*1*1*1**1*1*1**1i*1,)(,),(0,),(.,\.,0,v??????????????????OR3 38 求最大流的方法：標(biāo)號法 ? 方法很簡單：首先找到一條增廣鏈，沿此進(jìn)行最大可能調(diào)整，再找增廣鏈，再調(diào)整，直到?jīng)]有增廣鏈為止。 ?f*f*f*f*f*f*OR3 37 再證明：若 D中不存在關(guān)于 的增廣鏈，則該流是最大流。令 ： 由增廣鏈的定義可知 ，令： 0????????????????????????),(),(),(*****vvfvvfvvffjiijjiijjiijij不難驗(yàn)證該流是一個可行流，且其最大流量比原流大 。 可行流 f 是最大流的充分必要條件是不存在從 到 可行流 是最大流的充分必要條件是不存在從到可行流 是最大流的充分必要條件是不存在從f*f*OR3 36 定理 8可行流 是最大流的充要條件是不存在從 vs到 vt的關(guān)于 的增廣鏈證明： f*?????????? ????ffc ijijij ** m i nm i n ),(m i n???先證明：若可行流 是最大流，則 中不存在關(guān)于 的增廣鏈。 OR3 35 ? 最大流量最小截量定理 ? 定理 8：可行流 是最大流的充要條件是不存在從 vs到 vt的關(guān)于 的增廣鏈。 ?????? ?? ? ?fijf ????????cfcfijijijij??00??????),(),(vvvvjiji??OR3 34 ? 增廣鏈的實(shí)際意義： 沿著這條鏈從 vs 到 vt輸送的流，還有潛力可挖，只需按照定理證明中的調(diào)整方法，就可以把流量提高；調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，即仍為可行流。 OR3 33 ? 增廣鏈 ? 在容量網(wǎng)絡(luò) D=(V,A,C)中，若 為網(wǎng)絡(luò)中從vs到 vt的一條鏈，給鏈 定方向?yàn)閺?vs到 vt，上與 同方向的弧稱為前向弧，與 反方向的弧稱為后向弧，前向弧和后向弧的集合分別用 和 來表示。所以，截集是從發(fā)點(diǎn)到收點(diǎn)的必經(jīng)之道。 .,),(1111111111）的截集，記為（的弧的全體稱為分離指向，則把從＝且使得，和分成兩部分的點(diǎn)集截集：如果將VVvvVVVVVvVvVVtstsVCAVD?????V1 V1
法律信息相關(guān)推薦
鄂ICP備17016276號-1