定義・基本的な用語

またマッチングに関連する以下の基本的な用語も押さえておきましょう。

この定義からグラフ\(\,G\,\)の完全マッチング\(\,M\,\)が存在したら，それは最大マッチングにもなることを押さえておきましょう。

定義だけでは分かりづらいと思うので，次節でイメージを確認していきましょう。

イメージ

簡単のため，まずは\(\,2\,\)部グラフのマッチングについて考えていきましょう。

\(2\,\)部グラフのマッチングは男女のお見合いを考えると分かりやすいです。

次のように構成される，\(\,X,Y\,\)を部集合とする\(\,2\,\)部グラフ\(\,G(X,Y)\,\)について考えましょう。

まさにお見合いの設定です。

例えば下のような男性\(\,5\,\)人，女性\(\,5\,\)人からなるお見合いが考えられます。

男性\(\,x_2\,\)について言えば，\(\,3\,\)辺\(\,x_2y_1,x_2y_2,x_2y_4\,\)が存在するので，
男性\(\,x_1\,\)は女性\(\,y_1,y_2,y_4\,\)とお互いに気になっている状態になりますね。

このとき下のような赤い辺からなるマッチング\(\,M\,\)が考えられます。

これはお見合いの結果，カップル\(\,x_2y_2,x_3y_3,x_4y_5,x_5y_1\,\)ができたと解釈できます。

つまり\(\,2\,\)部グラフのマッチングはお見合い結果と考えられるということです。

同様に他の用語についても，このお見合いの状況と照らし合わせると次のようにまとめることができます。

\(2\,\)部グラフにおいて
• マッチング\(\,\cdots\,\)お見合い結果
• 飽和されている\(\,\cdots\,\)お見合いして彼氏・彼女ができた
• 最大マッチング\(\,\cdots\,\)カップル数が最も多いお見合い結果
• 完全マッチング\(\,\cdots\,\)全員に彼氏・彼女ができたお見合い結果

先程のグラフをもとに，このイメージを理解すると良いでしょう。

ちなみに赤い辺で与えたマッチングは明らかに完全マッチングではありませんが，最大マッチングにはなっています。

※男性\(\,x_1,x_3\,\)が女性\(\,y_3\,\)だけを狙っているので，どんなお見合い結果でも男性\(\,x_1,x_3\,\)の片方しか彼女ができないことから最大性が分かります。

ここまでは男女のお見合いをもとに説明していきましたが，他にも色々な具体例が考えられます。

例えば学校のクラスの係決めにおいて，
一方の部集合をそのクラスの生徒達，もう一方をクラスの係とし，
生徒がその係を希望しているとき，その生徒と係を辺で結ぶと考えると，
マッチングは係決めの結果を表すと考えられますね。

一般のグラフについても
生徒達をグラフの点とし，辺はすべて結んだ場合のグラフのマッチングは，生徒達でペア作成した様子を表すと考えられます。

体育の授業で二人組を作った様子と言えば分かりやすいでしょうか。

このように，一般のグラフにおいてもマッチングはなんらかのペアを作成した結果だと考えることができます。

発展的な内容へ

マッチングについてさらに詳しく学習したい方は，以下の記事をオススメします。

【グラフ理論】ホールの結婚定理とは？
\(\to\,\)マッチングの最も基本的な定理を学びたい方におススメです。

【グラフ理論】最大マッチングとは？
\(\to\,\)\(\,2\,\)部グラフの最大マッチングを求めるアルゴリズムを知りたい方，\(\,M\text{-}\)交互道・増大道について学びたい方におススメです。

【グラフ理論】安定マッチングとは？
\(\to\,\)より現実のお見合いに即したマッチングのモデルを考えたい方におススメです。

【グラフ理論】絶望の定理とは？
\(\to\,\)面白い名前の定理を理解したい人や，有名な病院僻地定理との関連を知りたい方におススメです。

今回の記事ではマッチング(matching)を解説いたしました。

発展的な内容も面白いので，そちらも読んでいただけると嬉しいです。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。