多品種フロー
読み方：たひんしゅふろー
【英】：multicommodity flow
【英】：multicommodity flow
1つのネットワーク上の複数の品種の流れ. 枝容量をもつ有向グラフと, 各品種ごとに出発点と到着点となる点が与えられているとき, 各枝ではすべての品種のフロー量の和はその枝の容量を超えず, 各品種ごとに出発点と到着点以外では, 流出量が流入量と等しくなる枝上の品種ごとの流れを多品種フローという. 連続値をとる多品種フローを求める問題は線形計画問題に定式化できるが, 整数値をとる多品種フローを求める問題はNP完全である.
「OR事典」の他の用語
| グラフ･ネットワーク： | 基多面体 基族 基本分割 多品種フロー 多項式時間アルゴリズム 安定結婚問題 完全グラフ |
- 多品種フローのページへのリンク
