マトロイド（４）Transversal Matroid

二部グラフのマッチングマトロイドと対応がつく Transversal Matroid と言う概念がある（したがって一般のマッチングマトロイドよりも狭い概念）ので簡単に説明。

今までの例と違って、慣習的に元となる有限集合を とする。 の部分集合の族を とする。 の部分集合 が に部分横断的とは、

の部分族 との1対1対応 で を満たすものが存在する

ことを言う。すなわち、 の部分族 をうまくとれば、 に含まれる の部分集合の中から、 の要素をひとつずつ選ぶことができると言うこと。

このとき、 に部分横断的な部分集合の全体を とすると、 がマトロイドになる。

さて、これを二部グラフのマッチングマトロイドとみなす魔法は、次のとおり。

として、 として、 を頂点、 を辺とみなすと、二部グラフになる。このとき二部グラフのマッチングマトロイドは頂点集合の部分集合を規定するが、それを　 に制限したものを考えると、マッチングによってマッチされていることと、部分横断的なことが同値になる。