マトロイド（３）二部グラフ

マトロイドの次の例としてマッチングマトロイドを説明しようかと思ったのだが、その前に二部グラフと（グラフの）マッチングを説明しておいた方がよさそう。二部グラフとはグラフ の頂点の集合 を２つに分割して、どの辺の端点もそれぞれ別の集合に属するようにできるときのことを言う。別の言い方をすると、 と２つの交わりのない集合に分けて、辺が必ず の頂点から の頂点へ出ている場合に二部グラフと言う。

最初に交わりのない（有限）集合 が与えられたとき、 を頂点とする二部グラフの辺は とみなせることに注意しよう。 と の要素のペアの集合を考えることと二部グラフを考えることは同値になる。マッチングマトロイドの定義も、グラフの言葉で記述する流儀と、二部グラフの場合に対応した要素のペアの言葉で記述する流儀があるようだ。

ここではグラフの言葉で記述したいので、もう少しの辛抱。

グラフ のマッチングとは、頂点を共有しない辺の集合 のこと。頂点の部分集合 がマッチング の端点からなる頂点の部分集合と一致するとき、 は で覆われているとか、マッチされているなどという。マッチングの概念は一般のグラフについて定義されるが、日常語のマッチングと意味が近いのは、二部グラフのマッチングを考えた場合である。頂点集合 と分かれている場合のマッチングは と の要素のペアの重複しない集合、すなわち２つ以上の の要素がある の要素とペアを作っていない、のことである。

さて、マッチングマトロイドであるが、これは頂点集合 とマッチングによってマッチされている頂点集合の部分集合の族 の組 のこと。これがマトロイドになるとはどういうことかは次回。