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

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

まずは定義から！

注：基族による定義，階数などによる同値な定義もありますが，ここでは独立集合族による定義を紹介します。

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

上記の例では例えば $X=\{2\}$，$Y=\{1,3\}$ とすると，$e$ として $1$ が取ってこれて，$X+e=\{1,2\}$ もメンバーになっています。

マトロイドと行列

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

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

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

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

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

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

マトロイドがなぜ嬉しいのか

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

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