マトロイド

マトロイドとは

マトロイド（英: matroid）は、有限集合とその部分集合族の組であり、特定の公理を満たす数学的な構造です。これは、行列の線形独立性という概念を一般化したものであり、組合せ最適化問題を解く上で非常に重要な役割を果たします。

マトロイドの定義

有限集合 E とその部分集合族 F (⊆ 2^E) の組 (E, F) が、以下の3つの公理を満たすとき、(E, F) はマトロイドと呼ばれます。

(A1) 空集合は F に含まれる (∅ ∈ F).
(A2) F に含まれる集合 Y の任意の部分集合 X も F に含まれる (X ⊆ Y ∈ F ⇒ X ∈ F).
(A3) F に含まれる2つの集合 X, Y について、X の要素数が Y の要素数よりも多いとき、X の要素 x であって、Y に x を加えた集合が F に含まれるようなものが存在する (X, Y ∈ F, |X| > |Y| ⇒ ∃ x ∈ X \ Y s.t. Y ∪ {x} ∈ F).

(A1)と(A2)のみを満たす場合は、独立性システムと呼ばれます。また、(A1)と(A3)を満たす場合は、グリードイドと呼ばれます。

用語の定義

- 独立集合 (independent set): F の要素
- 従属集合 (dependent set): 2^E \ F の要素
- サーキット (circuit): 極小な従属集合
- 基 (base, basis): 極大な独立集合
- X の基: X ⊆ E における極大な独立集合

ランク（階数）関数

独立性システム (E, F) のランク（階数）関数 r: 2^E → R は、X ⊆ E に対して次のように定義されます。

r(X) := max{|Y| : Y ⊆ X, Y ∈ F}

マトロイドの場合、公理(A3)から、X のどの基の要素数も等しいので、ランク関数を X の基の要素数と定義することもできます。

例えば、E = {1, 2, 3}, F = {{}, {1}, {2}, {1, 2}} のマトロイドでは、r({1}) = 1, r({1, 2}) = 2, r({1, 2, 3}) = 2, r({1, 3}) = 1 となります。

独立性システム (E, F) のランク関数 r は、任意の X, Y ⊆ E と x, y ∈ E について、以下の性質を持ちます。

(R1) r(X) ≤ |X|
(R2) X ⊆ Y ⇒ r(X) ≤ r(Y)
(R3) r(∅) = 0

さらに、(E, F) がマトロイドならば、以下の性質も持ちます。

(R4) r(X ∪ Y) + r(X ∩ Y) ≤ r(X) + r(Y) (劣モジュラ性)
(R5) r(X) ≤ r(X ∪ {x}) ≤ r(X) + 1
(R6) r(X ∪ {x}) = r(X ∪ {y}) = r(X) ⇒ r(X ∪ {x, y}) = r(X)

特に(R4)の劣モジュラ性は、マトロイドの重要な性質です。

閉包関数

独立性システム (E, F) の閉包関数 σ: 2^E → 2^E は、X ⊆ E に対して次のように定義されます。

σ(X) := {y ∈ E : r(X ∪ {y}) = r(X)}

σ(X) を X の閉包と呼びます。マトロイド (E, F) の閉包関数 σ は、以下の性質を持ちます。

(L1) X ⊆ σ(X) (任意の X ⊆ E)
(L2) X ⊆ Y ⇒ σ(X) ⊆ σ(Y) (任意の X, Y ⊆ E)
(L3) σ(X) = σ(σ(X)) (任意の X ⊆ E)
(L4) y ∉ σ(X), y ∈ σ(X ∪ {x}) ⇒ x ∈ σ(X ∪ {y}) (任意の X, Y ⊆ E と x, y ∈ E)

ランク商

X に含まれる基の最小元数を下方ランク関数 ρ(X) とすると、ランク商 q(E, F) は次のように定義されます。

q(E, F) := min{ρ(X) / r(X) : X ⊆ E}

マトロイドでは q(E, F) = 1 です。独立性システムでは q(E, F) ≤ 1 であり、A ∈ F, b ∈ E に対して、A ∪ {b} が高々 p 個のサーキットしか持たないならば 1/p ≤ q(E, F) であることが知られています。

マトロイドの例

一様マトロイド

