「最大フロー最小カット定理」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【さいだいふろーさいしょうかっとていり (maximum flow minimum cut theorem)】''' 枝容量をもつ有向グラフと入口, 出口となる2点が与え...')
 
("最大フロー最小カット定理" を保護しました。 [edit=sysop:move=sysop])
(相違点なし)

2007年7月20日 (金) 10:26時点における版

【さいだいふろーさいしょうかっとていり (maximum flow minimum cut theorem)】

枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口と出口以外では流出量と流入量が等しい枝上の流れに対し, 入口からの流入量をフロー値という. また, 入口を含み, 出口を含まないような点の部分集合から出る枝の容量の総和をカット値という. 最大フロー値が最小カット値に一致するというフォード(L. R. Ford, Jr.)とファルカーソン(D. R. Fulkerson)による定理.