組合せとグラフの理論（塩田）第14回 (1) マッチングの定義
マッチする、ということ
問 1 10人の刑事を2人ずつのペアにして捜査を行いたい。
ただし、気の合わない者をペアにして支障をきたすといけないので、
気の合う者同士のペアを作ることにする。
「気の合う関係」が次のグラフで表されるとき、どのようなペアを作ればよいか。
定義
このように辺の中からいくつかを選んで頂点のペアを作ったものをマッチングと言います。 グラフ理論用語で定義を書くと次のようになります。 他にもいくつか例を見てみましょう。
Ex.3 図の赤い部分がマッチングです。
必ずしも全ての頂点をペアにしなくてもマッチングと呼びますし、
全くペアの無い「ゼロマッチング」もマッチングのひとつです。
気持ちとしてはたくさんペアを作れる方が嬉しいので、次の定義をします。
さらに「全ての頂点を含むマッチングが存在するか」
ということを考えるのですが、二部グラフか否かで様相が違いますので、
まずは二部グラフを扱いましょう。