最大フロー最小カット定理

3行要約

1. ネットワークにおける最大流量が、ソースとシンクを分断する最小のカット容量に等しいという定理である。
2. グラフ理論における最適化問題の基本であり、効率的な輸送や通信経路の設計に用いられる。
3. フォード・ファルカーソン法などのアルゴリズムによって、具体的な最大流を求めることができる。