マトロイド

【まとろいど (matroid)】

概要

マトロイドとは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を満たすものである． 1935年にホイットニー(H. Whitney)が導入し，1950年代以降タット(W. T. Tutte)らにより研究が発展してきた． 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.

詳説

　マトロイド (matroid) は, 線型空間内のベクトル集合の一次独立・従属といった概念の組合せ論的な側面を抽象化して得られる公理系を満たすものとして定義されている. 有限集合 $N\,$ とその部分集合族 ${\mathcal {I}}\,$ が以下の (I0)-(I2) を満たすとき, $(N,{\mathcal {I}})\,$ はマトロイドと呼ばれる.

$\mathbf {(I0)} \quad \emptyset \in {\mathcal {I}}.,$

$\mathbf {(I1)} \quad I\subseteq J\in {\mathcal {I}}\Rightarrow I\in {\mathcal {I}}.\,$

$\mathbf {(I2)} \quad I,J\in {\mathcal {I}},|I|<|J|\Rightarrow \exists j\in J\setminus I:I\cup \{j\}\in {\mathcal {I}}.\,$

マトロイド $\mathbf {M} =(N,{\mathcal {I}})\,$ において, $N\,$ を $\mathbf {M} \,$ の台集合, ${\mathcal {I}}\,$ を独立集合族 (independent set family) という.部分集合 $I\in {\mathcal {I}}\,$ は, $\mathbf {M} \,$ の独立集合と呼ばれる.

　マトロイド $\mathbf {M} \,$ の基とは, 極大な独立集合のことである. 公理 (I2) から明らかなように, 基の要素数は全て等しい. この数をマトロイド $\mathbf {M} \,$ の階数という. 基の全体を${\mathcal {B}}\,$ と書き, $\mathbf {M} \,$ の基族 (base family) と呼ぶ. 基族 ${\mathcal {B}}\,$ は以下の (B0)-(B1) を満たす.

$\mathbf {(B0)} \quad {\mathcal {B}}\neq \emptyset .\,$

$\mathbf {(B1)} \quad B,F\in {\mathcal {B}},i\in B\setminus F\Rightarrow \exists j\in F\setminus B:(B\setminus \{i\})\cup \{j\}\in {\mathcal {B}}.\,$

　マトロイド $\mathbf {M} \,$ の階数関数 (rank function) $\rho \,$ は,

$\rho (X)=\max\{|I|\mid I\subseteq X,\,I\in {\mathcal {I}}\}\quad \quad \quad (X\subseteq N)\,$

と定義される. 階数関数 $\rho \,$ は以下の (R0)-(R3) を満たしている.

$\mathbf {(R0)} \quad \rho (\emptyset )=0\,$.

$\mathbf {(R1)} \quad \forall X\subseteq N:\rho (X)\leq |X|\,$.

$\mathbf {(R2)} \quad X\subseteq Y\Rightarrow \rho (X)\leq \rho (Y)\,$.

$\mathbf {(R3)} \quad \forall X,Y\subseteq N:\rho (X)+\rho (Y)\geq \rho (X\cap Y)+\rho (X\cup Y)\,$.

特に, (R3) は $\rho \,$ が劣モジュラ関数 (submodular function) であることを示している.

　ここでは, (I0)-(I2) によってマトロイドを定義したが, (B0)-(B1) を満たす基族 ${\mathcal {B}}\,$ からマトロイドを定義することもできる. この場合, 独立集合は基の部分集合として定義される. 同様に, (R0)-(R3) を満たす階数関数によってマトロイドを定義することもできる. この場合, 独立集合族は ${\mathcal {I}}=\{I\subseteq N\mid \rho (I)=|I|\}\,$ によって定められる.

　離散最適化に現れるマトロイドの代表的な例を以下に挙げる.

グラフ的マトロイド　(graphic matroid) 点集合 $V\,$, 枝集合 $E\,$ を持つ無向グラフ $G=(V,E)\,$ を考える. 枝集合の部分集合のうち, 閉路を含まないものの全体を ${\mathcal {I}}\,$ とすると, $(E,{\mathcal {I}})\,$ は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイドをグラフ的マトロイドと呼ぶ.

