最大フロー最小カットとは？
最大フロー最小カットとは、始点から終点へ流せる最大の流量は、その経路を分断するカット（辺の集合）の容量の最小値に等しいという定理。ネットワークで同時に使用できる回線数や最大伝送容量を求める問題に使う。
ネットワークスペシャリスト試験の過去問では1回出題されています。
さいだいふろーさいしょうかっと
最大フロー最小カットの意味
始点から終点へ流せる最大の流量は、その経路を分断するカット（辺の集合）の容量の最小値に等しいという定理。ネットワークで同時に使用できる回線数や最大伝送容量を求める問題に使う。
最大フロー最小カットの具体例
途中に容量2の区間があれば、他がいくら太くても全体では2しか流せない。
最大フロー最小カットは試験でどう引っ掛けられる？
個々の経路の容量を単純に足すのではなく、ボトルネックとなるカットを見つけて容量を合計するのが正しい解き方。
最大フロー最小カットと関連する用語
最大フロー最小カットが出た過去問
図のネットワークで、数字は二つの地点間で同時に使用できる論理回線の多重度を示している。X地点からY地点までには同時に最大幾つの論理回線を使用することができるか。
正解：10
要点：同時使用可能な回線数は最小カットの容量で決まる
この種の問題は最大フロー問題であり、最大フロー最小カット定理を使って解く。X側とY側にノードを分ける切り口（カット）をいろいろ試し、その切り口をまたぐ辺の容量の合計が最小になる値が、同時に使用できる論理回線の最大数と一致する。X直結の3本の合計は11だが、途中の中継区間の容量がボトルネックとなり、最小カットは10になる。
出典：令和3年度 春期 ネットワークスペシャリスト試験 午前Ⅱ 問4（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。