最大流問題単語

サイダイリュウモンダイ
  • 14
  • 0pt
掲示板へ

最大流問題とは、最大の流量をめる問題である。線計画問題のひとつ。

概要

例えば、ある地点から他の地点に物資を送るとする。このとき、いくつかの地点を経由し、分岐や合流をしながら物資が送られるとする。送られる過程で、それぞれの地点からそれぞれの地点に一度に送ることのできる量の最大値が決まっている際、全体で一度に送れる量の最大値はいくらなのか。これを考えるのが最大流問題である。最大流問題では、送られる量をフロー、出発点をソース、終着点をシンクという。

フロー増加法

最大流問題を解くアルゴリズムのひとつ。

  1. フローをすべて0にする。
  2. 残余ネットワーク(後述)をめる。
  3. 残余ネットワークソースからシンクへつながる路がなければ、6へ飛ぶ。あれば、その中から1つ選ぶ。
  4. その路の残余容量の中で最小のものを、その路の各フローに加える。既に流れている方向と逆方向にフローを加えるのは、フローを減少することを意味する。
  5. 2へ戻る。
  6. この時点での流れ方が、最大流である。

残余ネットワークとは

「あとどれだけフローを増加できるか」を図にしたもの。

例えば、地点Aから地点Bへ最大で5流せるとし、実際に2流れているとする。このとき、さらにフローを3だけ増やすこともできるし、流れている2をキャンセルすることもできる。この量を「残余容量」という。AからBへの残余容量は3、BからAへの残余容量は2である。残余容量をすべてめ、図にしたものが残余ネットワークである。

最大流問題の例です。

上図を例にして、最大流をフロー増加法でめる。

フローをすべて0にしたときの残余ネットワークは、上図に一致する。A→B→Eにフローを4加えると、残余ネットワークは次のとおり。

残余ネットワーク(第1段階)

A→D→Eに6加える。

残余ネットワーク(第2段階)

A→C→Eに2加える。

残余ネットワーク(第3段階)

A→B→C→Eに1加える。

残余ネットワーク(第4段階)

AからEにつながる路がないため、ループ脱出。最大流は13で、次のように流せばよいことがわかる。(流量は括弧付きで記す)

この例の最適解です。

最大流最小カット定理

全体を、ソースを含む部分Sとシンクを含む部分Tの2つに分割するとき、SとTの組をカットという。Sの点からTの点に流れ込む容量の合計を、そのカットの容量という。存在しうカットの中で容量が最小のものは、その容量と最大流が一致する。これが最大流最小カット定理である。つまり、最大流をめることと最小カットめることは同等な関係にある。これは線形計画問題における双対問題であることを意味している。

前述の例でいうと、最小カットは以下の通り。

最小カットです。

他のカットを調べても、確かに13より小さくなることはない。

関連項目

【スポンサーリンク】

  • 14
  • 0pt
スマホ版URL:
https://dic.nicovideo.jp/t/a/%E6%9C%80%E5%A4%A7%E6%B5%81%E5%95%8F%E9%A1%8C

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

最大流問題

19 ななしのよっしん
2013/07/19(金) 02:39:38 ID: C0EeKT/4xW
何でこんなところに記事が・・・と思ってたら分かりやすくて吹いた
20 ななしのよっしん
2014/02/09(日) 15:47:35 ID: 3f3TLXI487
なんでこんなに詳しい記事があるんだよwwww
21 ななしのよっしん
2014/07/28(月) 08:11:10 ID: e+sT6SgI/S
テスト前だったのでたすかりました!ありがとうございます!
22 ななしのよっしん
2014/07/31(木) 04:24:58 ID: NxmdDMchlb
Wikipediaより詳しい。
神様ありがとうございます
23 ななしのよっしん
2014/07/31(木) 04:26:03 ID: NxmdDMchlb
詳しいもとい解りやすい。
感動のあまり誤謬が…。
24 ななしのよっしん
2015/01/27(火) 20:54:52 ID: j3REUt7SYg
本でアルゴリズムイミフだったから飛ばしてたやつだ~
ありがと
25 ななし
2018/03/23(金) 20:32:53 ID: BpHcDODDx7
https://img.atcoder.jp/arc092/editorial.pdfexit
のC: 2D Plane 2N Points を最大流問題アルゴリズムに適用しようとしたら上手く行かなかったです。
なんか勘違いしてるんですかね。
26 ななしのよっしん
2018/07/15(日) 18:22:38 ID: Vdp41Zd7gX
大学の講義1時間半分よりわかりやすいやんけ!
27 ななしのよっしん
2018/11/21(水) 16:34:02 ID: R5+OLaWFgj
なるほど、まったくわからん
28 ななしのよっしん
2019/10/18(金) 07:51:28 ID: V6WMEkmt0Y
アルゴリズムの本よりグラフ理論の本といった感じがする
面に書くと線が交差するような有向グラフであっても点集合を2つに分ければカットと呼べるのかな?
知らんけど

急上昇ワード改