Matroidとは何？わかりやすく解説 Weblio辞書

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

マトロイド

概要

マトロイドとは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を満たすものである． 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.

「OR事典」の他の用語

グラフ･ネットワーク：

ポリマトロイドマッチングマッチング問題マトロイドユークリッド巡回セールスマン問題付値マトロイド共通マトロイド問題

ウィキペディア

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

マトロイド

(Matroid から転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/13 10:20 UTC 版)

マトロイド（英: matroid）は、ある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって多項式時間のアルゴリズムとは限らないものの最適解が得られることは非常に重要である。

定義

E = {1, 2, 3} におけるそれぞれの例。左は(A1),(A2),(A3)を満たすからマトロイド。中央は(A1),(A2)を満たすから独立性システム。右は(A1),(A3)を満たすからグリードイド。

有限集合 $E$ とその部分集合族 $F\subseteq 2^{E}$

Vámosマトロイドは、網掛け四角の4頂点をサーキット(計5つ)とするマトロイドである。

E を体上の行列の列集合、その体上で線形独立である列の集合を F とするとき、(E, F) はマトロイドとなり、ベクトルマトロイド (vector matroid) と呼ぶ。マトロイドが同等の体 K 上のベクトルマトロイドとして記述できるとき、表現可能であると呼ばれる。任意の体上で表現可能なマトロイドを正則マトロイド (regular matroid) と呼び、位数2の有限体上で表現可能なマトロイドを2値マトロイド（英語版） (binary matroid) と呼ぶ。これらは、

マトロイド ⊃ 2値マトロイド ⊃ 正則マトロイド ⊃ グラフ的マトロイド

という包含関係が成り立つ。一方で、Fanoマトロイドは、2値マトロイドであるが（実数体上では表現できないため）正則マトロイドではない。また、Vámosマトロイド（英語版） (Vámos matroid) は、任意の体上で表現できないマトロイドの最も簡単な例である。

その他のマトロイド

2部マトロイド (bipartite matroid) は、サーキットの大きさがすべて偶数であるマトロイドである。2部グラフのグラフ的マトロイドを一般化しており、グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である。
シルベスターマトロイド（英語版） (Sylvester matroid) は、すべてのサーキットの大きさが3であるようなマトロイドである。例えば、ランク2の一様マトロイド $U_{n}^{2}$
- イスラエル
- アメリカ

>> 「Matroid」を含む用語の索引
Matroidのページへのリンク

Matroidとは？わかりやすく解説

マトロイド

概要

詳説

マトロイド

定義

その他のマトロイド

「Matroid」の関連用語


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのマトロイド (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

Matroidとは？ わかりやすく解説

マトロイド

概要

詳説

マトロイド

定義

その他のマトロイド

「Matroid」の関連用語

Matroidとは？わかりやすく解説