有限集合 E と整数 r が与えられたとき、E の部分集合で要素数が r 以下のものを F とすると、(E, F) はマトロイドになります。これを一様マトロイドと呼び、U_n^r などと書きます。基は要素数 r の部分集合、サーキットは要素数 r+1 の部分集合です。

一様マトロイドの直和は分割マトロイドと呼ばれます。互いに素な集合 B_1, ..., B_k と整数 0 ≤ d_i ≤ |B_i| が与えられたとき、|I ∩ B_i| ≤ d_i を満たす I ⊂ ∪_i B_i の集合を F とすれば、マトロイドになります。

グラフ理論におけるマトロイド

グラフの辺集合 E と、森の集合 F の組 (E, F) はマトロイドになり、グラフ的マトロイドまたは閉路マトロイドと呼ばれます。

グラフ G がグラフ的マトロイドであることは M(G) と書かれます。従属集合は閉路を持つグラフの集合、サーキットは単純閉路となる辺集合です。基は最大の森であり、階数関数は r(X) = (X がカバーする点数) - 1 です。

その他のグラフにおけるマトロイドとして、以下のようなものがあります。

- bicircularマトロイド: 辺集合 E と (G, X) がpseudoforestとなるようなXの集合 F
- 横断マトロイド: 2部グラフ G = (U, V, X) において、マッチングの端点となる点集合 S ⊆ U の集合 F。
- ガンモイド: 点集合 V のグラフにおいて、U への点素な |U| 本の道が存在する V' の部分集合を F の要素とする。特に(V, F) を狭義ガンモイドという。

線形代数におけるマトロイド

体上の行列の列集合 E と、線形独立な列の集合 F の組 (E, F) はマトロイドになり、ベクトルマトロイドと呼ばれます。マトロイドが同等の体 K 上のベクトルマトロイドとして記述できるとき、表現可能であると言います。任意の体上で表現可能なマトロイドを正則マトロイド、位数2の有限体上で表現可能なマトロイドを2値マトロイドと呼びます。

マトロイド ⊃ 2値マトロイド ⊃ 正則マトロイド ⊃ グラフ的マトロイドの包含関係が成り立ちます。Fanoマトロイドは2値マトロイドだが正則マトロイドではなく、Vámosマトロイドは任意の体上で表現できないマトロイドです。

その他のマトロイド

- 2部マトロイド: サーキットの大きさがすべて偶数であるマトロイド。
- シルベスターマトロイド: すべてのサーキットの大きさが3であるようなマトロイド。ランク2の一様マトロイド U_n^2 など。
- pavingマトロイド: すべてのサーキットの大きさがランクよりも大きいマトロイド。一様マトロイド U_n^r など。
- オイラーマトロイド: 要素がサーキットによって分割できるようなマトロイド。一様マトロイド U_n^r は r + 1 が n を割り切るときのみオイラーマトロイド。

マトロイドの他の公理系

マトロイドは、独立集合の族 F の他に、基族、サーキット族、ランク関数、閉包関数によっても定義できます。

基族による定義

有限集合 E と B ⊆ 2^E について、B がマトロイド (E, F) の基族であるための必要十分条件は、次の(B1), (B2) が成り立つことです。

