マトロイドの定義と具体例

まずはマトロイドの定義です。

定義だけではわかりにくいので，例を見てみましょう。

• $\mathcal{F}$ は $E$ の部分集合たちの集合です。
• 公理1は「空集合はメンバーにいれる」というルールです。
• 公理2は「包含の意味で大きいものがメンバーなら小さいやつもメンバー」というルールです。例えば「$\{1,2\}$ がメンバーなら $\{1\}$ も $\{2\}$ もメンバー」です。上記の例では確かにそのようになっています。
• 公理3がマトロイドの重要な部分です。「要素数の異なる2つのメンバーに対して，大きい方の元 $e$ をうまく選べば，それを小さい方に加えたものもメンバーとなる」というルールです。上記の例では例えば $X=\{2\}$，$Y=\{1,3\}$ とすると，$e$ として $1$ が取ってこれて，$X+e=\{1,2\}$ もメンバーになっています。

定義の補足

• 有限集合 $E$ は台集合と呼ばれます。
• $E$ の部分集合族 $\mathcal{F}$ は独立集合族と呼ばれます。
• マトロイドには同値な定義がいくつもあります。ここでは独立集合族による定義を紹介しましたが，他にも基族による定義，階数による定義，サーキットによる定義などもあります。

行列 $A$ が与えられたときに以下のようにしてマトロイドが構成できます。

例えば，$A$ として図のような行列を考えると，$A$ の列数は $3$ なので $E=\{1,2,3\}$ となります。

また，列ベクトルたちが一次独立な集合たちを集めると，$\mathcal{F}=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\}\}$ となります。

（一列目と二列目は一次独立だが，二列目と三列目は一次独立でないので $\{2,3\}$ は独立集合でない）

これは最初の例で紹介したマトロイドです。このように，行列から構成されるマトロイドを行列マトロイド（線形マトロイド，ベクトルマトロイド）と言います。

なお，任意の行列に対して上記のように構成した $(E,\mathcal{F})$ がマトロイドになることは線形代数の知識で簡単に確認できます。

• 線形マトロイド，グラフマトロイド，マッチングマトロイド，一様マトロイドなど，いろいろなところに登場します。ベクトルの一次独立性を抽象化した概念ですが，線形マトロイド以外にもたくさんのマトロイドがあります。

• マトロイドは要素数最大化，線形関数最大化がしやすいです（貪欲アルゴリズムが成功する）。 →離散最適化において扱いやすい構造。