关系: 0?流量?容量图中数据为容量
2 2 2 1 1 流 2 2 容量(c) 流量(f) 最大流量 2 1 2 2 怎么求最大流
求最大流:
v1 (4) (5)
v4 v5 (3) v2 vs (3) vt
v3
(2)
v6
可行流
?
网络N=(V,X,Y,A,C)的一个可行流失指定义在A上的一个整值函数f,使得:
??(1)对?a?A,0?f(a)?c(a),(容量约束);(2)对?V?(X?Y),f(v)?f(v),(流量守恒)其中f(v)表示点v处于入弧上的流量之和,f(v)表示点v处于出弧上的流量和.(5,3) (4,2) (3,2) (3,1) (3,2) y
??可行流存在性
x
(4,2) (3,3) 注:
(1)可行流总是存在的,比如?a?A,f(a)?0,便是任一网络中的一个可行流,这个流称为零值流;(2)对网络中任一可行流f和任一顶点子集S,f(S)表示从中流出的流量,即从S中顶点指向S外的弧上的流量和,f(S)表示流入的流量,即从S外的顶点指向S的弧上的流量之和??流量与最大流
设f是网络N?(V,X,Y,A,C)中的一个可行流,则必有f(X)?f(Y)?Valf称为流f的流量.??N中流量最大的可行流称为的最大流(5,3) (4,2) (3,2) x
(4,2) (3,1) (3,2) (3,3) y
图论—最大流及最小费用流
关系:0?流量?容量图中数据为容量22211流22容量(c)流量(f)最大流量2122怎么求最大流求最大流:v1(4)(5)v4v5(3)v2vs(3)vtv3(2)v6可行流?
推荐度:
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
点击下载文档文档为doc格式