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