アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム

No.



4-9

 頂点を共有しない辺の集合を「マッチング」といいます。マッチングは頂点同士をペアにする

ことを意味しています。ここでは、

2

つの異なるグループの間の関係を表す二部グラフのマッチン

グを見ていきます。

A

B

C

D

E

F

1

2

3

4

5

図のにとに分てりののとのつグ

ラフ「グラフ」といい

A

B

C

D

E

F

1

2

3

4

5

共いの合「マッチング」といい図のレンジのの合はマッチング



01

02

の

の

とと



2

のは

A



C



E

の

3

つの

と



01

のに

 と 「 

1

」に「 



B

」「

2

」に

「

E

」  「 

4

」

に「  

D

」  り

てと







 

03

の説明からわかるとおり、つまりマッチングは「どの人にも仕事を

2

つ以上は割り

当てず、どの仕事も

2

人以上には割り当てられないようにしたもの」と解釈できます。

A

B

C

D

E

F

1

2

3

4

5

A

B

C

D

E

F

1

2

3

4

5

の図のレンジのの合はマッチング

はり

B



4

数のに共

さてい

マッチングのにていは ...