「《マトロイド》」の版間の差分
| 1行目: | 1行目: | ||
'''【まとろいど (matroid) 】''' | '''【まとろいど (matroid) 】''' | ||
| − | [[マトロイド]] (matroid) は, 線型空間内のベクトル集合の一次独立・従属といった概念の組合せ論的な側面を抽象化して得られる公理系を満たすものとして定義されている. 有限集合 $N$ とその部分集合族 $\I$ が以下の (I0)-(I2) を満たすとき, $(N,\I)$ はマトロイドと呼ばれる. | + | [[マトロイド]] (matroid) は, 線型空間内のベクトル集合の一次独立・従属といった概念の組合せ論的な側面を抽象化して得られる公理系を満たすものとして定義されている. 有限集合 $<math>N</math>$ とその部分集合族 $<math>\I</math>$ が以下の (I0)-(I2) を満たすとき, $<math>(N,\mathcal I)</math>$ はマトロイドと呼ばれる. |
| − | + | '''(I0)''' $<math>\emptyset\in\I</math>$. | |
| − | |||
| − | |||
| + | '''(I1)''' $<math>I\subseteq J\in\I\Rightarrow I\in\I</math>$. | ||
| − | + | '''(I2)''' $<math>I,J\in\I$, $|I|<|J|\Rightarrow\exists j\in J\del I$: $I\cup\{j\}\in\I</math>$. | |
| − | |||
| − | \ | + | マトロイド $<math>\M=(N,\I)</math>$ において, $<math>N</math>$ を $<math>\M</math>$ の台集合, $<math>\I</math>$ を[[独立集合族]] (independent set family) という.部分集合 <math>$I\in\I</math>$ は, $<math>\M$</math> の独立集合と呼ばれる. |
| − | |||
| − | マトロイド $\M$ の[[ | + | マトロイド $<math>\M</math>$ の基とは, 極大な独立集合のことである. 公理 (I2) から明らかなように, 基の要素数は全て等しい. この数をマトロイド $<math>\M</math>$ の階数という. 基の全体を$<math>\B</math>$ と書き, $<math>\M</math>$ の[[基族]] (base family) と呼ぶ. 基族 $<math>\B</math>$ は以下の (B0)-(B1) を満たす. |
| − | + | '''(B0)''' $<math>\B\neq\emptyset</math>$. | |
| − | |||
| + | '''(B1)''' $<math>B,F\in\B$, $i\in B\del F\Rightarrow\exists j\in F\del B$: $(B\del\{i\})\cup\{j\}\in\B</math>$. | ||
| − | |||
| + | マトロイド $<math>\M</math>$ の[[階数関数]] (rank function) $<math>\rho</math>$ は, | ||
| − | |||
| − | |||
| − | |||
| − | |||
| + | :<math>\rho(X)=\max\{|I|\mid I\subseteq X,\, I \in\I\} | ||
| + | \quad\quad\quad(X\subseteq N)</math> | ||
| − | |||
| − | ここでは, (I0)-(I2) によってマトロイドを定義したが, (B0)-(B1) を満たす基族 $\B$ からマトロイドを定義することもできる. この場合, 独立集合は基の部分集合として定義される. 同様に, (R0)-(R3) を満たす階数関数によってマトロイドを定義することもできる. この場合, 独立集合族は $\I=\{I\mid \rho(I)=|I|\}$ によって定められる. | + | と定義される. 階数関数 $<math>\rho</math>$ は以下の (R0)-(R3) を満たしている. |
| + | |||
| + | |||
| + | '''(R0)''' <math>$\rho(\emptyset)=0</math>$. | ||
| + | |||
| + | '''(R1)''' $<math>\forall X\subseteq N$: $\rho(X)\leq |X|</math>$. | ||
| + | |||
| + | '''(R2)''' $<math>X\subseteq Y \Rightarrow \rho(X)\leq\rho(Y)</math>$. | ||
| + | |||
| + | '''(R3)''' $<math>\forall X,Y\subseteq N$: $\rho(X)+\rho(Y)\geq\rho(X\cap Y)+\rho(X\cup Y)</math>$. | ||
| + | |||
| + | |||
| + | 特に, (R3) は $<math>\rho</math>$ が[[劣モジュラ関数]] (submodular function) であることを示している. | ||
| + | |||
| + | ここでは, (I0)-(I2) によってマトロイドを定義したが, (B0)-(B1) を満たす基族 $<math>\B</math>$ からマトロイドを定義することもできる. この場合, 独立集合は基の部分集合として定義される. 同様に, (R0)-(R3) を満たす階数関数によってマトロイドを定義することもできる. この場合, 独立集合族は $<math>\I=\{I\mid \rho(I)=|I|\}</math>$ によって定められる. | ||
離散最適化に現れるマトロイドの代表的な例を以下に挙げる. | 離散最適化に現れるマトロイドの代表的な例を以下に挙げる. | ||
| − | '''グラフ的マトロイド''' 点集合 $V$, 枝集合 $E$ を持つ無向グラフ $G=(V,E)$ を考える. 枝集合の部分集合のうち, 閉路を含まないものの全体を $\I$ とすると, $(E,\I)$ は (I0) | + | '''グラフ的マトロイド''' 点集合 $<math>V</math>$, 枝集合 $<math>E</math>$ を持つ無向グラフ $<math>G=(V,E)</math>$ を考える. 枝集合の部分集合のうち, 閉路を含まないものの全体を $<math>\I</math>$ とすると, $<math>(E,\I)</math>$ は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイドをグラフ的マトロイドと呼ぶ. |
| − | '''横断マトロイド''' 点集合 $U$, $V$, 枝集合 $E$ からなる2部グラフ $H=(U,V;E)$ を考える. 枝部分集合 $M\subseteq E$ で端点を共有しないものを $H$ のマッチングという. 点集合 $U$ の部分集合で, $H$ のマッチングの $U$ における端点集合となり得るものの全体を $\I$ とする. このとき, $(U,\I)$ は (I0) | + | '''横断マトロイド''' 点集合 $<math>U</math>$, $<math>V</math>$, 枝集合 $<math>E</math>$ からなる2部グラフ $<math>H=(U,V;E)</math>$ を考える. 枝部分集合 $<math>M\subseteq E</math>$ で端点を共有しないものを $<math>H</math>$ のマッチングという. 点集合 $<math>U</math>$ の部分集合で, $<math>H</math>$ のマッチングの $<math>U</math>$ における端点集合となり得るものの全体を $<math>\I</math>$ とする. このとき, $<math>(U,\I)</math>$ は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイド $<math>(U,\I)</math>$ を横断マトロイドと呼ぶ. |
| − | マトロイド $\M=(N,\I)$ の各要素 $i\in N$ に重み $w(i)$ が与えられたとき, 以下の様な[[貪欲アルゴリズム]] (greedy algorithm) を適用して最終的に得られる $I$ が, 重み最小の基, すなわち, $w(B)=\sum\{w(i)\mid i\in B\}$ を最小にする基 $B\in\B$ となる. | + | マトロイド $<math>\M=(N,\I)</math>$ の各要素 $<math>i\in N</math>$ に重み $<math>w(i)</math>$ が与えられたとき, 以下の様な[[貪欲アルゴリズム]] (greedy algorithm) を適用して最終的に得られる $<math>I</math>$ が, 重み最小の基, すなわち, $<math>w(B)=\sum\{w(i)\mid i\in B\}</math>$ を最小にする基 $<math>B\in\B</math>$ となる. |
| − | + | *$<math>I\leftarrow\emptyset$; $S\leftarrow N$; </math> | |
| − | + | ||
| − | + | *$<math>S=\emptyset</math>$ となるまで, 以下を繰り返す. | |
| − | + | ::$<math>S</math>$ の中で, 重み最小の要素を $<math>j</math>$ とする; $<math>S\leftarrow S-\{j\}$;</math> | |
| − | + | :: <math>-</math>もし $<math>I\cup\{j\}\in\I</math>$ であれば, $<math>I\leftarrow I\cup \{j\}$.</math> | |
| − | |||
全く同様のアルゴリズムによって, 重みの最大化も可能である. | 全く同様のアルゴリズムによって, 重みの最大化も可能である. | ||
| − | 離散最適化におけるマトロイドの重要性は, 貪欲アルゴリズムのみならず, [[共通マトロイド問題]] (matroid intersection problem) に負うところが大きい. 共通マトロイド問題とは, 台集合を共有するマトロイド $\M^+=(N,\I^+)$ と $\M^-=(N,\I^-)$ における共通独立集合のうちで, 要素数最大のものを求める問題である. この問題の最適値は, $\M^+$ の階数関数 $\rho^+$ と $\M^-$ の階数関数 $\rho^-$ を用いて, | + | 離散最適化におけるマトロイドの重要性は, 貪欲アルゴリズムのみならず, [[共通マトロイド問題]] (matroid intersection problem) に負うところが大きい. 共通マトロイド問題とは, 台集合を共有するマトロイド $<math>\M^+=(N,\I^+)</math>$ と $<math>\M^-=(N,\I^-)</math>$ における共通独立集合のうちで, 要素数最大のものを求める問題である. この問題の最適値は, $<math>\M^+$</math> の階数関数 $<math>\rho^+</math>$ と $<math>\M^-</math>$ の階数関数 $<math>\rho^-</math>$ を用いて, |
| − | + | :<math>\max\{|I|\mid I\in\I^+\cap\I^-\}=\min\{\rho^+(X)+\rho^-(N-X)\mid X\subseteq N\}$$</math> | |
| 70行目: | 77行目: | ||
---- | ---- | ||
| − | + | '''参考文献''' | |
| − | 参考文献 | ||
[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. | [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. | ||
| 81行目: | 87行目: | ||
[4] J. G. Oxley, ''Matroid Theory'', Oxford University Press, 1992. | [4] J. G. Oxley, ''Matroid Theory'', Oxford University Press, 1992. | ||
| − | [5] A. Recski, ''Matroid Theory and Its Applications in Electric Network | + | [5] A. Recski, ''Matroid Theory and Its Applications in Electric Network Theory and in Statics'', Springer-Verlag, 1989. |
| − | Theory and in Statics'', Springer-Verlag, 1989. | ||
[6] D. J. A. Welsh, ''Matroid Theory'', Academic Press, 1976. | [6] D. J. A. Welsh, ''Matroid Theory'', Academic Press, 1976. | ||
2007年7月6日 (金) 16:48時点における版
【まとろいど (matroid) 】
マトロイド (matroid) は, 線型空間内のベクトル集合の一次独立・従属といった概念の組合せ論的な側面を抽象化して得られる公理系を満たすものとして定義されている. 有限集合 $$ とその部分集合族 $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \I} $ が以下の (I0)-(I2) を満たすとき, $$ はマトロイドと呼ばれる.
(I0) $構文解析に失敗 (不明な関数「\I」): {\displaystyle \emptyset\in\I}
$.
(I1) $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle I\subseteq J\in\I\Rightarrow I\in\I} $.
(I2) $構文解析に失敗 (不明な関数「\I」): {\displaystyle I,J\in\I$, $|I|<|J|\Rightarrow\exists j\in J\del I$: $I\cup\{j\}\in\I} $.
マトロイド $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M=(N,\I)}
$ において, $$ を $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M}
$ の台集合, $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \I}
$ を独立集合族 (independent set family) という.部分集合 構文解析に失敗 (不明な関数「\I」): {\displaystyle $I\in\I}
$ は, $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \M$}
の独立集合と呼ばれる.
マトロイド $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M} $ の基とは, 極大な独立集合のことである. 公理 (I2) から明らかなように, 基の要素数は全て等しい. この数をマトロイド $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \M} $ の階数という. 基の全体を$構文解析に失敗 (不明な関数「\B」): {\displaystyle \B} $ と書き, $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M} $ の基族 (base family) と呼ぶ. 基族 $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \B} $ は以下の (B0)-(B1) を満たす.
(B0) $構文解析に失敗 (不明な関数「\B」): {\displaystyle \B\neq\emptyset}
$.
(B1) $構文解析に失敗 (不明な関数「\B」): {\displaystyle B,F\in\B$, $i\in B\del F\Rightarrow\exists j\in F\del B$: $(B\del\{i\})\cup\{j\}\in\B} $.
マトロイド $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M}
$ の階数関数 (rank function) $$ は,
- 構文解析に失敗 (不明な関数「\I」): {\displaystyle \rho(X)=\max\{|I|\mid I\subseteq X,\, I \in\I\} \quad\quad\quad(X\subseteq N)}
と定義される. 階数関数 $$ は以下の (R0)-(R3) を満たしている.
(R0) $.
(R1) $$.
(R2) $$.
(R3) $$.
特に, (R3) は $$ が劣モジュラ関数 (submodular function) であることを示している.
ここでは, (I0)-(I2) によってマトロイドを定義したが, (B0)-(B1) を満たす基族 $構文解析に失敗 (不明な関数「\B」): {\displaystyle \B} $ からマトロイドを定義することもできる. この場合, 独立集合は基の部分集合として定義される. 同様に, (R0)-(R3) を満たす階数関数によってマトロイドを定義することもできる. この場合, 独立集合族は $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \I=\{I\mid \rho(I)=|I|\}} $ によって定められる.
離散最適化に現れるマトロイドの代表的な例を以下に挙げる.
グラフ的マトロイド 点集合 $$, 枝集合 $$ を持つ無向グラフ $$ を考える. 枝集合の部分集合のうち, 閉路を含まないものの全体を $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \I} $ とすると, $構文解析に失敗 (不明な関数「\I」): {\displaystyle (E,\I)} $ は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイドをグラフ的マトロイドと呼ぶ.
横断マトロイド 点集合 $$, $$, 枝集合 $$ からなる2部グラフ $$ を考える. 枝部分集合 $$ で端点を共有しないものを $$ のマッチングという. 点集合 $$ の部分集合で, $$ のマッチングの $$ における端点集合となり得るものの全体を $構文解析に失敗 (不明な関数「\I」): {\displaystyle \I} $ とする. このとき, $構文解析に失敗 (不明な関数「\I」): {\displaystyle (U,\I)} $ は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイド $構文解析に失敗 (不明な関数「\I」): {\displaystyle (U,\I)} $ を横断マトロイドと呼ぶ.
マトロイド $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M=(N,\I)} $ の各要素 $$ に重み $$ が与えられたとき, 以下の様な貪欲アルゴリズム (greedy algorithm) を適用して最終的に得られる $$ が, 重み最小の基, すなわち, $$ を最小にする基 $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B\in\B} $ となる.
- $
- $$ となるまで, 以下を繰り返す.
- $$ の中で, 重み最小の要素を $$ とする; $
- もし $構文解析に失敗 (不明な関数「\I」): {\displaystyle I\cup\{j\}\in\I} $ であれば, $
全く同様のアルゴリズムによって, 重みの最大化も可能である.
離散最適化におけるマトロイドの重要性は, 貪欲アルゴリズムのみならず, 共通マトロイド問題 (matroid intersection problem) に負うところが大きい. 共通マトロイド問題とは, 台集合を共有するマトロイド $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M^+=(N,\I^+)} $ と $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M^-=(N,\I^-)} $ における共通独立集合のうちで, 要素数最大のものを求める問題である. この問題の最適値は, $構文解析に失敗 (不明な関数「\M」): {\displaystyle \M^+$} の階数関数 $$ と $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \M^-} $ の階数関数 $$ を用いて,
- 構文解析に失敗 (不明な関数「\I」): {\displaystyle \max\{|I|\mid I\in\I^+\cap\I^-\}=\min\{\rho^+(X)+\rho^-(N-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, 1999.
[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.