# 多物網絡流問題

## 定義

 容量限制： ${\displaystyle \,\sum _{i=1}^{k}f_{i}(u,v)\leq c(u,v)}$ 流守恆： ${\displaystyle \,\sum _{w\in V}f_{i}(u,w)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}$ 需求的滿足： ${\displaystyle \,\sum _{w\in V}f_{i}(s_{i},w)=d_{i}\Leftrightarrow \sum _{w\in V}f_{i}(w,t_{i})=d_{i}}$

${\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\right)}$

${\displaystyle \sum _{i=1}^{k}\sum _{w\in V}f_{i}(s_{i},w)}$

${\displaystyle \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 978-0-262-03293-3.
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. （原始内容存档于2013-01-12）.
3. ^ George Karakostas. Faster approximation schemes for fractional multicommodity flow problems. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms: 166––173. 2002. ISBN 0-89871-513-X.