作業フローを簡素化：miniwebtoolを検索。
追加
関連ツール
隣接行列電卓複素数電卓ダイクストラ最短経路電卓ハミルトン路チェッカー巡回セールスマン問題ソルバー TSP
ホームページ > 数学 > 高度な数学操作 > ネットワークフロー電卓最大フロー
 

ネットワークフロー電卓最大フロー

Ford-Fulkerson法（Edmonds-Karp）を使用して、容量付き有向ネットワーク内のソースからシンクへの最大フローを計算します。すべての増加道をアニメーションで表示し、残余容量、飽和エッジ、および最適性を証明する最小カット・パーティションを表示します。

ネットワークフロー電卓最大フロー
クイック例:
教科書の例 (6ノード) 小規模ネットワーク 定番の CLRS 二部グラフ風 行列入力
エッジ形式: A -> B : 10 (矢印と容量)、または A, B, 10。
行列形式: 1行に1行ずつ。C[i][j] はエッジ i → j の容量です（エッジがない場合は 0 を使用）。対角成分は 0 である必要があります。
カンマまたはスペース区切りのラベル。行列の各行に対応します。省略時は S, A, B, …, T になります。

Embed ネットワークフロー電卓最大フロー Widget

ネットワークフロー電卓最大フロー

ネットワークフロー電卓最大フローは、任意の容量付き有向ネットワークにおいて、選択した始点（ソース）s から終点（シンク）t への最大フローを計算します。内部では幅優先探索による増加道を用いた Ford-Fulkerson 法（Edmonds-Karp アルゴリズム）を実行し、見つかったすべてのパスを記録します。これにより、意思決定プロセスを1回ずつの反復でリプレイして確認できます。また、結果ページには最小カット（フロー値が真に最適であることを証明するボトルネックの分割）も表示されます。

最大フロー問題とは？

フローネットワークとは、有向グラフ G = (V, E) と容量関数 c: E → ℝ≥0 の組み合わせです。2つの頂点が区別されます：フローが湧き出すソース s と、フローが吸収されるシンク t です。フロー f は、以下の規則に従うエッジへの値 f(u, v) ≥ 0 の割り当てです：

容量制約: 0 ≤ f(u, v) ≤ c(u, v) （すべてのエッジ (u, v) に対して） 流量保存: Σ f(w, v) = Σ f(v, w) （s, t 以外のすべての v ∈ V に対して） フロー値: |f| = Σ f(s, w) − Σ f(w, s) （s から流出する正味のフロー）

最大フロー問題は、このフロー値 |f| を最大化するフロー f を求めるものです。直感的に言えば、エッジが所定の容量を持つ水道管であるとき、s から t へ毎秒何リットルの水を送れるかという問題です。

アルゴリズムの仕組み — BFS を用いた Ford-Fulkerson

このアルゴリズムは、現在のフローと並行して残余グラフを保持します。容量 c、現在のフロー f の各エッジ (u, v) に対して、残余グラフには以下が含まれます：

各反復において、残余グラフ上で s から t への幅優先探索（BFS）を実行します。パスが見つかった場合、そのパス上の最小のエッジ容量（ボトルネック）を、パスに沿った各順方向エッジのフローに加え、逆方向エッジのフローから差し引きます。これを増加道と呼びます。BFS で t に到達できなくなったとき、現在のフローが最適となります。

残余グラフ内に s から t への増加道 P が存在する間： b ← P 内のエッジ (u, v) における最小の c_residual(u, v) P に沿って b 単位のフローを流す // 残余グラフとフローを更新 合計フロー |f| を返す

（任意のパス選択ではなく）BFS を使用することで、Ford-Fulkerson 法は Edmonds-Karp アルゴリズムとなり、実行時間は O(V · E²) に抑えられることが保証されます。また、通常の Ford-Fulkerson では対応できない無理数の容量に対しても、必ず終了することが保証されます。

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

カットとは、頂点集合を s ∈ S かつ t ∈ T となる2つの集合 (S, T) に分割することです。その容量は、S から T へ向かうエッジの容量の合計です：

cap(S, T) = Σ c(u, v) （u ∈ S, v ∈ T に対して）

最大フロー最小カット定理 (Ford & Fulkerson, 1956) によれば：

最大フロー値 = 最小カット容量

このツールは最小カットを自動的に検出します。Edmonds-Karp が終了した後、残余グラフ上で s からもう一度 BFS を実行します。到達できた頂点が S を構成し、残りが T となります。元のグラフで S → T を横断するすべてのエッジは飽和しており、それらの容量の合計は最大フロー値と正確に一致します。これは結果の「最小カット容量 ✓ 最適性が確認されました」として表示されます。

