Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
28
Help us understand the problem. What is going on with this article?
@kanten4205

ネットワークフローを基礎から学びたい!【第1編 - これは知っておこう】

 みなさん、こんにちは。Kanten4205 です。
 2021/03/26 ~ 2021/03/28 の期間で、日本情報オリンピックの春季ステップアップセミナーが開催され、私も受講しました。私は、選抜参加者ではなかったので、チューターがいない中お勉強をしましたが、それでもかなり多くのことを学べました。サブチューターの方々にもいろいろ教えていただきました。本当にありがとうございました。
 さて、私はこの 3 日間で、できないことを身につけようと思い、ネットワークフローの勉強をしました。セミナーで用いた書籍「問題解決力を鍛える!アルゴリズムとデータ構造」(以下、けんちょん本)でいうと、第 16 章にあたります。このセミナーで、私はこれをしっかりと理解し、これを使って問題を解くこともできました。せっかくなので、忘備録というわけではないですが、ここに書き残しておこうと思います。
 第1編と書いてますが、第2編以降いつ書くか決まってないです(必ず書きはします)。

前提知識

 ここでは、前提知識を必要とします。具体的には、次の内容です:

  • グラフの基本
  • グラフアルゴリズム(DFS、BFS、最短路、最小全域木など)

 これらを学ぶものとして、例えばアルゴロジックなどを読めばいいと思います(なげやり)。

目次

1. 基礎知識 - link

項目番号 項目 リンク
1-1. ネットワークフローってなに? link
1-2. カット link
1-3. 辺連結度 link
1-4. 辺連結度に関する問題の、弱双対性・強双対性 link
1-5. 残余グラフ link

2. 辺連結度を求めるアルゴリズム - link

項目番号 項目 リンク
2-1. イメージ link
2-2. 正しく求められる...? link
2-3. 結局、どんなアルゴリズムなのか link
2-4. 証明 link
2-5. 計算量 link
2-6. 実装 link

3. おわりに - link

4. 参考文献 - link

1. 基礎知識

 では、ここではいろいろな基本的な事項を学んでいくこととしましょう。

1-1. ネットワークフローってなに?

 「ネットワークフロー」と書いてググったら、いろいろ出てくるわけなんですが、どれもよくわからないので簡単に自分の言葉で説明してしまおうと思います。
 といっても、ネットワークフローというのは、「最大流問題や最小カット問題などの総称」(最大流問題・最小カット問題とはなにか、については第2編で説明します)というほかはありません。グラフに関する問題の中でも、特に「始点と終点が定められていて、その間のパスでどれくらいの水を流せるか」みたいな問題の総称がネットワークフローとなります。 うまく説明できないので誰か説明お願いします(他力本願)。

1-2. カット

 まずは、「カット」というものを定義します。
 下のようなグラフを考えます。
スクリーンショット (42).png
 この8つの頂点の集合を、5つの頂点の集合と3つの頂点の集合に分けることを考えてみましょう。例えば、{ 頂点 1, 2, 5, 6, 7 } という集合と、{ 頂点 3, 4, 8 }という集合に分けることができますね。そうなるように、2 つの頂点の集合を図で示したものが下の図です。ここで、2 つの頂点の集合を $X,\ Y$ とします。
スクリーンショット (43).png
この分け方を、カット $(\mathbb cut)$ といいます。わかるかもしれませんが、このようなカットは複数種類あります。さらに、集合 $X,\ Y$ の要素数を変えれば、もっと種類はあります。
 カットを数学用語を使って定義しますと、グラフ $G = (\ V,\ E\ )$ について、頂点集合 $V$ の分割 $(\ X,\ Y\ )$ のことを カット $(\mathbb cut)$ といいます。
 以降、このようなカットを、カット $(\ X,\ Y\ )$ と表します。
 さて、この状態で、辺に注目してみましょう。ここには、大きく分けて 3 種類の辺があります。
 ① $X$ に含まれる 2 頂点を結ぶ辺
 ② $Y$ に含まれる 2 頂点を結ぶ辺
 ③ $X$ に含まれる 1 頂点と $Y$ に含まれる 1 頂点を結ぶ辺
 これを色分けしてみましょう。
