アルゴリズムc 第9回 最大流

アルゴリズムc 第9回

最大流

問題の定義は、

https://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E3%83%95%E3%83%AD%E3%83%BC%E5%95%8F%E9%A1%8C によると

以下の通りです。

最大フロー問題または最大流問題（英: Maximum flow problem）とは、単一の始点から単一 の終点へのフローネットワークで最大となるフローを求める問題である。単にフローの最大値 を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問 題である最小費用流問題の特殊ケースと見ることもできる。 最小カット問題（英: Minimum cut problem）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存 在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から 終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定 理と呼ぶ。 2部グラフの最大マッチング問題（英: Maximum bipartite matching）とは、2部 グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解 ける。

最大フローのあるフローネッ トワークの例。始点 s と終点 t があり、各枝の数値はフロー と容量を示す。

Wikipedia の定義はちょっとわかりにくいですが、要は、グラフの上で流れ（フロー）を扱うということです。

例として、次の5個のノード s, t, a, b, c から構成される有向グラフを考えます。 グラフで、ノード s からノード t に流せる最大の流量はい くらになるでしょうか？ グラフ中のエッジの「流量 (flow)」と「容量(最大流量, capacity)」を '流量/容量' の形式で表現しています。

[1] ノード s では無限量の水が湧き出していて、ノード t では無限量

の水を排水できるものとします。 sからt に流れる水の最大流量はど うなるでしょうか？

[2] まず、s -> a -> b -> t のパスに沿って、流量 3 で流してみます。

グラフ中で b -> t の有向エッジの流量が容量(最大流量)に達したの

で、点線で表しています。

[3] 次に、s -> a -> c -> t のパスに沿って、流量 3 で流してみます。

グラフ中で s -> a の有向エッジの流量は容量(最大流量)に達したの で、点線で表しています。

[4] 左のグラフをみると、もうs から t へむかうパスは存在しないよ

うに見えます。 ではsからt への最大流は 3+3=6 なのでしょうか？

[5] 実は、次のように流すことで s から t へは 7 の流量を流すことが

でき、最大流は 7 であることがわかります。

[6] [4]と[5]のグラフではどこが違うのでしょうか？ 異なる流れを赤

で示しました。 すなわち、a -> b への流量3を1だけ押し戻す ことで

s -> b -> a -> c -> t へ 1 の流量を流していることになります。

[7] そうです。あるエッジを流れる流量が n の状態では、逆方向に 0

〜 n の流量を流せるエッジが存在すると考えるべきなのです。 [4]の グラフに逆方向のエッジを加えたグラフを左に示します。 この逆方 向のエッジを流れる水は流れを押し戻している ことに相当します。

最大流を解くプログラム

最大流を解くプログラムの例を示します。 このプログラムでは、有向エッジを 終点ノード to

残された容量 cap

対になる逆向きのエッジ rev (ノードtoのrev番目のエッジ)

を持つ Edge クラスで表現しています。 各ノードが持つ情報はそのノードを起点とする有向エッジの集合 ArrayList<Edge> であり、 それ

をまとめた ArrayList<ArrayList<Edge>> がノードの集合で、グラフを表しています。

MaxFlow.javaの実行例

$ javac MaxFlow.java

$ java MaxFlow < data01.txt 7

data01.txt

5 7 0 1 6 0 2 2 1 2 4 1 3 4 2 4 3 3 2 3 3 4 5 0 4

入力データの形式

N E

S 

 D 

 C 

...

S 

 D 

 C 

F T

N はノードの数で E はエッジの数。 S 

 は i番目のエッジの始点ノード番号で D 

 は i番目のエッジの 終点ノード番号で、 C 

 は i番目のエッジの容量を表す。 0 

 S 

 < N , 0 

 0 

 D 

 < N 。 F と T はそ れぞれ湧き出しと排水のノード番号である。

最小カット

グラフ中のノードを、ノードs を含む集合 S と、ノードt を含む集合 T

に分けます。 「ノードの集合から出て行くエッジ」の集合を「カッ

ト」と呼び、 「Sに含まれるノード」から「Tに含まれるノード」へと

向かうカットを特に「s-t カット」と呼びます。 「s-tカット」に含まれ

