アルゴリズムクイックリファレンス 第2版

8.3

 二部マッチング

■

263

が、各品種の使用量は変動する。この問題を解くアルゴリズムの実際のアプリケー

ションには、無線ネットワークのルーティング（

Fragouli and Tabet, 2006

）が

ある。

Leighton

と

Rao

は、多品種フロー問題でよく引用される論文を書いている

（

Leighton and Rao, 1999

）。

最大フロー問題には、次のような変形がある。

節点容量

フローネットワークで、グラフの節点

v

に、その節点を流れる最大容量

k(v)

が課せられたらどうなるだろうか。修正フローネットワーク

G

m

を次

のように構築する。ネットワークの各節点

v

に対して、

2

つの節点

v

a

と

v

b

を作り、容量

k(v)

の辺

(v

a

, v

b

)

を作る。

G

内の容量

c (u, v)

の

v

に入ってく

る辺

(u, v)

に対して、容量

c(u, v)

の新しい辺

(u, v

a

)

を作る。

G

内の

v

か

ら出て行く辺

(v, w)

に対して、

G

m

内に容量

k(v)

の辺

(v

b

, w)

を作る。

G

m

を解くと、

G

の解になる。

無向辺

フローネットワーク

G

で、無向辺の場合はどうなるだろうか。次のよう

に修正フローネットワーク

G

m

を構築する。新しいグラフでも節点は同じ

である。元のグラフの容量

c(u, v)

の各辺

(u, v)

に対して、辺の対

(u, v)

と

(v, u)

を同じ容量

c(u, v)

で作る。

G

m

を解くと、

G

の解になる。

8.3

 二部マッチング

マッチング問題は、さまざまな形態で存在する。次のようなシナリオを考えよう。

5

人の求職者が、募集中の

5

つの業務に関して面 ...