スクリーンショット (44).png
 緑色の辺が①の辺、黄色の辺が②の辺、赤色の辺が③の辺に相当します。
 この、赤色の辺のことを カット辺 $(cut\ edge)$ といいます。そして、このカット辺全体の集合を カットセット $(cut\ set)$ といいます。
 ここでは無向グラフに対して定義していますが、有向グラフに対しても同様に定義可能です。この場合、カット辺の定義は、「カット $(\ X,\ Y\ )$ のカット辺とは、$X$ に含まれる頂点を始点、$Y$ に含まれる頂点を終点とする辺のことである」となります。そして、このカットセットに含まれる辺の本数を、カット $(\ X,\ Y\ )$ の容量 $(capacity)$ といい、$c(\ X,\ Y\ )$ と表します。
 例)下のグラフのカット $(\ X,\ Y\ )$の容量は、$3$ です。
スクリーンショット (46).png

1-3. 辺連結度

 続きまして、辺連結度のお話でもしましょう。
 まずは、一つ問題を。下のグラフについて、頂点 $s$ から頂点 $t$ に対して互いに辺を共有しない $s$-$t$ パス(頂点 $s$ と頂点 $t$ をつなぐパス)は最大で何本とれますか?
スクリーンショット (49).png
 正解は、2 本です。下図のように、赤色の辺を辿っていくパスと、緑色の辺を辿っていくパスがあります。
スクリーンショット (50).png
 この、頂点 $s$ から頂点 $t$ に対して互いに辺を共有しない $s$-$t$ パスの本数の最大値を、グラフの 2 頂点 $s, t\ $に関する 辺連結度 $(edge$-$connectivity)$ といいます。上のグラフの辺連結度は $2$ ということになります。
 そして、この「互いに辺を共有しない」ことを、辺素$(edge$-$disjoint)$ といいます。例えば、上図の赤のパスと緑のパスは辺素です。
 本当に、辺連結度は $2$ なのでしょうか。次の図をご覧ください。
スクリーンショット (52).png
赤の辺は、頂点集合 $X$ から頂点集合 $Y$ へ出ていく辺です。これが $2$ 本あることが、根拠となります。
 頂点 $s$ から頂点 $t$ へ行くためには、必ず頂点集合 $X$ から頂点集合 $Y$ へ行かなければなりません。頂点集合 $X$ の中でぐるぐるしていても、頂点 $t$ には行けそうにないですよね。まあ、あまりぐるぐるできないんですけど。 よって、辺連結度は $2$ であると言えます。
 ちなみに、上のカットのように、$s \in X,\ t \in Y$ を満たすカットを、$s$-$t$ カットといいます。

1-4. 辺連結度に関する問題の、弱双対性・強双対性

 まず、次の性質を紹介します。
スクリーンショット (56).png

 ちょっと考えれば比較的自明に分かることですが、これが成り立つ根拠を簡単に述べると、「辺素な $s$-$t$ パスの最大本数を $k$ 本としたとき、頂点 $s$ を含む頂点集合から、頂点 $t$ を含む頂点集合へ出ていく辺の本数は最小で $k$ 本ある」ことです。例えば、下図のような感じです。緑の辺は、辺素な $s$-$t$ パスを構成する辺です。
スクリーンショット (61).png

 この性質を、弱双対性 $(weak\ duality)$といいます。これは何を意味しているのでしょうか。
 辺素な $k$ 本の $s$-$t$ パスの集合があり、容量が $k$ である$s$-$t$ カットが存在するとき、次が成立します:

  • 辺素な $s$-$t$ パスの最大本数 = $k$
  • $s$-$t$ カットの最小容量 = $k$

 つまり、この時に辺素な $s$-$t$ パスの最大本数は、考えられる最大本数、言い換えれば「辺連結度」なのです。それと同時に、辺連結度と $s$-$t$ カットの最小容量は一致することもわかります。すなわち、次の性質が成り立ちます:
