マトロイド

マトロイド（)は、ある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって多項式時間のアルゴリズムとは限らないものの最適解が得られることは非常に重要である。
定義.
有限集合 とその部分集合族 formula_1 の組 が
を満たすとき、マトロイドと呼ばれ、(A1) および (A2) のみを満たすとき独立性システム ("independence system") と呼ばれる。さらに (A1) および (A3) を満たすときグリードイド ("greedoid") と呼ばれる。
以下に本項で使う用語の定義を挙げる。
ランク、階数関数.
独立性システム (E, F) の階数 (rank) 関数 formula_10 は、formula_8 に対して 
と定義される。マトロイドならば、公理(A3) から の部分集合 に対して のどの基も元数は等しいため、階数関数をformula_7の基の大きさと定義しても構わない。
例えば、E = {1, 2, 3}, F= というマトロイドならば r({1}) = 1, r({1, 2}) = 2, r({1, 2, 3}) = 2, r({1, 3}) = 1 等となる。
独立性システム formula_14 の階数関数 formula_10 は任意の formula_16 と formula_17 について次の性質を持つ。
さらに、formula_14 がマトロイドならば次の性質も持つ。
特に(R4)に示されているように、階数関数が劣モジュラであることは、マトロイドの極めて重要な性質である。
閉包.
独立性システム formula_14 の閉包 (closure) 関数 formula_26 は、formula_8 に対して
で定義される。
formula_29 を の閉包と呼ぶ。
マトロイド formula_14 の閉包関数 formula_31 は次の性質を持つ。
ランク商.
下方ランク (lower rank) 関数 formula_41 を formula_7 に含まれる基の最小元数とする。つまり、
と定義する。すると、ランク商 (rank quotient) は次のように定義される。
マトロイドのとき formula_47 である。独立性システムのとき formula_48 であり、formula_49 に対して formula_50 が高々 個しかサーキットを持たないならば formula_51 であることが知られているのでランク商を見積もることが可能である。
例.
一様マトロイド.
E を有限集合とし、ある整数 r 以下の要素数を持つ 2 の部分集合をFとするとき、(E, F) はマトロイドとなる。これを、' ("uniform matroid") と呼び、n=|E|としたとき formula_52 などと書く。formula_52 における基は、要素数がrであるようなEの部分集合であり、サーキットは要素数がr+1であるようなEの部分集合である。また、一様マトロイドの直和は' ("partition matroid") と呼ばれる。具体的には、formula_54を互いに素な集合とし、それぞれに formula_55 を定めたとき、formula_56 それぞれにおいて formula_57 を満たす formula_58 の集合を F とすれば、マトロイドとなる。
グラフ理論におけるマトロイド.
E を無向グラフGの辺集合、F を森の集合とするとき、(E, F) はマトロイドとなり、 ("graphic matroid") または 閉路マトロイド ("cycle matroid") と呼ぶ。しばしばグラフGがグラフ的マトロイドであることを M(G) と書く。グラフ的マトロイドにおける従属集合は、閉路を持つグラフの集合であるから、サーキットとは単純閉路となる辺集合である。また（X の）基とは（X の部分集合の中で）できうる最大の森のことで、明らかに（X でカバーされる）点の数 − 1 本の辺で作られる森が最大であり、この森の集合を言う。よって、階数関数は r(X) = (Xがカバーする点数) − 1 と書ける。
他にも、グラフにおけるマトロイドはいくつか知られている。
線形代数におけるマトロイド.
E を体上の行列の列集合、その体上で線形独立である列の集合を F とするとき、(E, F) はマトロイドとなり、ベクトルマトロイド ("vector matroid") と呼ぶ。マトロイドが同等の体 K 上のベクトルマトロイドとして記述できるとき、表現可能であると呼ばれる。任意の体上で表現可能なマトロイドを正則マトロイド ("regular matroid") と呼び、位数2の有限体上で表現可能なマトロイドを ("binary matroid") と呼ぶ。これらは、
という包含関係が成り立つ。一方で、Fanoマトロイドは、2値マトロイドであるが（実数体上では表現できないため）正則マトロイドではない。また、 ("Vámos matroid") は、任意の体上で表現できないマトロイドの最も簡単な例である。
他の公理系.
集合Eとその部分集合の族Fが(A1)から(A3)を満たすときマトロイドと呼ぶことにし、そこから基やランクを定義した。だが、実はこれらの性質を持つ族あるいは関数からマトロイドとなる F を得ることができる。
基族.
有限集合 と formula_66 とする。
formula_67 がマトロイド (E, F) の基族であるための必要十分条件は次の(B1),(B2)が成り立つことである。
基が1つしかない場合は明らかにマトロイドとなる。そうでない場合、例えば formula_72 とすると formula_67 は(B1)および(B2)を満たす。このような基の族を持つマトロイドは、一様マトロイド formula_74 ただ1つに決まることが分かる。また、基族が formula_75 のときは(B2)を満たさないため、この基族ではマトロイドにならない。事実、formula_76 とすると、この例の基族となるが、(A3)を満たさずマトロイドになっていない。
サーキットの族.
有限集合 E と C ⊆ 2 とする。C がマトロイド (E, F) のサーキットの族であるための必要十分条件は次の(C1),(C2),(C3)が成り立つことである。
ランク関数.
マトロイドのランク関数は(R1)から(R6)を満たすが、逆にEと(R1),(R2),(R4)を満たす関数 formula_79 を与えればFは直ちに決まり (E, F) はマトロイドであり、r はランク関数である。
例えば、E = {1, 2, 3} とし、関数 r を
と定義すると、r は(R1),(R2),(R4)を満たすことが確認できる。すると、r(X) = |X| となる X の族を F と定義すると F = となり、(E, F) はマトロイドになることが確認できる。このように、r を決めれば対応する F がただ1つに決まる。
閉包関数.
(L1)から(L4)を満たす関数 formula_82 はマトロイドの閉包関数となる。
マトロイドの構成法.
ここでは、1つ以上のマトロイド（あるいは独立性システム）から新たなマトロイドを構成する方法について説明する。
双対.
独立性システム (E, F) に対して、F を formula_83 となる (E, F) の基 B が存在する formula_8 の集合とする。このとき、(E, F) を (E,F) の双対 ("dual") と定義する。
双対には次のような性質がある。
例えば、 E = {1, 2, 3}, F = というマトロイドに対して基の族 B = { {1, 2} } だから F = { {3} } となる。双対のランク関数も、例えば r({1, 3}) = 2 + r({2}) - r({1, 2, 3}) = 2 + 1 - 2 = 1 となるように、成り立っていることが分かる。
また、平面グラフに対する双対とグラフ的マトロイドの双対の概念は一致する。つまり、任意の平面的グラフ G の閉路マトロイド M(G) の双対は、G の双対平面グラフ G のマトロイドと（平面埋め込みの方法によらず）同一である。
交差.
2つの独立性システム (E, F), (E, F) とするとき、(E, F ∩ F) を2つの独立性システムの交差 ("intersection") と定義する。有限個の独立性システムの交差も同様に定義でき、交差もまた独立性システムとなる。任意の独立性システム (E, F) は、有限個のマトロイドの交差で表せる。さらに、p 個のマトロイドの交差ならば、q(E, F) ≧ 1/p。
例えば2部グラフのマッチング問題の場合、Eを辺集合、Fをマッチング集合とすれば、2部グラフであるから点集合は A ∪ B と書ける。F を任意の点 a ∈ A に繋がる辺は高々1本であるという条件とするならば (E, F) はマトロイドであり、同様に F を任意の点 b ∈ B に繋がる辺は高々1本であるという条件とするならば (E, F) もマトロイドである。F = F ∩ F なので、(E, F) は2つのマトロイド (E, F), (E, F) の交差である。
合併.
2つのマトロイド (E, F),(E, F) とする。X ∈ F, X ∈ F となる X の分割 X = X ∪ X が存在するとき、X ⊆ E は 分割可能 ("partitionable") であると呼ぶ。formula_87 とするとき、(E, F) を (E, F), (E, F) の合併("union") あるいは和("sum") と呼ぶ。有限個のマトロイドの合併も同様に定義できる。
組合せ最適化.
組合せ最適化問題の多くは、独立性システム formula_14 とコスト関数 formula_90 に対して、formula_91 を最大（あるいは最小）にする formula_92 を求める最適化問題に定式化できる。
例えば、以下の中で最小全域木問題はマトロイドになるが、他はマトロイドにはならず、独立性システムとなる。
貪欲法.
マトロイドにおいては貪欲法で最適解が得られることを示す。なお、マトロイドの貪欲法は組合せ最適化の貪欲法の全てを網羅しているわけではない。たとえば、クラスカル法はマトロイド上の貪欲法で説明できるが、プリム法やダイクストラ法は異なる。
最良選択貪欲法.
最良選択貪欲法は、formula_93 の大きい順に formula_94 を暫定解に追加できるならば追加し追加できない場合は次の要素に移ることを繰り返すアルゴリズムである。つまり、
というアルゴリズムである。
最良選択貪欲法で得られる解のコストを formula_101、最適解のコストを formula_102 とすると、ランク商 formula_103 を使って
が任意のコスト関数に対して成立する。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム (E, F) がマトロイドであるための必要十分条件は最良選択貪欲法で全ての formula_105 に対して最大化問題の最適解を求めることができることである。これを Edmonds-Rado 定理という。
証明の概要.
formula_106 の証明の概要を述べる。 
 を最良選択貪欲法で得られる解、formula_107 を最適解とする。formula_108 は、formula_95 となるようにソート済みであるとし、formula_110 とする。また、
