分割マトロイド

左側に示す二部グラフでは、最初の列の各頂点に固有の色が割り当てられています。そして、各辺は、接続先の頂点の色に基づいて色付けされます。右側のマトロイドの各独立集合には、各色の辺が最大1つずつ存在できます。したがって、このマトロイドは、すべてのに対してかつとなる分割マトロイドです。後者の条件は、このマトロイドが横断マトロイドでもあることを意味します。${\displaystyle |C_{i}|=3}$ ${\displaystyle d_{i}=1}$ ${\displaystyle i}$

数学において、分割マトロイドまたは分割マトロイドとは、一様マトロイドの直和であるマトロイドのことである。^[1]これは、要素が異なるカテゴリに分割された基本集合上で定義される。各カテゴリには、そのカテゴリから許容される要素の最大数である容量制約がある。分割マトロイドの独立集合とは、各カテゴリにおいて、そのカテゴリからの要素の数がカテゴリ容量以下となる集合である。

正式な定義

を互いに素な集合（「カテゴリ」）の集合とする。を（「容量」）を持つ整数とする。任意の添字 に対して のとき、部分集合を「独立」であると定義する。この条件を満たす集合は、マトロイドの独立集合を形成し、分割マトロイドと呼ばれる。 ${\displaystyle C_{i}}$ ${\displaystyle d_{i}}$ ${\displaystyle 0\leq d_{i}\leq |C_{i}|}$ ${\displaystyle I\subseteq \bigcup _{i}C_{i}}$ ${\displaystyle i}$ ${\displaystyle |I\cap C_{i}|\leq d_{i}}$

これらの集合は、カテゴリまたは分割マトロイドの ブロックと呼ばれます。${\displaystyle C_{i}}$

分割マトロイドの基底とは、どのブロックとも交差する部分集合の大きさがちょうど である集合である。マトロイドの回路とは、単一のブロックの部分集合であり、そのサイズはちょうど である。マトロイドの階数はである。^[2]${\displaystyle C_{i}}$ ${\displaystyle d_{i}}$ ${\displaystyle C_{i}}$ ${\displaystyle d_{i}+1}$ ${\displaystyle \sum d_{i}}$

すべての一様マトロイド は、単一の要素ブロックを持ち、 となる分割マトロイドです。すべての分割マトロイドは、各ブロックごとに1つずつある一様マトロイドの集合の直和です。 ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle C_{1}}$ ${\displaystyle n}$ ${\displaystyle d_{1}=r}$

いくつかの文献では、分割マトロイドの概念はより限定的に定義され、すべての となる。このより限定的な定義に従う分割は、それらのブロックによって与えられる分離集合族の横断マトロイドである。 ^[3]${\displaystyle d_{i}=1}$

プロパティ

分割マトロイドの双対マトロイドも分割マトロイドであり、分割マトロイドのすべてのマイナーマトロイドも分割マトロイドです。分割マトロイドの直和も分割マトロイドです。

マッチング

グラフにおける最大マッチングとは、2つの辺が端点を共有しないという条件のもとで、可能な限り大きな辺の集合である。二分割グラフにおいて、2つの辺が端点を共有しないという条件を満たす辺の集合は、頂点ごとに1つのブロックを持ち、それぞれの数が1である分割マトロイドの独立集合である。2つの辺が端点を共有しないという条件を満たす辺の集合は、 2番目の分割マトロイドの独立集合である。したがって、2部最大マッチング問題は、これら2つのマトロイドのマトロイド交差として表すことができる。^[4]${\displaystyle (U,V)}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle d_{i}}$ ${\displaystyle V}$

より一般的には、グラフのマッチングは、グラフ内のすべての奇数サイクルが2つ以上の次数2の頂点を含む三角形である場合にのみ、2つのマトロイドの交差として表すことができます。^[5]

クリーク複合体

クリーク複合体とは、グラフの頂点集合の族で、グラフの完全部分グラフを誘導するものである。クリーク複合体がマトロイドを形成するのは、グラフが完全多部グラフである場合のみであり、この場合、結果として得られるマトロイドは分割マトロイドである。クリーク複合体は、任意の を満たす分割マトロイドの族の交差として形成される集合系そのものである。^[6]${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle d_{i}=1}$

列挙

ラベル付き要素の集合に対して定義できる異なる分割マトロイドの数は、 ${\displaystyle n}$ ${\displaystyle n=0,1,2,\dots }$

1、2、5、16、62、276、1377、7596、45789、298626、2090910、...（OEISのシーケンスA005387）。

この数列の指数生成関数はである。[ 7 ^]${\displaystyle f(x)=\exp(e^{x}(x-1)+2x+1)}$

参考文献

1. Recski, A. (1975)、「アプリケーションを使用した分割マトロイドについて」、無限集合と有限集合 (Colloq.、Keszthely、1973; 60 歳の誕生日に P. Erdős に捧げ)、Vol. III、コロク。数学。社会ヤノス・ボリャイ、vol. 10、アムステルダム: 北オランダ、  1169 ～ 1179 ページ、MR  0389630。
2. Lawler, Eugene L. (1976),組合せ最適化：ネットワークとマトロイド、Rinehart and Winston、ニューヨーク：Holt、p. 272、MR  0439106。
3. 例えば、柏原・岡本・宇野 (2007) を参照。Lawler (1976) はより広い定義を用いているが、この制限は多くの応用において有用であると指摘している。${\displaystyle d_{i}=1}$
4. パパディミトリウ、クリストス・H. ;シュタイグリッツ、ケネス(1982)、「組み合わせ最適化：アルゴリズムと複雑性」、エングルウッドクリフス、ニュージャージー：プレンティス・ホール社、pp.  289– 290、ISBN 0-13-152462-3、MR  0663728。
5. Fekete, Sándor P.; Firla, Robert T.; Spille, Bianca (2003)、「マッチングをマトロイドの交差として特徴付ける」、オペレーションズ・リサーチの数学的手法、58 (2): 319– 329、arXiv : math/0212235、doi :10.1007/s001860300301、MR  2015015。
6. 柏原健二;岡本 良夫宇野 武昭 (2007)、「クリーク複合体のマトロイド表現」、離散応用数学、155 (15): 1910–1929、doi : 10.1016/j.dam.2007.05.004、MR  2351976クリークの代わりに独立集合を用いた補完的な形での同じ結果については、Tyshkevich, RI ; Urbanovich, OP ; Zverovich, I. È. (1989)「グラフのマトロイド分解」『組合せ論とグラフ理論』（ワルシャワ、1987年） Banach Center Publ.、第25巻、ワルシャワ：PWN、pp.  195– 205、MR  1097648を参照。。
7. Recski, A. (1974)、「Enumeration Partitional Matroids」、Studia Scientiarum Mathematicarum Hungarica、9 : 247–249 (1975)、MR  0379248。