スクリーンショット (63).png
 この性質を、強双対性 $(strong\ duality)$といいます。1927年に、Carl Menger によって証明されました。Menger の定理と呼ばれることもあるようです。また、後で紹介する、辺連結度を求める問題や「最小カット問題」は、互いに 双対問題であると言います。

1-5. 残余グラフ

 ここまで話したら、辺連結度を求めるアルゴリズムを知りたい!と思われるところだとは思いますが、その前にもう少し知識を詰めておかねばなりません。
 残余グラフは、「フローをあとどれだけ流すことができて、またどれだけ戻すことができるかを表す重み付き有向グラフ」です。言葉だけじゃわからないよ。というわけで、次の、「本の貸し借り」を例として示します。
スクリーンショット (104).png
 このとき、本を借りた人は、貸してくれた人に対して次の2種類の行動をとることができます:
スクリーンショット (105).png
 本を失くしたから紛失届を出すとか、コーヒーをこぼしたから破損届を出すといった行動も考えられるかもしれませんが、ここでは上の 2 通りだけを考えます。つまり、「さらに何冊か借りる」か、「何冊か返す」か、という2つのことだけを、2人の間で実行可能とするということです。
 この2人の間にある関係は、どのように変化したでしょうか。次の図を見てください。
スクリーンショット (112).png
 もともと、貸す人から借りる人への一方的な関係しかなかったところに、逆向きの関係が追加されています。また、貸すことのできる本の冊数の最大値が、8冊から5冊に減っています。最初に言った言葉に当てはめれば、「本をあと5冊貸すことができて、また3冊返すことができる」ということです。
 さて、抽象化しましょう。2頂点 $s,\ t$ について、$s$ と $t$ の関係に、この例の値をそのまま当てはめてみます。いわゆる「辺の重み」は、各辺の容量を表すことになります。その辺では容量以下のフローを流すことができます。
スクリーンショット (123).png
 この図の、左のような関係であったグラフが右のような関係となったグラフを、残余グラフと言います。
 一般化した図が下図です。ここで、$0 < m \leq n$ とします。
スクリーンショット (125).png
 いかにも有向グラフじゃないとできないみたいな感じですが、無向グラフでも実現可能です。無向グラフを形成させるプログラムからもわかるかと思いますが、無向グラフの各辺は、2頂点 のそれぞれの向きに有向辺を張っているのと一緒なので、そう考えればあとは考えやすいかなと思います。具体的に、無向グラフの場合の残余グラフは、次のようになります。
スクリーンショット (124).png

2. 辺連結度を求めるアルゴリズム

 さて、辺連結度の話に戻ります。これを求めるために、どんなアルゴリズムを使えばよいのでしょうか。ひとことで紹介します。
スクリーンショット (117).png
 完全にスペースの無駄な気がしますが、ともかく辺連結度は、貪欲法を使って解くことができます。
 ここでは、どんな貪欲法をしていけばいいのかというと、「$s$-$t$ パスを取れるだけとる」というやり方です。DFSに近い考え方といった感じでしょうか。

2-1. イメージ

 まずは、どんな感じかを見てみましょう。次のような有向グラフを考えます。
スクリーンショット (132).png
 $s = 1, t = 4$ として、$s$-$t$ パスの本数を考えてみます。
 このとき、このアルゴリズムは次のような遷移をします。
lt9DA8etPICk1iz5h9F21619313045-1619313157.gif

2-2. 正しく求められる...?

 しかし、ここで一つ問題が生じます。上の遷移通りに行けば、正しく辺連結度を求めることができますが、たとえば、1本パスを取った状態で次のような状態だった場合、単純な貪欲法ではうまくいかないように見えます。
スクリーンショット (162).png
 このままでは、$s$-$t$ パスは1本しかとれません。どうすれば、正しい答えを導くことができるでしょうか。
 ここで使うのが、先ほどお話しした「残余グラフ」です。ここでは、一つ $s$-$t$ パスをとったら、そのパスを構成する各辺に対して、逆向きの辺を張りなおしたグラフを考えることになります。
