「二部マッチング問題」とその応用

今回からは 4 回の記事にわたって、アルゴリズムで解ける発展的な問題をいくつか紹介します。競技プログラミングの簡単な問題ではあまり出題されないアルゴリズムもありますが、本稿によって「アルゴリズムという武器を使えばこんな問題も解けるんだ」ということを体感していただけると嬉しいです。

二部マッチング問題

最初に紹介する問題は「二部マッチング問題」です。4 匹の犬 （A, B, C, D） と 4 匹の猫 （E, F, G, H） がいます。以下に示す犬と猫のペアは仲良しですが、それ以外のペアは残念ながら仲が良くありません。

• 犬 A と猫 E
• 犬 A と猫 F
• 犬 A と猫 G
• 犬 B と猫 G
• 犬 C と猫 H
• 犬 D と猫 G

仲良しの犬と猫のペアは、一緒に遊ばせることができます。それでは、最大で何組のペアを同時に遊ばせることができるのでしょうか。

答えは 3 組です。例えば A と E、B と G、C と H を遊ばせると 3 組になりますが、ペアを 4 組つくることはできません。（イメージ図を以下に示します。この図では仲良しの犬と猫のペアを線で表しています）

このように、最大何組のペアを遊ばせられるかを求める問題を「二部マッチング問題」と言います。