Action disabled: source

最大流問題

問題設定

水道管のような、リンクを通じて何かが流れるネットワークを想像する

  • 有向グラフ $G$ がある
  • ノード $s$ から $t$ に、水を流す
  • 各リンクには容量 $cap$ があり、そのリンクを通じては $cap$ までの量しか流せない
  • $s, t$ 以外のノードでは流入量と流出量は一致する
  • 最大流せる流量を求めよ
       ① -9→ ②
  10↗    \6    \8
  /        ↘     ↘    ※リンク上の数値はcap
s-4→ ③ -3→ ④ -4→t

この場合、たとえば以下のように配分することで、12を流すことができる。

       ① -8→ ②
  10↗    \2    \8
  /        ↘     ↘    ※リンク上の数値は流量
s-2→ ③ -2→ ④ -4→t

わかりやすい図とかは上記リンク先参照

解き方

「逆辺」という概念を利用する。逆辺とは、$G$ の各辺を逆向きに繋ぐリンク。

  1. 答えとなる流量を $f$ とし、$f=0$ で初期化する
  2. $G$ に「逆辺」を追加する
  3. 各リンクに「残容量」を設定する
    • オリジナルの辺の残容量の初期値は、そのリンクの容量 $cap$
    • 逆辺の残容量の初期値は $0$
  4. $s$ から $t$ まで流せる任意の経路を探す
    • 残容量が0より大きい辺のみを辿る
    • 経路が見つからなければ終了。その時点の $f$ が答え
    • 見つかったら、その経路で流せる流量 $d$ を求める
      • $d=$経路中のリンク残容量の最小値
  5. $G$ を更新する
    • 経路の各リンクの残容量を $d$ ずつ減らす
    • 経路の逆方向の各リンクの残容量を $d$ ずつ増やす
  6. $f$ に $d$ を加え、4.に戻る

なぜ逆辺が必要なのか

いきなり逆辺なんて出てきて「何じゃこりゃ」と思うが、これを使うと貪欲法(見つかった経路に最大限流す、を繰り返す)が上手くいく。

逆辺の無い貪欲法で解くと、経路を発見する順番によっては最大を達成できなくなる場合がある。

逆辺の無いネットワーク
       ① -9→ ②        s→tの経路をどれか1つ見つける際、
  10↗    \6    \8     s-①-④-tの経路を最初に見つけてしまうと……
  /        ↘     ↘    流量4を流した結果、④-tのリンクがそれ以上使えなくなる
s-4→ ③ -3→ ④ -4→t
                         (下図:s-①-④-tに流量4を流した後の残容量)
       ① -9→ ②           
   6↗    \2    \8     最適解は、経路s-①-②-tに多めに流すことで
  /        ↘     ↘    経路s-①-④-tに流す容量を少なくし、
s-4→ ③ -3→ ④ -0→t リンク④-tを経路s-③-④-tのために開けておくのが良い
逆辺を張ったネットワーク(正方向残容量/逆方向残容量)
          9/0 
      ①ーー-→②        経路s-①-④-tを最初に見つけて流した後の状態
 6/4↗  \2/4    \8/0   
  /      ↘   0/4 ↘    同じく④-tのリンクは使えなくなっているが、
sー→③ー→④ーー-→t  代わりにs③④①②tという経路が使えるようになっている
  4/0   3/0              リンク①-④の逆辺を利用し、流しすぎた容量を「押し戻す」感覚。

                         これにより、経路の発見順にかかわらず、全経路が網羅される

高速化

Ford-Fulkerson

  • $s$ から探索して $t$ までの経路を発見
  • $G$を更新(経路の残容量を$d$減らし、逆を増やす)

という流れを繰り返す素朴な方法は、フォード・ファルカーソンのアルゴリズムという。

計算量は$O(Ef)$、ただしE:リンク数、f:最大フロー

Dinic法

1つの経路 $R$ が見つかって $G$ を更新した後、次の経路を求める際に、影響があるのは $R$ と辺を共有する経路だけである。 他の経路は、途中までの探索結果を利用できるはずだ。