スクリーンショット (164).png
 上図のように、赤色の辺を、それぞれ逆向きに張り直し、青色の辺のようにします。この後、右の残余グラフを見てみると、1 -> 5 -> 3 -> 4 という順番で、$s$ から $t$ へ行くことができ、また1本 $s$-$t$ パスがとれます。
 このように、1本 $s$-$t$ パスが存在したら、そのパスを構成する各辺を逆向きに張りなおした残余グラフを作って、それに対して $s$-$t$ パスがあるかどうかを調べる、という操作を繰り返すことで、辺連結度を求めることができます。

結局、どんなアルゴリズムなのか

 これを、疑似コードみたいに書き起こすと、次のようなアルゴリズムになります。

G はグラフ
f := 0 (f は G の s-t パスの本数を表す)
G' := G (G' は G の残余グラフ)
G' に s-t パスが存在する限り次の処理を繰り返す:
 f := f + 1
 G' の、みつけた s-t パスを構成する辺をそれぞれ逆向きに張る
f は求める辺連結度

2-3. 証明

 ここでは、次の事柄を証明します:
 ある連結の有向グラフ $G$ について、取れるだけ $s$-$t$ パスを取った時、そのパスの本数を $k$ とすると、$k$ は $G$ の辺連結度である。
 先ほどの例 で考えてみましょう。
 パスを取れるだけ取り終わった後、次のようなグラフになっています。(注:便宜上、頂点の配置を変えています):スクリーンショット (179).png
 そして、これの残余グラフは次のようになります。スクリーンショット (176).png
 これを、2つの頂点集合に分けます。
 $X$ を残余グラフにおいて頂点 $s$ から到達することのできる頂点の集合、$Y$ をそれ以外の頂点の集合とします。スクリーンショット (180).png
 この図からもわかるように、明らかに $X\ \cap\ Y = \varnothing$ です。
 このとき、次の 2 つのことが成り立ちます:

  • 元のグラフについて、$X$ から出ていく任意の辺 $e = (u,\ v)\ (u \in X,\ v \in Y)$ は、$k$ 本の $s$-$t$ パス $P_1,P_2,\cdots,P_k$ のいずれかに含まれている。上の場合、辺 $(1, 2), (5, 8)$ はいずれも $s$-$t$ パスに含まれている。(もしこれが成立しない場合、すなわち いずれのパスにも含まれない辺 $e = (u,\ v)\ (u \in X,\ v \in Y)$ が存在する場合、その頂点 $v$ は残余グラフにおいても頂点 $s$ から到達することができることになるので、$X\ \cap\ Y = \varnothing$ より $v \in X$ となるはずだが、これは $v \in Y$ という条件に矛盾する)
  • 元のグラフについて、$X$ へ入っていく任意の辺 $e = (u,\ v)\ (u \in X,\ v \in Y)$ は、$k$ 本の $s$-$t$ パス $P_1,P_2,\cdots,P_k$ のいずれにも含まれない。上の場合、辺 $(1, 6), (5, 3)$ はいずれも、どの $s$-$t$ パスにも含まれていない。(もしこれが成立しない場合、すなわち いずれかのパスに含まれる辺 $e = (u,\ v)\ (u \in X,\ v \in Y)$ が存在する場合、その頂点 $v$ は残余グラフにおいて辺の向きが逆になるため、頂点 $s$ から到達することができることになるので、$X\ \cap\ Y = \varnothing$ より $v \in X$ となるはずだが、これは $v \in Y$ という条件に矛盾する)

 以上から、$u \in X,\ v \in Y$ である任意の辺 $e = (u,\ v)$ は、それぞれ $P_1,P_2,\cdots,P_k$ と一対一に対応するので、 $c(X, Y) = k$ であることがわかります。これは、上記のアルゴリズムによって得られた $k$ 本の辺素な $s$-$t$ パス $P_1,P_2,\cdots,P_k$ が、このグラフで取れる辺素な $s$-$t$ パスの最大本数を達成していることを意味しています。よって、個のアルゴリズムは正しいことが証明されました。