学習のための機能

入力形式

1. 容量付きエッジリスト

1行に1つのエッジを入力します。矢印形式が最も読みやすいですが、いくつかの代替形式も可能です：

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

他にも A, B, 10 ・ A B 10 ・ A -> B , 10 などが受け付けられます。同じペアの間に複数のエッジがある場合は合算されます。

2. 容量行列

1行に1行ずつ、スペースまたはカンマで区切った値を入力します。項目 C[i][j] は頂点 i から 頂点 j へのエッジの容量です。エッジがない場合は 0 を使用してください。行列は正方行列である必要があり、対角成分は 0（自己ループなし）である必要があります。

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 0 ]

行列ラベルフィールドに、対応する頂点ラベルを（カンマまたはスペース区切りで）入力してください。省略した場合、ラベルはデフォルトで S, A, B, …, T になります。

最大フローの応用例

分野最大フローの活用方法
輸送と物流鉄道、道路、パイプラインのネットワークで、出発地から目的地まで1日にどれだけの貨物を運べるか？
二部マッチング労働者への仕事の割り当て、学生へのプロジェクトの割り当てなど。容量1の最大フローにより最大マッチングが得られます。
画像セグメンテーションコンピュータビジョンの Boykov–Kolmogorov 最小カットにより、前景ピクセルと背景ピクセルを分離します。
ネットワークの信頼性最小カットにより、切断されるとネットワークが分断されてしまう「最も弱いリンク」を特定します。
プロジェクトのスケジューリング閉包問題や選択問題は最小カットに還元できます。
野球の脱落決定チームが数学的にリーグ優勝の可能性がなくなったかどうかを判定します。

実行例

「教科書」のクイック例は、ソース S とシンク T を持つ6ノードのネットワークです。Edmonds-Karp を実行すると、4つの増加道が見つかります：

  1. S → A → B → T：ボトルネック 4（エッジ A-B が制限）。累積フロー: 4。
  2. S → A → D → T：ボトルネック 6。累積フロー: 10。
  3. S → C → D → T：ボトルネック 4（エッジ D-T が制限、残り 4）。累積フロー: 14。
  4. S → C → D → B → T：ボトルネック 5。累積フロー: 19。

これ以上増加道が存在しないため、アルゴリズムは停止します。最小カットは (S = {S, C}, T = {A, B, D, T}) であり、境界エッジは S → A (容量 10) と C → D (容量 9) です。これらを合計すると 19 となり、最大フロー値と一致します。

この電卓の使い方

  1. タブを使用して入力形式を選択します（エッジリスト推奨、または容量行列）。
  2. ネットワークを入力します。 クイック例から開始して変更することもできます。行列入力の場合、S, A, B, …, T 以外の名前を使いたい場合はラベルも入力してください。
  3. ソースとシンクを指定します（空欄にすると S と T を自動検出します）。
  4. 最大フローを計算をクリック。 結果ページに最大フロー値、最小カット分割、レイヤードグラフ可視化、すべての増加道、エッジ利用率テーブル、および3つの行列（容量、フロー、残余）が表示されます。
  5. グラフの下にあるアニメーションを再生して、アルゴリズムの決定プロセスを確認します。任意の増加道のステップをクリックすると、その時点へ直接ジャンプできます。

制限事項

よくある質問

最大フロー問題とは何ですか？

各エッジに非負の容量がある有向ネットワークにおいて、指定された始点（ソース）s から終点（シンク）t へ、各エッジのフローがその容量を超えず、かつソースとシンク以外の各頂点に流入するフローと流出するフローが等しいという規則に従って、どれだけのフローを送り出せるかを問う問題です。その答えを最大フロー値と呼びます。

Ford-Fulkerson 法とは何ですか？

Ford-Fulkerson は最大フローを計算するための一般的な手法です。残余グラフ内でソースからシンクへの増加道を繰り返し見つけ、そのパスに沿って可能な限りのフロー（ボトルネック容量）を押し出し、残余グラフを更新します。増加道が存在しなくなった時点で処理は終了します。パスの選択に幅優先探索（BFS）を使用する場合、それは Edmonds-Karp アルゴリズムと呼ばれ、O(V · E²) の時間で動作します。

フローネットワークの最小カットとは何ですか？

カットとは、頂点をソースを含む集合 S とシンクを含む集合 T の2つに分割することです。カットの容量は、S から T へのエッジの容量の合計です。最小カットとは、最小の容量を持つカットのことです。有名な最大フロー最小カット定理は、最大フロー値が常に最小カット容量と等しいことを証明しており、一方を見つければもう一方も自動的に得られます。