それをアルゴリズムとして確立したのが、Dinic法となる。

  1. $s$ からBFSを行い、各頂点の $s$ からの距離 $level_v$ を記憶しておく(距離=たどるリンク数)
  2. $s$ からDFSを行い、$t$ までの経路を1つ見つける
    • BFSで求めた $level_v$ が増加する方向にのみ移動する
    • 各ノードにつき、「探索した結果、$t$にたどり着けなかった辺」を覚えておく
    • 経路が見つかったら、$G$ を更新する
  3. 改めて $s$ からDFSを行う
    • やり方は同様
    • 前のDFSで、$t$ にたどり着けないとわかった辺は使わない
    • 見つかったら、$G$ を更新し、3.に戻る
    • 見つからなくなったら、探索した辺をリセットし、1.に戻る

※BFSもDFSも、残容量が残っているリンクのみを探索する。

BFSの時点で $t$ までの経路が見つからない状態になれば、それが最大流。

And more.

もっと高速化は進んでいるらしいのだが、理解が追いつかないため、無視。

事前処理に時間をかけることで、クエリの時間を短縮しているアルゴリズムもある。

実装

Dinic法 - tkw’s diaryを参考に。

from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))

# 使い方
mf = Dinic(6)
mf.add_link(0, 1, 10)
mf.add_link(0, 3, 4)
mf.add_link(1, 2, 9)
mf.add_link(1, 4, 6)
mf.add_link(2, 5, 8)
mf.add_link(3, 4, 3)
mf.add_link(4, 5, 4)
print(mf.max_flow(0, 5))

最小カット問題

最大流問題の答えは、最小カット問題の答えと一致する。

問題設定

  • 有向グラフ $G$ がある
  • 各リンクには非負のコストが与えられている
  • ある2点 $s, t$ について、$s→t$ まで行けなくなるように、リンクを取り除く
  • 取り除くリンクのコストをできるだけ少なくしたい場合、いくつになる?

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

最小流量制約

  • 使用シーン
    • 最低これだけ流さないといけない、というのが各辺(または一部の辺)にあって、その上で最大流を求めたい
    • 最大流が不要でも「このリンクに最低これだけ流した上で、$s→t$ まで破綻せず流せる?」というのを調べたい

いま、

  • 最低 $a$ 流さないといけなくて、容量が $b$ の辺 $(u,v)$
  • 最低 $c$ 流さないといけなくて、容量が $d$ の辺 $(w,x)$

があったとすると、

ⓢ -..-> ⓤ --[a,b]--> ⓥ -..-> ⓦ --[c,d]--> ⓧ -..-> ⓣ

最小流量制約を処理するための便宜的な起終点 $S,T$ を用意して、以下のように辺を張りなおす。
(ここでの辺は、容量のみが決められた、通常の最大流の辺)

                        ,----a---- S ----c----,
                       ↓                     ↓
ⓢ -..-> ⓤ --(b-a)--> ⓥ -..-> ⓦ --(d-c)--> ⓧ -..-> ⓣ
         |                     |
          `---a----> T <----c---'

こうしてフローを流したとき、$S$ から出る辺、$T$ に入る辺の容量が最小流量制約を表現している。
最低流量分はとりあえず辺の上流側頂点から $T$ に分離させて、改めて下流側頂点に $S$ から供給する。
こうすることで、最低流量分を流したかどうかが、全体に紛れずに、単独で確認できるようになる。

つまり、$S,T$ につながる辺の容量は全て使い切らないといけない。
使い切った上で、「$s→t$ への最大流 + 各辺の最小流量制約」が、最大流となる。

「$S$ から出る辺、$T$ に入る辺」を説明上、「必須辺」と呼ぶことにする。

必須辺の容量を使い切れない場合、条件を満たすフローは存在しないことになる。

しかし、単純に流すだけでは、 「上手いことやれば必須辺の容量が全て使えるが、探索順の関係で $t$ への辺などに優先的に流れてしまい、$T$ への辺の容量を全て使えず、『破綻』と判定されてしまう」などということが発生しうる。

以下の順序で流すと、必須辺を優先的に使うことが保証される。

  • $S→T$
  • $S→t$
  • $s→T$
  • ここまでで、$S$ から出る辺、$T$ に入る辺に流れた量を調べて、可能不可能を判定
  • $s→t$ で最大流を得る

また、可能不可能の判定だけでよいなら、$t→s$ に容量無限の辺を張った上で、 $S→T$ へ最大流を流し、必須辺の容量使い切りチェックすればフロー1回でいける。

Python3

programming_algorithm/graph_theory/maximum_flow.txt · 最終更新: 2023/01/16 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0