2-4. 計算量

 グラフの頂点集合を $V$、辺集合を $E$ とします(以降、前置きなしに $V, E$ が用いられたときはそれぞれこの意味であると思ってください)。
 $s$-$t$ パスを調べるときは、まず $s$ から出ている辺を全て探索する必要があります。$s$ から出る辺の本数は、最大で $|V| - 1$ 本になります($|V|$は、$V$ の要素の個数を表します。ここでは、頂点の個数)。スクリーンショット (181).png
 よって、$s$-$t$ パスの本数 $k$ は、最大でも $O(|V|)$ に抑えられます。
 それぞれの辺について、 $s$-$t$ パスを調べる操作は、パスを構成する辺の候補となる辺を1回ずつ見ればよいので、最大でも $O(|E|)$ に抑えられます。よって、全体的にこのアルゴリズムの計算量は、$O(|V||E|)$ であるといえます。

2-5. 実装

 先ほどのアルゴリズムを実装してみましょう。大まかな実装方針としては、頂点 $s$ を始点としてDFSを実行して、もしその途中で頂点 $t$ に到達したら、その辺を逆に張る、を繰り返していくというやり方にしたいと思います。
 (DFS が何かわからない方は、けんちょんさんの記事 をご覧ください。)
 ここで、構造体 Graph というものを作ります。けんちょん本に載っているコードを丸パクリしちゃってます(ごめんなさい)が、これよりわかりやすく書く方法が見つからないので許してください。
 この構造体で必要な操作は、「辺を張る」操作と、「辺にフローを流す」操作です。辺にフローを流すとき、その反対方向の辺の流量を増やす必要があるので、注意してください。

構造体 Graph の実装例 (けんちょん本より引用)
//グラフを表す構造体
struct Graph {
    //辺を表す構造体
    //rev : 逆辺 (to, from) が G[to] の中で何番目の要素か
    //cap : 辺 (from, to) の容量
    struct Edge {
        long long rev, from, to, cap;
        Edge(long long r, long long f, long long t, long long c) :
            rev(r), from(f), to(t), cap(c) {}
    };

    //隣接リスト
    vector<vector<Edge>> list;

    //N : 頂点数
    Graph(long long N = 0) : list(N) {}

    //グラフの頂点数取得
    size_t size() {
        return list.size();
    }

    //Graph インスタンスを G として、
    // G.list[v] を G[v] と書けるようにしておく
    vector<Edge>& operator [] (long long i) {
        return list[i];
    }

    //辺 e = (u, v) の逆辺 (v, u) を取得する
    Edge& redge(const Edge& e) {
        return list[e.to][e.rev];
    }

    //辺 e = (u, v) に流量 f のフローを流す
    //e = (u, v) の流量が f だけ減少する
    //この時、逆辺 (v, u) の流量を増やす
    void run_flow(Edge& e, long long f) {
        e.cap -= f;
        redge(e).cap += f;
    }

    //頂点 from から頂点 to へ容量 cap の辺を張る
    //このとき to から from へも容量 0 の辺を張っておく
    void addedge(long long from, long long to, long long cap) {
        long long fromrev = (long long)list[from].size();
        long long torev = (long long)list[to].size();
        list[from].push_back(Edge(torev, from, to, cap));
        list[to].push_back(Edge(fromrev, to, from, 0));
    }
};


 これを用いて、このアルゴリズムは次のように実装することができます。

サンプルコード
#include <iostream>
#include <vector>
//グラフを表す構造体
struct Graph {
    //辺を表す構造体
    //rev : 逆辺 (to, from) が G[to] の中で何番目の要素か
    //cap : 辺 (from, to) の容量
    struct Edge {
        long long rev, from, to, cap;
        Edge(long long r, long long f, long long t, long long c) :
            rev(r), from(f), to(t), cap(c) {}
    };

    //隣接リスト
    vector<vector<Edge>> list;

    //N : 頂点数
    Graph(long long N = 0) : list(N) {}

    //グラフの頂点数取得
    size_t size() {
        return list.size();
    }

