最大フロー最小カットとは？さいだいふろーさいしょうかっと
最大フロー最小カットとは、グラフで表したネットワークにおいて、始点から終点へ同時に流せる最大の流量は、始点側と終点側を分ける切り方（カット）のうち容量の合計が最小になるものと等しい、という定理。回線の同時利用本数や最大伝送容量を求める設問の根拠になる。
最終更新：2026-10-06
この語が出る過去問を解く →背景
経路を1本ずつ数え上げる解き方は、経路が共有するリンクを二重に数えたり、遠回りの経路を見落としたりして間違えやすい。切り方の側から見れば、どこか1か所で全体が制限されるという事実を機械的に取り出せる。ネットワーク設計では、この最小カットがそのまま単一障害点や増速すべき区間を指し示すため、定理としてだけでなく判断の道具として使える。
具体例
増加パスを見つけては流量を積み増すフォード・ファルカーソン法で求められる。試験では小さな有向グラフが与えられ、上下に分かれた冗長経路のどこか1か所だけ容量の小さいリンクがある、といった形で最小カットを目で探させる出題が多い。
試験での引っ掛け
各経路の容量を単純に足すのではなく、始点側から終点側へ向かう辺の容量だけを合計した最小のカットを探す。逆向きの辺を数えに入れる、共有リンクを経路ごとに二重計上する、という2つが典型的な誤りである。
関連用語
出た過去問
出典：令和3年度 春期 ネットワークスペシャリスト試験 午前Ⅱ 問4（IPA）解説で登場
図のネットワークで、数字は二つの地点間で同時に使用できる論理回線の多重度を示している。X地点からY地点までには同時に最大幾つの論理回線を使用することができるか。
正解：10
要点：同時使用可能な回線数は最小カットの容量で決まる
この種の問題は最大フロー問題であり、最大フロー最小カット定理を使って解く。X側とY側にノードを分ける切り口（カット）をいろいろ試し、その切り口をまたぐ辺の容量の合計が最小になる値が、同時に使用できる論理回線の最大数と一致する。X直結の3本の合計は11だが、途中の中継区間の容量がボトルネックとなり、最小カットは10になる。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。