マトロイド
マトロイド("matroid")はある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって多項式時間のアルゴリズムとは限らないものの最適解が得られることは非常に重要である。
有限集合 formula_1 とその部分集合族 formula_2 の組 formula_3 が
を満たすとき、マトロイドと呼ばれ、(A1) 及び (A2) のみを満たすとき独立性システム("independence system")と呼ばれる。さらに (A1) 及び (A3) を満たすときグリードイド("greedoid")と呼ばれる。
以下に本項で使う用語の定義を挙げる。
マトロイド及び独立性システムの定義を与えたが、ひどく抽象的で理解しづらいかもしれない。ここでは具体的なモデルとしてグラフで考えよう。Eを辺の集合とする。Fは辺の任意の組合せの中で(A2)の条件を満たすものでなくてはならない。そのために「Fは森集合」や「Fはハミルトン閉路の部分集合」という条件を与える。これらはいずれも(A2)を満たす。なぜならば、森から辺を取り去っても森であるし、ハミルトン閉路の部分集合から辺を取り去ってもハミルトン閉路の部分集合だからである。しかし「Fはハミルトン閉路の部分集合」という条件では図に示すように(A3)を満たさない。対して「Fは森集合」は(A3)を満たすから、Eをグラフの辺集合、Fを森集合とする組(E,F)はマトロイドであるということが言える。
Fを森集合とした場合、従属集合は閉路を持つグラフの集合であるから、サーキットとは単純閉路となっている辺集合である。また(Xの)基とは(Xの部分集合の中で)できうる最大の森のことで、明らかに(Xでカバーされる)点の数-1本の辺で作られる森が最大であり、この森の集合を言う。
Eをグラフの辺集合、Fを森集合とする(E,F)はマトロイドになることは上述したが、それも含めて次のような場合もマトロイドになって特別に名前が与えられている。独立性システム (E,F) の階数 (rank) 関数 formula_12 は、X⊆Eに対して 
と定義される。グラフで考えれば F が森集合ならば、X から作れる最大の森の辺数であるから、カバーしている点の個数に依存するので |Y| はどんな Y⊆X,Y∈F についても一定である。この事実は(A3)からも明らかであり、一般にマトロイドの場合はEの部分集合Xに対してXのどの基も元数は等しい。つまり、マトロイドならば階数関数をr(X)={|Y|:Y⊆X,Y∈F}としても構わない。
独立性システム formula_14 の階数関数 formula_12 は任意のX,Y⊆Eとx,y∈Eについて次の性質を持つ。
さらに、formula_14 がマトロイドならば次の性質も持つ。
特に(R4)に示されているように階数関数が劣モジュラであることはマトロイドの極めて重要な性質である。
いくつかの例を挙げよう。前述した通り閉路マトロイドにおいてXの基の元数はXがカバーする点の数より1小さいからr(X)=(Xがカバーする点数)-1と書ける。また、E={1,2,3},F=というマトロイドならばr({1})=1,r({1,2})=2,r({1,2,3})=2,r({1,3})=1等となる。
独立性システム formula_23 の閉包 (closure) 関数 formula_24 は、 formula_25 に対して
で定義される。
formula_27 を formula_9 の閉包と呼ぶ。
マトロイド formula_23 の閉包関数 formula_30 は次の性質を持つ。
下方ランク (lower rank) 関数 formula_40 を formula_9 に含まれる基の最小元数とする。つまり、
と定義する。すると、ランク商 (rank quotient) は次のように定義される。
マトロイドのとき formula_46 である。独立性システムのとき formula_47 であり、 formula_48 に対してformula_49 が高々formula_50 個しかサーキットを持たないならば formula_51 であることが知られているのでランク商を見積もることが可能である。
これにより、Eを辺集合、Fをマッチンググラフ集合とすると、q(E,F)≧1/2が得られる。これは、適当な辺を追加してできるのは高々長さ3のパスであるから、サーキットは2個しかできないのである。しかし、Eを点集合、Fを安定集合とするとq(E,F)はいくらでも小さくなる。なぜならば、スターグラフ(ネットワーク構成のスター型のようなグラフ)において、周囲の点を選べばそれは安定集合となるので、b∈Eとして中心の点を与えればサーキットは周囲の点の個数個になり、周囲の点数を無限に増やすことによってサーキットをいくらでも多くできるからである。また、マトロイドの場合q(E,F)=1であるので、任意のb∈Eを加えてもサーキットは高々1個しか持たない。例えば、Eを辺集合、Fを森集合とすると、森にどんな辺を加えても閉路は高々1個しか作れない。
集合Eとその部分集合の族Fが(A1)から(A3)を満たすときマトロイドと呼ぶことにし、そこから基やランクを定義した。だが、実はこれらの性質を持つ族あるいは関数からマトロイドとなるようなFを得ることができる。
有限集合 formula_1 と formula_53 とする。
formula_54 がマトロイド (E,F) の基族であるための必要十分条件は次の(B1),(B2)が成り立つことである。
基が1つしかない場合は明らかにマトロイドとなる。そうでない場合、例えば formula_59, formula_60 とすると formula_54 は(B1)及び(B2)を満たす。このような基の族を持つマトロイドはk=2であるような一様マトロイドただ１つに決まることが分かる。また、基族が formula_62のときは(B2)を満たさない。よって、この基族ではマトロイドにならない。事実、 formula_63 は先の基の族になるが、(A3)を満たさずマトロイドになっていない。
有限集合 E と C⊆2 とする。C がマトロイド (E,F) のサーキットの族であるための必要十分条件は次の(C1),(C2),(C3)が成り立つことである。マトロイドのランク関数は(R1)から(R6)を満たすが、逆にEと(R1),(R2),(R4)を満たす関数formula_66を与えれば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_69 はマトロイドの閉包関数となる。
独立性システム (E,F) の双対 (dual) は (E,F) である。ただし F の要素 f は E の部分集合であって、formula_70 となる (E,F) の基 b が存在する。 (E,F)=(E,F) であり、 (E,F) がマトロイドであることと (E,F) はマトロイドであることは等価である。マトロイド(E,F)とその双対(E,F)とし、それぞれのランク関数をr,rとすると、rは任意のX⊆Eに対して
である。
例えば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 のマトロイドと(平面埋め込みの方法によらず)同一である。
組合せ最適化問題は独立性システム formula_14 とコスト関数 formula_73 を与えられたとき formula_74 を最大にする formula_75 を求める最大化問題か、最小にする基を求める最小化問題に定式化できる。なお、コスト関数の符号を反転することによって、最小化問題から最大化問題あるいはその逆にできる。
例えば、以下の中で最小全域木問題はマトロイドになるが、他はマトロイドにはならず、独立性システムとなる。
2つの貪欲法を示し、マトロイドにおいてはこの2つに対しては最適解が得られることを示す。なお、この2つは貪欲法の全てを網羅しているわけではなく、クラスカル法はここの枠組みで説明できるが、プリム法やダイクストラ法は、ここの枠組みでは扱えない。
独立性システム formula_14 とコスト関数 formula_77 に対する最大化問題を解く。最良選択貪欲法は、formula_78 が最大である formula_79 から答えとなる集合 formula_80 に入れる。つまり、
というアルゴリズムである。
最良選択貪欲法で得られる解のコストを formula_88 、最適解のコストを formula_89 とすると、ランク商 formula_90 を使って
が任意のコスト関数に対して成立する。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム(E,F)がマトロイドであるための必要十分条件は最良選択貪欲法で全てのformula_92に対して最大化問題の最適解を求めることができることである。これを Edmonds-Rado 定理という。
次に独立性システム (E,F) とコスト関数 formula_93に対する最小化問題を解こう。最悪棄却貪欲法は、都合の悪い e∈E から解から除外する。つまり、
というアルゴリズムである。
最悪棄却貪欲法で得られる解のコストを G 、最適解のコストを 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_97、部分集合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_99やformula_100で、出力される解の評価が最適解の評価の高々(1+ε)倍であるアルゴリズムがある。
今までは具体的な問題を独立性システムやマトロイドに一般化して様々な定理を得てきたが、ここでは独立性システム間に関する様々な考察を取り上げる。
2つの独立性システム(E,F),(E,F')とするとき、(E,F∩F')を2つの独立性システムの交差(intersection)と呼ぶ。任意の独立性システム(E,F)はp個のマトロイドの交差で表せ、ランク商q(E,F)≧1/pであるので、最良選択貪欲法での解を見積もることができる。専ら興味が持たれるのは2つのマトロイドの交差である。例えば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)のランク関数をそれぞれr,rとすると、
となる。マトロイド交差問題は多項式時間で解けるが、3つのマトロイドを考えるとそれはNP困難問題である。
重み付き版についてもアルゴリズムが知られていて、2つの独立性オラクルの計算量の大きい方をαとするとO(|E|α)で解ける。
k個のマトロイド(E,F)...,(E,F)についてX⊆EはX=X∪…∪XとなるようなX∈F(i=1...,k)が存在するとき、分割可能(partitionable)と呼ぶ。また、Fが分割可能ならば(E,F)は(E,F)...,(E,F)の合併(union)あるいは和(sum)と呼ばれる。
マトロイドの交差は、必ずしもマトロイドにはならなかったが、マトロイドの合併はマトロイドになる。k個のマトロイド(E,F)...,(E,F)の各ランク関数をr...,rとすると、これらの合併(E,F)のランク関数は
である。
次の問題とマトロイド交差問題は等価である。グリードイドはマトロイドと反マトロイドを一般化したものである。グリードイドにも貪欲法が定式化できて、特殊な条件下においては最適解を出力する。だが、グリードイド上での最適化問題はNP困難であることが知られている。
また、マトロイドのランク関数が劣モジュラ関数であることは既に述べたが、有限集合Eと劣モジュラ関数formula_103を用いてポリマトロイド(polymatroid)と呼ばれる有界多面体を定義できる。ポリマトロイドとベクトルに対する分離問題は劣モジュラ関数最小化問題に帰着できる。劣モジュラ関数最小化問題は例えばフローネットワークにおける無向グラフの最小カットを求める問題などを一般化している。劣モジュラ関数最小化問題は楕円体法を用いることで多項式時間で解けることが知られて以来、Schrijverのアルゴリズム等が知られている。