横断マトロイド　(transversal matroid) 点集合 $U\,$, $V\,$, 枝集合 $E\,$ からなる2部グラフ $H=(U,V;E)\,$ を考える. 枝部分集合 $M\subseteq E\,$ で端点を共有しないものを $H\,$ のマッチングという. 点集合 $U\,$ の部分集合で, $H\,$ のマッチングの $U\,$ における端点集合となり得るものの全体を ${\mathcal {I}}\,$ とする. このとき, $(U,{\mathcal {I}})\,$ は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイド $(U,{\mathcal {I}})\,$ を横断マトロイドと呼ぶ.

　マトロイド $\mathbf {M} =(N,{\mathcal {I}})\,$ の各要素 $i\in N\,$ に重み $w(i)\,$ が与えられたとき, 以下の様な貪欲アルゴリズム　(greedy algorithm)　を適用して最終的に得られる $I\,$ が, 重み最小の基, すなわち, $\textstyle w(B)=\sum \{w(i)\mid i\in B\}\,$ を最小にする基 $B\in {\mathcal {B}}\,$ となる.

• $I\leftarrow \emptyset ;S\leftarrow N;\,$

• $S=\emptyset \,$ となるまで, 以下を繰り返す.

$-\;S\,$ の中で, 重み最小の要素を $j\,$ とする; $S\leftarrow S-\{j\};\,$

$-\,$もし $I\cup \{j\}\in {\mathcal {I}}\,$ であれば, $I\leftarrow I\cup \{j\}.\,$

全く同様のアルゴリズムによって, 重み最大の基を求めることもできる．

　離散最適化におけるマトロイドの重要性は, 貪欲アルゴリズムのみならず, 共通マトロイド問題 (matroid intersection problem)　に負うところが大きい. 共通マトロイド問題とは, 台集合を共有するマトロイド $\mathbf {M} ^{+}=(N,{\mathcal {I}}^{+})\,$ と $\mathbf {M} ^{-}=(N,{\mathcal {I}}^{-})\,$ における共通独立集合のうちで, 要素数最大のものを求める問題である. この問題の最適値は, $\mathbf {M} ^{+}\,$ の階数関数 $\rho ^{+}\,$ と $\mathbf {M} ^{-}\,$ の階数関数 $\rho ^{-}\,$ を用いて,

$\max\{|I|\mid I\in {\mathcal {I}}^{+}\cap {\mathcal {I}}^{-}\}=\min\{\rho ^{+}(X)+\rho ^{-}(N\setminus X)\mid X\subseteq N\}\,$

と特徴付けられる [1] . 共通マトロイド問題は, 回路理論やシステム解析においても本質的な役割を果たしている [2, 3, 5] .

　マトロイドが, 行列における一次独立性を抽象化して得られたのに対し, 対称行列や歪対称行列の正則主小行列の組合せ的な性質を抽象化した概念として，デルタマトロイド (delta-matroid) が提案された. デルタマトロイドは, マトロイドの一般化であり, 貪欲アルゴリズムが適用可能であると同時に, 一般グラフ上のマッチングの端点集合族をも包含する枠組として注目されている.

　また, 多項式行列の小行列式の次数の抽象化として付値マトロイド (valuated matroid) が提案された. 付値マトロイドの研究は, 劣モジュラ関数の凸性に関する理論と結び付いて, 離散凸解析と呼ばれる分野に発展している.

---

参考文献

[1] J. Edmonds, "Submodular functions, matroids, and certain polyhedra," in Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, 69-87, 1970.

[2] 室田一雄, 「マトロイドとシステム解析」, 藤重悟 編『離散構造とアルゴリズムⅠ』, 近代科学社, 第2章，57-109, 1992.

[3] K. Murota, Matrices and Matroids for Systems Analysis, Springer-Verlag, 2000.

[4] J. G. Oxley, Matroid Theory, Oxford University Press, 1992.

[5] A. Recski, Matroid Theory and Its Applications in Electric Network Theory and in Statics, Springer-Verlag, 1989.

[6] D. J. A. Welsh, Matroid Theory, Academic Press, 1976.

[7] N.White (ed.) , Matroid Applications, Cambridge University Press, 1992.

[8] 伊理正夫, 藤重悟, 大山達雄,『グラフ・ネットワーク・マトロイド』, 産業図書, 1986.

[9] J. Lee, A First Course in Combinatorial Optimization, Cambridge University Press, 2004.