組合せとグラフの理論(塩田)第14回 (1) マッチングの定義
戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\card}[1]{\left|\,#1\,\right|}$
マッチする、ということ
問 1 10人の刑事を2人ずつのペアにして捜査を行いたい。
ただし、気の合わない者をペアにして支障をきたすといけないので、
気の合う者同士のペアを作ることにする。
「気の合う関係」が次のグラフで表されるとき、どのようなペアを作ればよいか。
解
例えば図の赤い辺をペアとすれば 10 人全員が捜査に携われます。
「俺はこいつとしか気が合わん」という刑事さんがたくさんいましたが ( $0$, $4$, $7$, $9$ )、
なんとかペアが作れて良かったですね。
定義
このように辺の中からいくつかを選んで頂点のペアを作ったものをマッチングと言います。
グラフ理論用語で定義を書くと次のようになります。
Def.2 単純無向グラフ $G$ の $1$-正則な部分グラフをマッチングと呼ぶ。
他にもいくつか例を見てみましょう。
気持ちとしてはたくさんペアを作れる方が嬉しいので、次の定義をします。
Def.4 辺の本数が最大となるマッチングを「最大マッチング」と呼ぶ。
さらに「全ての頂点を含むマッチングが存在するか」
ということを考えるのですが、二部グラフか否かで様相が違いますので、
まずは二部グラフを扱いましょう。