残余グラフとは何ですか？

残余グラフは、各エッジにあとどれだけフローを流せるかを追跡するものです。容量 c、現在のフロー f の元のエッジ (u, v) に対して、残余グラフには容量 c - f の順方向エッジ (u, v)（残りの容量）と、容量 f の逆方向エッジ (v, u)（キャンセル可能なフロー）が含まれます。増加道は残余グラフのエッジを使用するため、アルゴリズムは以前の決定を取り消すことができます。

なぜこのツールは増加道に BFS を使用するのですか？

幅優先探索（Edmonds-Karp）で増加道を選択することで、エッジの容量に関係なく多項式時間での終了が保証されます。任意のパス選択戦略を用いる通常の Ford-Fulkerson では、特殊な入力に対して指数関数的な反復回数ループしたり、無理数の容量に対して終了しなかったりすることがあります。また、BFS は最短の増加道を生成するため、読みやすく理解しやすくなります。

飽和したエッジとはどういう意味ですか？

エッジのフローがその容量と等しくなり、それ以上フローを流せなくなった状態を「飽和」と呼びます。飽和したエッジはネットワークのボトルネックであり、すべての最小カットは、カットの S 側から T 側に向かう飽和エッジのみで構成されます。ツールでは飽和エッジを赤色でハイライトし、ボトルネックの構造を一目で確認できるようにしています。

参考文献

このコンテンツ、ページ、またはツールを引用する場合は、次のようにしてください：

"ネットワークフロー電卓最大フロー"（https://MiniWebtool.com/ja/ネットワークフロー電卓最大フロー/） MiniWebtool からの引用、https://MiniWebtool.com/

by miniwebtool チーム. 更新日: 2026年4月22日

また、AI 数学ソルバー GPT を使って、自然言語による質問と回答で数学の問題を解決することもできます。

高度な数学操作:

おすすめ:

