「最大フローアルゴリズム」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【さいだいふろーあるごりずむ (maximum flow algorithm)】''' 枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口, 出口以外の点での流出量と流入量が等しくなる枝上の流れをフローという. 入口からの流入量が最大となるフローを求めるアルゴリズム. 増加道法, プッシュ再ラベル法などがあり, 強多項式時間計算量のアルゴリズムが知られている. | 枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口, 出口以外の点での流出量と流入量が等しくなる枝上の流れをフローという. 入口からの流入量が最大となるフローを求めるアルゴリズム. 増加道法, プッシュ再ラベル法などがあり, 強多項式時間計算量のアルゴリズムが知られている. | ||
| + | |||
| + | [[Category:グラフ･ネットワーク|さいだいふろーあるごりずむ]] | ||
2008年11月9日 (日) 17:57時点における最新版
【さいだいふろーあるごりずむ (maximum flow algorithm)】
枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口, 出口以外の点での流出量と流入量が等しくなる枝上の流れをフローという. 入口からの流入量が最大となるフローを求めるアルゴリズム. 増加道法, プッシュ再ラベル法などがあり, 強多項式時間計算量のアルゴリズムが知られている.