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

264

■

8

章 ネットワークフローアルゴリズム

8.3.1

 入出力

二部マッチング問題は、

n

個の要素

s

i

∈

S

の集合

S

、

m

人のパートナー

t

j

∈

T

の集

合

T

、要素

s

i

∈

S

をパートナー

t

j

∈

T

に関係付ける

p

個の受理可能対

p

k

∈

P

の集合

P

とからなる。集合

S

と

T

は、互いに素であり、そこからこの問題の名前が来ている。

出力は、受理可能対の集合

P

から選ばれた対

(s

i

, t

j

)

の部分集合。これらの対が、

最大個数のマッチング可能対を表す。アルゴリズムは、これ以上多くの対はマッチ

ングできないことを保証する（ただし、同じ個数の対を得る他のマッチングはある

かもしれない）。

8.3.2

 解

この問題を解く新しいアルゴリズムを作る代わりに、二部マッチング問題を最大

フロー問題に帰着させる。二部マッチングでは、要素

s

i

∈

S

とパートナー

t

j

∈

T

の

マッチング

(s

i

, t

j

)

を選ぶと、両者とも他の対には選ばれない。フローネットワーク

グラフ

G

＝

(V, E)

において、同じ振る舞いをさせるには、

G

を次のように構築する。

V

が

n

＋

m

＋2 個の頂点を持つ

各要素

s

i

を、

i

という番号の節点に、パートナー

t

j

を番号

n

＋

j

の節点に対

応させる。新たなソース節点

src (

ラベル

0)

および新たな目標節点

tgt (

ラ

ベル

n

＋

m

＋

1)

を作る。

E

が

n

＋

m

＋

k

個の辺を持つ

新しい節点

src

から

S

の節点への

n

個の辺がある。

T

の節点から新しい節

点

tgt

への

m

個の辺がある。

k

個の対、各

p

k

＝

(s

i

, t

j

)

に対応して、辺

(i, n

＋

j)

を追加する。これらの辺のフロー容量は ...