マトロイドとは - OR事典 Weblio辞書

Weblio 辞書 > 学問 > OR事典 > マトロイドの意味・解説

OR事典

マトロイド

概要

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

グラフ･ネットワーク：

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

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

ウィキペディア

マトロイド

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2011/09/09 20:47 UTC 版)

マトロイド(matroid)はある公理を満たす集合とそのべき集合の部分集合の組である。

脚注

[ヘルプ]

注釈

^ 記号の意味については「冪集合」「空集合」「集合間の関係を表す記号」「濃度 (数学)」「和集合」「差集合」を参照のこと
^ (R3),(R5),(R6)を満たす関数と(R1),(R2),(R4)を満たす関数は同値
^ Xの基でないことに注意
^ 概念は「多項式時間変換」に詳しい
^ 最良選択貪欲法を使うことによって(本質的には独立性オラクルを複数回使うことによって)基決定オラクルを作れるが、逆に基決定オラクルを多項式回使っても独立性オラクルを作れない

出典

^ D. Hausmann, B. Korte , T. A. Jenkyns (1980). “Worst case analysis of greedy type algorithms for independence systems”. Mathematical Programming Studies 12: pp.120-131.
^ Hassler Whitney (1935 7). “On the abstract properties of linear dependence” (pdf). American Journal of Mathematics 57: pp.509-533. 2011年3月19日閲覧。
^ T.A. Jenkyns (1976). “The Efficacy of the greedy Algorithm”. Proc. of 7th S-E. Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Winnipeg: pp.341-350.
^ Bernhard Korte; Dirk Hausmann (1978). “An Analysis of the greedy heuristic for independence systems”, in B. Alspach, P. Hell, D.J. Miller, eds.: Aogorithmic Aspects of Combinatorics; Annals of Discrete Mathematics 2. Amsterdam: North-Holland, pp.65-74.
^ R. Rado (1957). “Note on Independence Functions”. Proceedings of the London Mathematical Society 7: pp.300-320.
^ Jack Edmonds (1971). “Matroids and the greedy algorithm”. Mathematical Programming 1: pp.127-136.
^ Bernhard Korte; C.L. Monma (1979). “Some remarks on a classification of oracle-type algorithms”, in L. Collatz, G. Meinardus, W. Wetterling, eds.: Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen 2. Basel: Birkhäuser, pp. 195-215.
^ Richard M. Karp (1972). “Reducibility Among Combinatorial Problems”, in R. E. Miller and J. W. Thatcher eds: Complexity of Computer Computations. New York: Plenum, pp. 85-103.
^ D. Hausmann, B. Korte (1981). “Algorithmic versus axiomatic definitions of matroids”. Mathematical Programming Study 14: pp.98-111.
^ B. Korte; R. Schrader (1981). “On the existence of fast approximation schemes”, in O. Mangaserian, R.R. Meyer, S.M. Robinson, eds.: Nonlinear Programming. New York: Academic Press, pp. 415-437.
^ Oscar H. Ibarra, Chul E. Kim (1975 10). “Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems”. Journal of the ACM 22 (4): pp. 463-468. ISSN 0004-5411. doi:10.1145/321906.321909.
^ Sartaj K. Sahni (1976 1). “Algorithms for Scheduling Independent Tasks”. Journal of the ACM 23 (1): pp. 116-127. ISSN 0004-5411. doi:10.1145/321921.321934.
^ G.V. Gens (1979). “Computational complexity of approximation algorithms for combinatorial problems”, in J. Becvar, ed.: Mathematical Foundations of Computer Science. Berlin: Springer, pp. 292-300.
^ Eugene L. Lawler (1979). “Fast Approximation Algorithms for Knapsack Problems”. Mathematics of Operations Research 4: pp. 339-356. doi:10.1287/moor.4.4.339.
^ J. Edmonds (1970). “Submodular functions, matroids and certain polyhedra”, in R. Guy, H. Hanani, N. Sauer, J. Schonheim, eds.: Combinatorial Structures and Their Applications. New York: Gordon and Breach, pp.69-87.
^ A. Frank (1981). “A weighted matroid intersection algorithm”. Journal of Algorithms 2: pp.328-336.
^ Crispin Nash-Williams (1967). “An application of matroids to graph theory”, in P.Rosenstiehl, ed.: Theory of Graphs; proceedings of an international symposium in Rome 1966. New York: Gordon and Breach, pp.263-265.
^ M. Grötschel, L. Lovász, A. Schrijver (1981). “The ellipsoid method and its consequences in combinatorial optimization” (pdf). Combinatorica 1: pp.169-197. 2011年3月26日閲覧。
^ Alexander Schrijver (2000). “A combinatorial algorithm minimizing submodular functions in strongly polynomial time” (pdf). Journal of Combinatorial Theory, Series B 80 (2): pp. 346-355. 2011年3月26日閲覧。

[続きの解説]

「マトロイド」の続きの解説一覧

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

マトロイドに関係した商品

【送料無料】グラフ・ネットワ-ク・マトロイド楽天ブックス
【送料無料】スーパー戦隊シリーズ::天装戦隊ゴセイジャー Vol.11楽天ブックス
【送料無料】数理計画法楽天ブックス

>> 「マトロイド」を解説文に含む用語の一覧

>> 「マトロイド」を含む用語の索引

マトロイドのページへのリンク

マトロイドのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

1		TPP
2		ガナッシュ
3		面目を失う
4		再臨界
5		今井遥
6		あざとい
7		先負
8		四大陸
9		粉糖
10		.m4a

21		高階通憲
22		共益費
23		及第点
24		トリュフ
25		こざとへん
26		コシノジュンコ
27		未満
28		法人
29		門出
30		赤口

11		ベキサロテン
12		リツイート
13		コシノミチコ
14		SARAH (AV女優)
15		捗る
16		ほたえる
17		コシノヒロコ
18		アウターライズ地震
19		プラリネ
20		ホキ


	Copyright (C) 2012 （社）日本オペレーションズ・リサーチ学会 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の元に提供されております。

マトロイドとは？

OR事典

マトロイド

概要

詳説

ウィキペディア

マトロイド

注釈

出典