(B1) B ≠ ∅
(B2) 任意の B', B'' ∈ B と x ∈ B' \ B'' について、(B' \ {x}) ∪ {y} ∈ B となる y ∈ B'' \ B' が存在する。

サーキット族による定義

有限集合 E と C ⊆ 2^E について、C がマトロイド (E, F) のサーキット族であるための必要十分条件は、次の(C1),(C2),(C3) が成り立つことです。

(C1) ∅ ∉ C
(C2) 任意の C1, C2 ∈ C について、C1 ⊆ C2 ならば C1 = C2
(C3) 任意の C1, C2 ∈ C (C1 ≠ C2) と c ∈ C1 ∩ C2 について、C3 ⊆ (C1 ∪ C2) \ {c} となる C3 ∈ C が存在する。

ランク関数による定義

E と (R1), (R2), (R4) を満たす関数 r: 2^E → Z_+ が与えられれば、F が一意に定まり、(E, F) はマトロイドとなり、r はランク関数になります。

閉包関数による定義

(L1)から(L4)を満たす関数 σ: 2^E → 2^E はマトロイドの閉包関数になります。

マトロイドの構成法

双対

独立性システム (E, F) に対して、F を X ∩ B = ∅ となる (E, F) の基 B が存在するような X ⊆ E の集合とすると、(E, F) を (E, F) の双対と定義します。

- (E, F*) = (E, F)
- (E, F) が独立性システムならば、(E, F) は独立性システム
- (E, F) がマトロイド ⇔ (E, F) がマトロイド

マトロイド (E, F) とその双対 (E, F) のランク関数をそれぞれ r, r とすると、r(X) = |X| + r(E \ X) - r(E) が成立します。

平面グラフの双対とグラフ的マトロイドの双対の概念は一致します。

交差

2つの独立性システム (E, F1), (E, F2) に対して、(E, F1 ∩ F2) を2つの独立性システムの交差と定義します。有限個の独立性システムの交差も独立性システムになります。

合併

2つのマトロイド (E, F1), (E, F2) に対して、X = X1 ∪ X2 (X1 ∈ F1, X2 ∈ F2) となる X ⊆ E の集合 F を (E, F1), (E, F2) の合併と呼びます。マトロイドの合併はマトロイドとなります。

k個のマトロイド (E, F1), …, (E, Fk) の各ランク関数を r1, …, rk とすると、これらの合併 (E, F) のランク関数は r(X) = min{ |X \ A| + Σ(i=1 to k) r_i(A) : A ⊆ X} となります。

組合せ最適化

多くの組合せ最適化問題は、独立性システム (E, F) とコスト関数 c: E → R に対して、Σ(e ∈ X) c(e) を最大（または最小）にする X ∈ F を求める問題として定式化できます。

貪欲法

マトロイドにおいては、貪欲法で最適解が得られます。

最良選択貪欲法

c(e) の大きい順に e ∈ E を暫定解に追加できる限り追加するアルゴリズムです。ランク商 q(E, F) を用いると、q(E, F) ≤ c(G) / c(OPT) ≤ 1 が成り立ちます。マトロイドのランク商は1なので、マトロイドの最大化問題は、最良選択貪欲法で最適解が得られます。

最悪棄却貪欲法

コスト関数に対する最小化問題を解くためのアルゴリズムです。都合の悪い e ∈ E を優先して解から除外していきます。

オラクル

組合せ最適化問題では、F は明示的に与えられることはなく、独立性オラクルが必要となります。独立性オラクルは、X ⊆ E が与えられたとき X ∈ F であるかどうかを判定するオラクルです。

マトロイドでは、独立性オラクル、基拡張集合オラクル、ランクオラクル、閉包オラクルは全て多項式等価ですが、独立性システムでは必ずしもそうではありません。

近似

最適化問題は厳密解を求めることが難しい場合も多いです。近似の限界について、効率的に解けることと、誤差が高々 1+ε 倍の解を出力する多項式時間アルゴリズムが存在することは同値であるという研究もあります。

マトロイドに関する問題

マトロイド交差問題

2つのマトロイド (E, F1), (E, F2) が与えられたとき、|F| が最大となるような F ∈ F1 ∩ F2 を求める問題です。多項式時間で解けます。3つ以上の場合はNP困難です。

マトロイド分割問題

k個のマトロイド (E, F1), …, (E, Fk) が与えられたとき、|X| が最大になるような分割可能な X ⊆ E を求める問題です。マトロイド交差問題と等価です。

一般化

グリードイド

マトロイドと反マトロイドを一般化したもので、特定の条件下で貪欲法により最適解を得ることができますが、NP困難な問題も存在します。

ポリマトロイド

マトロイドのランク関数が劣モジュラ関数であることを利用して、有界多面体を定義できます。ポリマトロイドとベクトルに対する分離問題は劣モジュラ関数最小化問題に帰着できます。

参考文献

- B.コルテ、J.フィーゲン著、浅野孝夫、平田富夫、小野孝男、浅野泰仁訳『組合せ最適化-理論とアルゴリズム』（第2版）シュプリンガー・ジャパン、2012年2月29日。

外部リンク

- 『マトロイドの定義と具体例』 - 高校数学の美しい物語

もう一度検索