世界大百科事典（旧版）内の最大フロー最小カット定理の言及
【ネットワーク理論】より
…代表的なネットワークフロー問題は，有向あるいは無向のネットワークにおいて，それぞれの辺を流れるフローの最大値(辺の容量という)が与えられている時，ネットワークの一つの頂点sから別の頂点tへの流れの量(フロー値という)を最大にするという問題である。この問題はネットワーク理論の発展の基礎となった問題であって，1956年にフォードL.R.FordとフルカーソンD.R.Fulkersonの2人がsからtへの最大フロー値を与える最大フロー最小カット定理とそれを解く簡単なアルゴリズムとしてのラベリング法を提起することによって，それに対する解答を与えた。 ネットワークにおける頂点の集合を二つの集合S,Tに分割して頂点s,tがそれぞれS,Tに含まれるようにしたとき，SからTに向かう辺の集合をカットと呼び，そのカットに含まれる辺の容量の和をカット容量という。…
※「最大フロー最小カット定理」について言及している用語解説の一部を掲載しています。
出典｜株式会社平凡社「世界大百科事典（旧版）」
Sponsored by 