「多品種フロー」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【たひんしゅふろー (multicommodity flow)】''' 1つのネットワーク上の複数の品種の流れ. 枝容量をもつ有向グラフと, 各品種ごとに出...') |
細 ("多品種フロー" を保護しました。 [edit=sysop:move=sysop]) |
(相違点なし)
| |
2007年7月20日 (金) 11:19時点における版
【たひんしゅふろー (multicommodity flow)】
1つのネットワーク上の複数の品種の流れ. 枝容量をもつ有向グラフと, 各品種ごとに出発点と到着点となる点が与えられているとき, 各枝ではすべての品種のフロー量の和はその枝の容量を超えず, 各品種ごとに出発点と到着点以外では, 流出量が流入量と等しくなる枝上の品種ごとの流れを多品種フローという. 連続値をとる多品種フローを求める問題は線形計画問題に定式化できるが, 整数値をとる多品種フローを求める問題はNP完全である.