「最小費用フロー問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【さいしょうひようふろーもんだい (minimum cost flow problem)】''' 有向グラフと, 枝の容量と費用, 点の供給(需要)量が与えられたと...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
'''【さいしょうひようふろーもんだい (minimum cost flow problem)】''' | '''【さいしょうひようふろーもんだい (minimum cost flow problem)】''' | ||
| − | + | 最小費用流問題ともいう．有向グラフと, 枝の容量と費用, 点の供給(需要)量が与えられたときに, 各枝の容量を超えず, 各点での正味の流出量が供給量と等しくなる枝上の流れをフローという. 各枝の流量に対する費用の総和を最小にするフローを求める問題の総称. 線形計画問題の特殊ケースである. 強多項式時間で解けることが知られている. | |
| + | |||
| + | [[Category:グラフ･ネットワーク|さいしょうひようふろーもんだい]] | ||
2008年11月9日 (日) 17:53時点における最新版
【さいしょうひようふろーもんだい (minimum cost flow problem)】
最小費用流問題ともいう．有向グラフと, 枝の容量と費用, 点の供給(需要)量が与えられたときに, 各枝の容量を超えず, 各点での正味の流出量が供給量と等しくなる枝上の流れをフローという. 各枝の流量に対する費用の総和を最小にするフローを求める問題の総称. 線形計画問題の特殊ケースである. 強多項式時間で解けることが知られている.