「最小費用フロー問題」の版間の差分

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

2007年10月14日 (日) 00:51時点における版

【さいしょうひようふろーもんだい (minimum cost flow problem)】

最小費用流問題ともいう.有向グラフと, 枝の容量と費用, 点の供給(需要)量が与えられたときに, 各枝の容量を超えず, 各点での正味の流出量が供給量と等しくなる枝上の流れをフローという. 各枝の流量に対する費用の総和を最小にするフローを求める問題の総称. 線形計画問題の特殊ケースである. 強多項式時間で解けることが知られている.