「最大フロー最小カット定理」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【さいだいふろーさいしょうかっとていり (maximum flow minimum cut theorem)】''' 枝容量をもつ有向グラフと入口, 出口となる2点が与え...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口と出口以外では流出量と流入量が等しい枝上の流れに対し, 入口からの流入量をフロー値という. また, 入口を含み, 出口を含まないような点の部分集合から出る枝の容量の総和をカット値という. 最大フロー値が最小カット値に一致するというフォード(L. R. Ford, Jr.)とファルカーソン(D. R. Fulkerson)による定理. | 枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口と出口以外では流出量と流入量が等しい枝上の流れに対し, 入口からの流入量をフロー値という. また, 入口を含み, 出口を含まないような点の部分集合から出る枝の容量の総和をカット値という. 最大フロー値が最小カット値に一致するというフォード(L. R. Ford, Jr.)とファルカーソン(D. R. Fulkerson)による定理. | ||
| + | |||
| + | [[Category:グラフ･ネットワーク|さいだいふろーさいしょうかっとていり]] | ||
2008年11月9日 (日) 17:57時点における最新版
【さいだいふろーさいしょうかっとていり (maximum flow minimum cut theorem)】
枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口と出口以外では流出量と流入量が等しい枝上の流れに対し, 入口からの流入量をフロー値という. また, 入口を含み, 出口を含まないような点の部分集合から出る枝の容量の総和をカット値という. 最大フロー値が最小カット値に一致するというフォード(L. R. Ford, Jr.)とファルカーソン(D. R. Fulkerson)による定理.