77书库

手机浏览器扫描二维码访问

第46部分（第1页）

对于包含n个顶点V1，V2。。。；Vn的网络流，V　1为发点，Vn为收点，各段弧（V　i；Vj）上容量为

Cij，设｛Xij｝是一个可行流，如果存在一条从V1到Vn的路线，这条路线具有以下特点：

（1）所有正向弧（弧的方向与流向一致）上　Xij0。

则称此条路线为可行流｛Xij｝的一个增广链，记

ε1=min｛cij…xij｜　当（v　i；vj）为正向弧｝

（12。8）

ε2=min｛xij｜　当　（v　i；vj）为反向弧｝　（12。10）

ε=min｛ε1；　ε2｝　（12。11）

由增广链的特点可知ε》0；按如下公式调整可行流｛x　ij｝为｛x　’ij｝：

当（vi；vj）是增广链的正向弧

当（vi；vj）是增广链的反向弧　（12。12）

当（vi；vj）不在增广链上

V3

V5

12…13

。x

＋ε

ij

xij

=

。。

xij

唤起心中的巨人  泣画  狼性法则  痞子将军:战争之王  著名女性演说精粹  企业员工哲学:终极期望  美国厚黑学-人生必胜之道  不忍放开你的手  黑天鹅(军旅)  苍狼与白鹿  杀手的任务穿越  瓦岗英雄  红色风暴  宇宙第一军  长沙王传  心理操纵术  真本事来自好观念  蛟郎  二战大兵  你为什么是穷人