# 多物網絡流問題

## 定義

 容量限制： $\,\sum_{i=1}^{k} f_i(u,v) \leq c(u,v)$ 流守恆： $\,\sum_{w \in V} f_i(u,w) = 0 \quad \mathrm{when} \quad u \neq s_i, t_i$ 需求的滿足： $\,\sum_{w \in V} f_i(s_i,w) = d_i \Leftrightarrow \sum_{w \in V} f_i(w,t_i) = d_i$

$\sum_{(u,v)\in E} \left(a(u,v) \sum_{i=1}^{k} f_i(u,v) \right)$

$\sum_{i=1}^{k} \sum_{w \in V} f_i(s_i,w)$

$\min_{1 \leq i \leq k} \frac{\sum_{w \in V} f_i(s_i,w)}{d_i}$

## 參考

1. ^ Thomas H. CormenCharles E. LeisersonRonald L. RivestClifford Stein. 29. Introduction to Algorithms 2nd edition. MIT Press and McGraw-Hill. 2001: 788–789 [1990]. ISBN 0-262-03293-7.
2. ^ S. Even and A. Itai and A. Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing (SIAM). 1976, 5 (4): 691–703. doi:10.1137/0205048.
3. ^ George Karakostas. Faster approximation schemes for fractional multicommodity flow problems. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. 2002: pp. 166--173. ISBN 0-89871-513-X.