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

更新日時 2021/03/07

ベクトルの一次独立性の構造を抽象化したマトロイドについて解説します。離散最適化という分野の基本的な話題です。

非常に抽象的ですが「一次独立」の意味が分かる高校生ならご理解いただける内容かと思います。

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

まずは定義から!

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

マトロイドの定義

有限集合 EE とその部分集合族 F\mathcal{F} について,以下の三つの条件が成立するとき (E,F)(E,\mathcal{F}) のペアをマトロイドと言う。

  1. F\emptyset\in \mathcal{F}

  2. XYX\subseteq Y かつ YFY\in\mathcal{F} なら XFX\in\mathcal{F}

  3. X,YFX,Y\in \mathcal{F} かつ X<Y|X| <|Y| ならある eYXe\in Y\setminus X が存在して X+eFX+e\in \mathcal{F}

E={1,2,3}E=\{1,2,3\}F={,{1},{2},{3},{1,2},{1,3}}\mathcal{F}=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\}\}

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

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

マトロイドと行列

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

  • 台集合 EEAA の列のインデックスの集合。
  • XX に対応する列ベクトルたちが一次独立なら XXF\mathcal{F} のメンバーとする。空集合もメンバーとする。

マトロイドの例

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

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

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

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

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

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

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

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

グラフマトロイドや最適化についても書きたかったのですがスペースの都合上今回は省略させていただきました。