マスターナンバー電卓InstagramユーザーID検索パーセンテージ減少電卓パーセント増加電卓サッカーxg期待ゴール電卓弧長電卓パーセント誤差電卓標準偏差電卓 - 高精度ランダムカラージェネレーター合計電卓画像分割ツールシグマ記法電卓 総和動画を結合HEX電卓円錐展開図テンプレートジェネレーターMACアドレス検索番号を並べ替える中央値電卓筆算割り算電卓フィートとインチからセンチメートルへのコンバーター英単語ランダム生成ツールエンジェルナンバー電卓ランダム超能力ジェネレーター平方完成電卓ランダム絵文字ジェネレーター不可視文字除去ツール太陽位置計算機動画を逆再生war電卓逆テキスト売上総利益率電卓ランダム誕生日ジェネレーターボウリングスコア計算機ai句読点追加手数料電卓楕円円周電卓ASCIIコード表ランダムトーナメント表作成ツール加速度電卓MP3ルーパー相対標準偏差電卓FPSコンバーターCAGR電卓対数電卓モジュロ電卓ランダム名前ジェネレータービンゴカードジェネレーター動画を回転センチメートルからフィートとインチへのコンバーター変化率電卓ボルト締付トルク計算機t検定電卓相関係数計算機関数電卓階段電卓比率電卓血糖値コンバーターランダム日付ジェネレーターYouTubeチャンネル統計私のIPアドレスは何ですかHEXコンバーター圧力電卓ビデオ速度を調整fena電卓マン・ホイットニーのU検定計算機平均寿命電卓デシベル (dB) 電卓桁数電卓小数時間から普通の時間へのコンバーター🖱️ クリックカウンター外れ値電卓クロスワードパズルメーカー土星回帰電卓指数電卓-高精度平方根電卓迷路ジェネレーターオーディオ スプリッターピタゴラスの定理電卓分数電卓XMLバリデーター上下反転テキストジェネレーターBUN対クレアチニン比電卓ホームランの打席電卓熱膨張計算機SRTからTXTへの変換ツール積分電卓斜辺電卓変動係数電卓パスワード強度テスター労働時間計算ツール正多角形電卓筆算足し算・引き算計算機log-base-2電卓バイナリ電卓行番号を追加CRC32チェックサム電卓タンジェント電卓平均電卓-高精度角度変換ツールANC電卓画像回転ツール空の行を削除するトルク電卓🔊 トーンジェネレーター周波数波長変換ツールじゃんけんジェネレーター10進数からBCDへのコンバーター中国剰余定理電卓年の日電卓 - 今日は今年の何日目分散電卓 高精度VTTからtxtへのコンバーター太陽・月・上昇星座電卓 🌞🌙✨ランダム時刻ジェネレーター動画から画像抽出ツールcsvからsrtへTikTok収益計算ツールHTMLからテキストコンバータSHA256 ハッシュジェネレーター👙 ブラサイズ電卓三角関数グラフ作成ツール二乗平均平方根電卓慣性モーメント計算機水泳ペース計算機熱伝達計算機パーセント成長率電卓文字数による改行角速度計算機パーソナリティ・ナンバー電卓学習曲線電卓自然対数電卓並列抵抗電卓割り切れるテスト電卓複数分数電卓CMYKからHEXへの変換ツールコラッツ予想電卓標準誤差電卓💧 露点電卓インタラクティブ単位円ビジュアライザーベーカーズパーセント電卓車両重量配分計算機BCDからバイナリへのコンバーター配管流量電卓IPアドレスから16進数への変換パレットジェネレーターランダムクレジットカードジェネレーターワイヤーゲージ電卓絶対値不等式ソルバーピザ生地計算機eの最初のn桁Zalgoテキストジェネレーター中間日計算機平均中央値モード電卓服のサイズ変換音節カウンターpH電卓ランダムグループジェネレーター水星逆行カレンダー点つなぎジェネレーターGIFメーカーアナグラム生成器オンライン句読点削除ツールコラージュメーカービデオをループ再生カイ二乗検定電卓ランダム算数問題ジェネレーター分圧器計算電卓沸点計算ツール逆行列電卓FacebookユーザーID検索hba1c電卓エラー関数電卓梁の電卓配当利回り電卓3d距離電卓双曲線関数電卓平均電卓部分分数分解電卓10進数から16進数へのコンバーターランダムアニマルジェネレーター円錐台電卓論理ゲートシミュレーター退職カウントダウンYouTubeショート収益化計算ツールケリー基準電卓ヴァンパイア黙示録電卓⏱️ 時間計算機水分補給計算機絶対値電卓10進数からバイナリへのコンバーターAIテキストヒューマナイザーLED抵抗器電卓グレイコード・バイナリ変換電卓ノノグラムジェネレーター (ピクロス)馬力電卓テンソル積電卓ビデオ反転ピッグラテン翻訳機ランダム整数ジェネレーター二項係数電卓動画圧縮CGPAからパーセンテージへの変換器簡単採点ツール EZ Grader子育て費用計算機赤ちゃんのミルク量計算おむつサイズ電卓赤ちゃんの名前ジェネレーター赤ちゃんの目の色予測子供のBMIパーセンタイル計算機子供の身長予測ツールhcg倍加時間計算ツール体外受精出産予定日電卓着床計算ツール中国式性別予測カレンダーISO 8601 日付フォーマッターユリウス日変換器昼寝電卓月相電卓日の出＆日の入り電卓世界時計日付ローマ数字変換電卓ソブリエティ計算機ハーフバースデー計算機記念日計算機週番号計算機チップ分配計算機メールマーケティングROI電卓リード獲得単価計算機運転資本計算機限界利益計算機FIFO / LIFO 電卓安全在庫計算機発注点計算機経済的発注量EOQ電卓減価償却計算機ハンドメイド価格電卓卸売価格計算機Shopify利益計算機Amazon FBA 電卓eBay手数料計算機Etsy手数料計算機Stripe手数料計算機PayPal手数料計算機ベッティングオッズ変換器什一献金計算機ザカート計算機英国印紙税計算機HRA非課税計算ツールグラチュイティ計算機NPS計算機EPF電卓PPF計算機RD電卓SWP電卓グロスアップ計算機ローン比較電卓クレジット利用率計算ツールCDラダー電卓T-Bill米国短期国債電卓I Bond 電卓529大学積立計算機HSA電卓退職金計算機昇給計算機請求書作成ツール出張日当計算機走行距離手当計算機家賃値上げ計算機日割り家賃計算家賃適正額計算機乗り出し価格計算ツール車購入可能額計算機バイクローン計算機キャンピングカーローン計算ボートローン電卓土地ローン計算機建設ローン計算機金利のみ住宅ローン計算機バルーンローン計算機住宅ローンポイント計算機PMI電卓隔週住宅ローン返済額計算機ARM住宅ローン電卓VAローン計算機給与手取り計算機AI SQLクエリジェネレーターAI正規表現ジェネレーターAIデータ可視化ツールCSV貼り付けAIテキストトーン分析ツールAI履歴書アナライザーAI単位変換ツール自然言語AI謝罪文ジェネレーターAI 丁寧なお断り文ジェネレーターAI旅行日程ジェネレーターAI読書リストジェネレーターAIワークアウトプランジェネレーターAI献立ジェネレーターAIギフトアイデアジェネレーターAIレシピジェネレーター食材から奨学金ROI電卓大学費用計算機言語学習 流暢になるまでの学習時間電卓単語クイズ作成ツールコーネルノート作成ツールフラッシュカード間隔反復スケジューラーペイント色混合計算機タイル目地計算機食洗機の積み込み最適化ツール洗剤の使用量計算ヘアカラー混合計算機印刷コスト計算機ガス vs 電気 コスト比較電卓ギフトカードチップ電卓引っ越し用ダンボール数計算機ストレージユニットサイズ計算機カプセルワードローブ計算機ベルト長さ計算機油圧シリンダー推力計算機滑車システム計算機ギア比計算機機械比熱計算機ベルヌーイの式計算機レイノルズ数計算機潮汐時刻計算機星空観測条件計算機結び方リファレンスツール寝袋温度評価ガイドテントフットプリントサイズ電卓バックパッキング食料重量電卓ネイスミス式ハイキングペース電卓刺繍糸長さ電卓レジンキャスト量計算電卓ビーズパターン電卓陶芸粘土収縮率電卓折り紙用紙サイズ電卓キルトバインディング電卓クロスステッチ刺繍糸計算編み物パターン計算機編み針サイズ変換器かぎ針サイズ変換器馬の干し草計算ツールペット航空輸送クレートサイズ検索爬虫類飼育UVBライト距離計算機鳥かごサイズ計算機水槽ヒーターワット数電卓猫のトイレ数計算機ヘッドライト照射距離電卓エンジン圧縮比計算機タイヤ溝摩耗計算機トレーラー牽引荷重計算機旅行費用割り勘計算停止距離計算機労災補償計算機遺産配分電卓商標区分検索ツール特許出願料電卓売上税ネクサスチェッカー刑期短縮計算機時効計算機Airbnb料金最適化ツールルームメイト家賃分割計算機セクション8 家賃電卓BRRRR法計算機キャッシュオンキャッシュリターン計算機賃貸利回り計算機1031エクスチェンジ計算機資産成長ビジュアライザーランチ代計算機ジム vs 自宅トレーニング費用電卓コーヒー代計算機リモートワーク節約計算機副業ROI電卓サブスクリプション費用トラッカーSaaS料金計算ツールフリーランスプロジェクト料金計算機スモークウッド・ペアリングガイド発酵時間計算機マリネ時間計算機食事制限レシピフィルタースパイス代用品ファインダーカフェイン半減期トラッカー標準ドリンク計算ツールワインペアリング提案ツールクライミンググレード変換器自転車ギア比計算機釣り結び強度計算機ヨガポーズホールドタイマー水泳SWOLF電卓レースタイム予測計算機ボクシングパンチ力計算機ラグビー得点電卓クリケット・ランレート電卓テニススコアトラッカーWellsスコア電卓 (DVT/PE)グラスゴー・コーマ・スケール計算機アプガースコア計算機FFMI 電卓クーパー12分間走計算ツール1マイルウォークテストロックポート電卓除脂肪体重から筋力計算炭水化物インスリン比計算機インスリン感受性係数計算機ヘブライ暦変換器ヒジュラ暦変換器旧暦変換ツール文化別年齢電卓どれくらい前計算機あと何日カウントダウン電卓日付パターンジェネレーター日付に営業日を追加営業日計算機単語頻度アナライザー文の長さばらつき分析ツールヘミングウェイ風リーダビリティエディタ発音IPA変換ツールヴィジュネル暗号ツールアトバッシュ暗号ツールROT13エンコーダー・デコーダーEXIFデータビューア・削除ツールバックロニム ジェネレーター頭字語ジェネレーターパングラムチェッカーリポグラム チェッカー画像からSVGトレーサー画像からASCIIアートへの変換器JSONスキーマジェネレーターTypeScriptプレイグラウンドLessからCSSへのコンパイラーSCSSからCSSへのコンパイラーSVGからReact/JSXへの変換器クエリ文字列ビルダーURLパーサーUUID検証・デコーダーHTTPステータスコードリファレンスcURLコマンドビルダーシェルピンスキーの三角形ジェネレーター3D曲面プロッター極方程式プロッタージュリア集合生成器マンデルブロ集合エクスプローラーL-Systemフラクタルジェネレータードロネー三角形分割ジェネレーターボロノイ図ジェネレータースピログラフジェネレーターテッセレーションジェネレーターシックスシグマ工程能力計算機youtubeサムネイルダウンローダーyoutube収益見積もりツールランダムRPGキャラクタージェネレーター