まとろいどとは何？わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキングカテゴリー

マトロイド

読み方：まとろいど
【英】：matroid

　マトロイド (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}\,$ となる.

$- \; 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] 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.