「最小費用フロー問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【さいしょうひようふろーもんだい (minimum cost flow problem)】''' 有向グラフと, 枝の容量と費用, 点の供給(需要)量が与えられたと...') |
細 ("最小費用フロー問題" を保護しました。 [edit=sysop:move=sysop]) |
(相違点なし)
| |
2007年7月20日 (金) 10:21時点における版
【さいしょうひようふろーもんだい (minimum cost flow problem)】
有向グラフと, 枝の容量と費用, 点の供給(需要)量が与えられたときに, 各枝の容量を超えず, 各点での正味の流出量が供給量と等しくなる枝上の流れをフローという. 各枝の流量に対する費用の総和を最小にするフローを求める問題の総称. 線形計画問題の特殊ケースである. 強多項式時間で解けることが知られている.