るエッジを全て除去すると、sからtへのパスが存在しなくなります。

「sからtへのパスが存在しなくなるために除去しなければならないエッ ジの容量の和の最小値」を「最小カット」といいます。

「最小カット」と「最大流」は一致します。左の図ではどちらも 7 に なります。

二部グラフのマッチング

「ノードの集合を2つの部分集合に分割したときに、部分集合内のノード同士にはエッジが無いようにできるグラフ」 を「二部グラフ (Bipartite graph)」といいます。 また、グラフにおいて「端点を共有しないエッジの集合」を「マッチング」といいます。 二部グラフにお いて最大のマッチングを求める問題は、最大流で解くことができます。(課題15a)

応募者 c

 は3名で、仕事 t

 が3個ある。 応募者は全員1個の仕事を希 望している。 希望する仕事はそれぞれ c

はt

 か t

, c

はt

 か t

, c

はt

 である。

ノード s と t を作り、sとc

を、 t

とtを、容量1 の有向エッジで結 ぶ。 また、c

 がt

 を希望する場合は、容量1の有向エッジで結ぶ。

応募者 c

 は3名で、仕事 t

 は4個ある。 応募者c

は2個の、c

 と c

は1個の仕事を希望している。 希望する仕事はそれぞれ c

はt

 か t

か t

, c

はt

 か t

, c

はt

 である。

ノード s と t を作り、 sとc

を容量2の有向グラフで、 sとc

, sとc

を容量1の有向エッジで結ぶ。 t

とtを、容量1 の有向エッジで結ぶ。

また、c

 がt

 を希望する場合は、容量1の有向エッジで結ぶ。

最小費用流

各エッジに流量に応じて発生するコストがある場合を考えます。 sからtへ流量 F を流したときの最小費用を求める問題が、最小費用流で す。

基本的な考え方は最大流と同じですが、sからtへのパスを探すときに毎回コストが最小となるパスを求めていけばよいのです。 これは負の 重みを持つグラフの最短経路を求める話になりますから、ダイクストラ法では駄目で、Bellman-Ford法を用いて sからtへのパスを探すこと になります。

アルゴリズムc 演習

作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。

提出した後は、正しく提出されていることを 

課題提出〆切は次回の講義の開始時刻です。

課題9a

提出ファイル

BipartiteMatch.java

コメント欄:

次のデータをこの問題の入力形式で表現した bipartite03.txtの内容。

提出先:

「宿題提出Web:アルゴリズムB：課題9a」 http://nw.tsuda.ac.jp/class/algoC/local/handin/up.php?id=kadai9a 問題を解くプログラム BipartiteMatch.java を作成せよ。 MaxFlow クラスを外部から呼び出して構わない。

問題

アルバイトに応募してきた人に、仕事を割り振るプログラムを考えます。 条件は次の通りです。

応募者によって可能な仕事数は異なる。

応募者に、希望しない仕事が割り当てられることはない。

一つの仕事が、複数の応募者に割り当てられることはない。

なるべく多くの仕事を割り当てたい。

入力データの形式

N M E C 

...

C 

S 

 D 

...

S

 D 

N は応募者の数、 M は仕事の数、 E は応募者と希望した仕事との対応の数である。 C 

 は i番目の応 募者が可能な仕事の数である。 S 

 と D 

 は S 

 番目の応募者が 希望する仕事が D 

 であることを表し ている。 0 

 S 

 < N , 0 

 D 

 < M である。

bipartite01.txt

3 3 5 1 1 1 0 0 0 1 1 0 1 2 2 0

bipartite02.txt

3 4 6 2 1 1 0 0 0 2 0 3 1 0 1 1 2 0

BipartiteMatch.javaの実行例

$ javac BipartiteMatch.java

$ java BipartiteMatch <bipartite01.txt 3

$ java BipartiteMatch <bipartite02.txt 4

$ java BipartiteMatch <bipartite03.txt 4

ヒント

ノードの数が n + m + 2 個の有向グラフで表現できる。 たとえば、ノード番号を

応募者: 0...(n-1), 仕事: n...(n+m-1) src: (n+m)

dst: (n+m+1)

とすればよい。応募者が希望する仕事数が src とその応募者を結ぶエッジの容量で、それ以外のエッジの容量は全て1である。