とし、任意の formula_112 に対して、formula_113 と置く。このとき、次の事実が成り立つ。
以上のことから、
となる。
最悪棄却貪欲法.
独立性システム (E, F) とコスト関数 formula_123に対する最小化問題を解く。最悪棄却貪欲法は、都合の悪い e ∈ E を優先して解から除外する。つまり、
というアルゴリズムである。
最悪棄却貪欲法で得られる解のコストを c(G)、最適解のコストを c(OPT) とすると、ランク商 q(E, F)、双対な独立性システム (E, F) の下方ランク関数 ρ、ランク関数 r を使って
と書ける。マトロイドならば ρ = r なので、常に最適解を得られることが分かる。
オラクル.
組合せ最適化問題において F は明示的に与えられることはまずない。F を列挙しようとすることは無謀であるので、現実には E とコスト関数cのみが与えられる。最良選択貪欲法を実行するには、さらに独立性オラクルを必要となる。独立性オラクルとは、X ⊆ E が与えられたとき X ∈ F であるかどうかを判定するオラクルである。これがないと最良選択貪欲法の3番目のステップは実行できない。同様に最悪棄却貪欲法を実行するためには X ⊆ E が与えられたとき X が基を含むかを判定する基拡張集合オラクルを必要とする。
では、独立性オラクルか基拡張集合オラクルどちらか一方が与えられたとき、そのオラクルを使ってもう一方を多項式時間で実行可能(多項式等価)だろうか。例えば、巡回セールスマン問題に対する独立性システムの独立性オラクルはつまり、与えられた辺集合がハミルトン閉路の部分集合であるかを判定するものであるが、グラフは完全グラフであるので、多項式時間で実行可能である。対して基拡張集合オラクルは与えられた辺集合からいくらか辺を削除することによってハミルトン閉路になるかということを判定しなくてはならない。それはつまりハミルトン閉路問題と等価であり、ハミルトン閉路問題はNP完全であるため難しいと言える。このように、独立性システムにおいて独立性オラクルと基拡張集合オラクルは必ずしも多項式等価ではない。
マトロイドにおいては独立性オラクル、基拡張集合オラクル、ランク関数を返すランクオラクル、閉包関数を返す閉包オラクル全て多項式等価である。しかし、与えられた部分集合が基かどうかを判定する基決定オラクルは独立性オラクルより弱いし、与えられた部分集合の最小元数の従属部分集合を返すオラクルは独立性オラクルより強い。
近似.
最適化問題は厳密解を求めることが現実的でないことが多いために、近似の限界についても研究されている。次の問題が効率的に解ける（入力のサイズと 1/ε の多項式時間で解を出力するアルゴリズムが存在する）ことと、誤差が高々 1+ε 倍の解を出力する多項式時間アルゴリズムが存在することは同値である。
独立性システム (E, F)、コスト関数 formula_131、部分集合 S, S' ⊆ E, ε > 0 が
であるとき、S ⊆ B となる基 B が存在して S' ⊆ B' となる基 B' 全てに対して (1 + ε)c(B) ≧ c(B') が成立するか？
つまり、部分的なコスト（c(S) や c(S')）が高々 1 + ε 倍違う程度ならば、それらからできうる最適解も 1 + ε 倍程度しか違わないだろうか、という問題である。部分が最適ならば全体も最適であるという場合はε=0であり、よく知られているように動的計画法が存在する。よって、(E, F) をマトロイドに限定するならば多項式時間アルゴリズムは存在する。
ナップサック問題はこのアルゴリズムが知られている珍しい例で、計算時間が formula_133や formula_134で、出力される解の評価が最適解の評価の高々 1 + ε 倍であるアルゴリズムがある。
マトロイドに関する問題.
マトロイド交差問題と分割問題.
マトロイド交差問題 ("Matroid Intersection Problem") は、2つのマトロイド (E, F), (E, F) が与えられたとき、|F| が最大となるような F ∈ F ∩ F を求める問題である。マトロイド交差問題は多項式時間で解ける。また、3つ以上のマトロイド交差問題も同様に考えることができるが、これはNP困難問題である。
重み付き版についてもアルゴリズムが知られていて、2つの独立性オラクルの計算量の大きい方を α とすると O(|E|α) で解ける。
マトロイド分割問題 ("Matroid Partitioning Problem") は k 個のマトロイド (E, F), …, (E, F) が与えられたとき |X| が最大になるような分割可能な X ⊆ E を求める問題である。マトロイド交差問題とマトロイド分割問題は等価である。
一般化.
グリードイドはマトロイドと反マトロイドを一般化したものである。グリードイドにも貪欲法が定式化できて、特殊な条件下においては最適解を出力する。だが、グリードイド上での最適化問題はNP困難であることが知られている。
また、マトロイドのランク関数が劣モジュラ関数であることは既に述べたが、有限集合Eと劣モジュラ関数 formula_135を用いてポリマトロイド (polymatroid) と呼ばれる有界多面体を定義できる。ポリマトロイドとベクトルに対する分離問題は劣モジュラ関数最小化問題に帰着できる。劣モジュラ関数最小化問題は例えばフローネットワークにおける無向グラフの最小カットを求める問題などを一般化している。劣モジュラ関数最小化問題は楕円体法を用いることで多項式時間で解けることが知られて以来、Schrijverのアルゴリズム等が知られている。