多品種フロー
ナビゲーションに移動
検索に移動
【たひんしゅふろー (multicommodity flow)】
1つのネットワーク上の複数の品種の流れ. 枝容量をもつ有向グラフと, 各品種ごとに出発点と到着点となる点が与えられているとき, 各枝ではすべての品種のフロー量の和はその枝の容量を超えず, 各品種ごとに出発点と到着点以外では, 流出量が流入量と等しくなる枝上の品種ごとの流れを多品種フローという. 連続値をとる多品種フローを求める問題は線形計画問題に定式化できるが, 整数値をとる多品種フローを求める問題はNP完全である.