    //Graph インスタンスを G として、
    // G.list[v] を G[v] と書けるようにしておく
    vector<Edge>& operator [] (long long i) {
        return list[i];
    }

    //辺 e = (u, v) の逆辺 (v, u) を取得する
    Edge& redge(const Edge& e) {
        return list[e.to][e.rev];
    }

    //辺 e = (u, v) に流量 f のフローを流す
    //e = (u, v) の流量が f だけ減少する
    //この時、逆辺 (v, u) の流量を増やす
    void run_flow(Edge& e, long long f) {
        e.cap -= f;
        redge(e).cap += f;
    }

    //頂点 from から頂点 to へ容量 cap の辺を張る
    //このとき to から from へも容量 0 の辺を張っておく
    void addedge(long long from, long long to, long long cap) {
        long long fromrev = (long long)list[from].size();
        long long torev = (long long)list[to].size();
        list[from].push_back(Edge(torev, from, to, cap));
        list[to].push_back(Edge(fromrev, to, from, 0));
    }
};
struct edge_connectivity {
    edge_connectivity() {}
    vector<bool>seen;
    long long find_path(Graph& G, long long v, long long t) { //パスを見つける
        if (v == t) return 1; //頂点 t に到達したら返す
        seen[v] = true;

        //DFS
        for (auto& e : G[v]) {
            if (seen[e.to]) continue;
            if (e.cap == 0) continue; //容量 0 の辺は実際には存在しない

            //s-t パスが見つかったらcapacity = {そのパスを構成する辺の本数}
            //見つからなかったら capacity = 0
            long long capacity = find_path(G, e.to, t); 
            if (capacity == 0) continue; //s-t パスが見つからなかったら次の辺へ
            G.run_flow(e, capacity); //辺 e に、容量 capacity のフローを流す
            return capacity; //s-t パスが見つかったら、パス上の辺の本数を返す
        }
        return 0; //s-t パスが見つからなかったら 0 を返す
    }

    //辺連結度を求める
    //リターンした時に、 G は残余グラフになっている
    long long solve(Graph& G, long long s, long long t) {
        long long res = 0;

        //残余グラフに s-t パスがなくなるまで探索
        while (true) {
            seen.assign((long long)G.size(), false);
            long long capacity = find_path(G, s, t);
            if (capacity == 0) return res; //s-t パスが見つからないので終了
            res += 1; //答えを加算
        }
        //s から t へ到達できなかった
        return 0;
    }
};
int main() {
    //N : 頂点の個数、M : 辺の本数、s : 始点、t : 終点
    long long N, M, s, t; cin >> N >> M >> s >> t;
    s--; t--;
    Graph G(N); //0-indexed のグラフ
    for (long long i = 0; i < M; i++) {
        long long u, v; cin >> u >> v;
        u--; v--;
        G.addedge(u, v, 1); //容量 1 の辺 e = (u, v) を張る
    }

    edge_connectivity EC;
    cout << EC.solve(G, s, t) << endl;
}

 例えば、ここに、次のような入力を与えます(先ほどの例と同じです):

8 10 1 4
1 2
1 5
1 7
2 3
3 4
3 5
5 8
6 1
7 5
8 4

 すると、次のように出力が返ってきます:

2

 これで、正しく実装ができました。

3. おわりに

 今回は、いろいろな前提知識を書き連ねたうえで、辺連結度を求めるアルゴリズムを考えました。
 このアルゴリズムの実装は、今後かなり重要になってくるので、しっかりできるといいと思います。
 次の第2編では、最大流問題と最小カット問題についてを書こうと思っていますが、いつ書けるかわからないのですぐに第2編が出るわけではないことに注意してください。

4. 参考文献

 問題解決力を鍛える!アルゴリズムとデータ構造(大槻兼資・著、秋葉拓也・監修) (リンク先は Amazon です)

28
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
kanten4205
中3の服部です. 競プロと、スピードキューブをやっていますが、どちらもよわよわです. 精進します. 皆さんの、役に立つような記事を投稿できたらと思っています. よろしくお願いします.

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
28
Help us understand the problem. What is going on with this article?