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