マトロイドのソースを表示

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

== 定義 ==
[[画像:set system examples.svg|300px|thumb|E = {1, 2, 3} におけるそれぞれの例。左は(A1),(A2),(A3)を満たすからマトロイド。中央は(A1),(A2)を満たすから独立性システム。右は(A1),(A3)を満たすからグリードイド。]]
有限集合 {{mvar|E}} とその部分集合族 <math>F \subseteq 2^E</math> の組 {{math2|(''E'', ''F'')}} が<ref group="注">記号の意味については「[[冪集合]]」「[[空集合]]」「[[集合間の関係を表す記号]]」「[[濃度 (数学)]]」「[[合併 (集合論)|和集合]]」「[[差集合]]」を参照のこと</ref>
*('''A1''') <math>\emptyset\in{F}</math>
*('''A2''') <math>X \subseteq Y \in F \Rightarrow X \in F</math>
*('''A3''') <math>X, Y \in F,\ |X|>|Y| \Rightarrow \exists\ x \in X \setminus Y \text{ s.t. } Y \cup \{x\} \in F.</math>
を満たすとき、'''マトロイド'''と呼ばれ、(A1) および (A2) のみを満たすとき'''独立性システム''' (''independence system'') と呼ばれる。さらに (A1) および (A3) を満たすとき'''グリードイド''' (''greedoid'') と呼ばれる。

以下に本項で使う用語の定義を挙げる。

*'''独立集合''' ({{lang-en-short|independent set}}) - <math>F</math> の要素
*'''従属集合''' ({{lang-en-short|dependent set}}) - <math>2^E \setminus F</math> の要素
*'''サーキット''' ({{lang-en-short|circuit}}) - 極小な従属集合
*'''基''' ({{lang-en-short|base, basis}}) - 極大な独立集合
*<math>X</math> の'''基''' - <math>X \subseteq E</math> とする <math>X</math> の部分集合の中で極大な独立集合

=== ランク、階数関数 ===
独立性システム (E, F) の階数 (rank) 関数 <math>r: 2^E \to \mathbb{R}</math> は、<math>X \subseteq E</math> に対して 
:<math>r(X) := \max \{ |Y| : Y \subseteq X,Y \in F \}</math> 
と定義される。マトロイドならば、公理(A3) から {{mvar|E}} の部分集合 {{mvar|X}} に対して {{mvar|X}} のどの基も元数は等しいため、階数関数を<math>X</math>の基の大きさと定義しても構わない。

例えば、E = {1, 2, 3}, F=<nowiki>{{},{1},{2},{1,2}}</nowiki> というマトロイドならば r({1}) = 1, r({1, 2}) = 2, r({1, 2, 3}) = 2, r({1, 3}) = 1 等となる。

独立性システム <math>(E,F)</math> の階数関数 <math>r: 2^E \to \mathbb{R}</math> は任意の <math>X,Y \subseteq E</math> と <math>x,y \in E</math> について次の性質を持つ。
*('''R1''') <math>r(X) \leq |X|</math>
*('''R2''') <math>X \subseteq Y \Rightarrow r(X) \le r(Y)</math>
*('''R3''') <math>r(\emptyset)=0</math>

さらに、<math>(E,F)</math> がマトロイドならば次の性質も持つ。
*('''R4''') <math>r(X \cup Y)+r(X \cap Y) \leq r(X) + r(Y)</math>
*('''R5''') <math>r(X) \leq r(X \cup \{x\}) \leq r(X)+1</math>
*('''R6''') <math>r(X \cup \{x\}) = r(X \cup \{y\}) = r(X) \Rightarrow r(X \cup \{x,y\})=r(X)</math>

特に(R4)に示されているように、階数関数が[[劣モジュラ関数|劣モジュラ]]であることは、マトロイドの極めて重要な性質である。

=== 閉包 ===
独立性システム <math>(E,F)</math> の閉包 (closure) 関数 <math>\sigma \colon 2^E \to 2^E</math> は、<math>X \subseteq E</math> に対して
:<math>\sigma (X) := \{ y \in E : r(X \cup {y}) = r(X) \}</math>
で定義される。
<math>\sigma(X)</math> を {{mvar|X}} の閉包と呼ぶ。

マトロイド <math>(E,F)</math> の閉包関数 <math>\sigma\colon 2^E \to 2^E</math> は次の性質を持つ。
*('''L1''') 任意の <math>X \subseteq E</math> に対して、<math>X \subseteq \sigma(X)</math> 
*('''L2''') 任意の <math>X, Y \subseteq E</math> に対して、<math>X \subseteq Y \Rightarrow \sigma(X) \subseteq \sigma(Y)</math>
*('''L3''') 任意の <math>X \subseteq E</math> に対して、<math>\sigma(X) = \sigma(\sigma(X))</math> 
*('''L4''') 任意の <math>X, Y \subseteq E</math> と任意の <math>x,y \in E</math> に対して、<math>y \not\in \sigma(X),\ y \in\sigma(X\cup\{x\}) \Rightarrow x \in \sigma(X \cup \{y\})</math>

=== ランク商 ===
下方ランク (lower rank) 関数 <math>\rho(X)</math> を <math>X</math> に含まれる基の最小元数とする。つまり、
:<math>\rho(X) := \min \{ |Y|:Y \subseteq X, Y \in F</math> かつ  <math>\forall{x} \in X \setminus Y</math> に対し <math>Y \cup \{x\} \not\in F \}</math>

と定義する。すると、ランク商 (rank quotient) は次のように定義される。
:<math>q(E,F):=\min_{X\subseteq{E}}\frac{\rho(X)}{r(X)}</math>
マトロイドのとき <math>q(E,F)=1</math> である。独立性システムのとき <math>q(E,F) \le 1</math> であり、<math>A \in F, b \in E</math> に対して <math>A \cup \{b\}</math> が高々{{mvar|p}} 個しかサーキットを持たないならば <math>1/p \le q(E,F)</math> である<ref>{{Cite journal |author=D. Hausmann |coauthors=B. Korte , T. A. Jenkyns |year=1980 |title=Worst case analysis of greedy type algorithms for independence systems |journal=Mathematical Programming Studies |volume=12 |pages=120-131}}</ref>ことが知られているのでランク商を見積もることが可能である。

== 例 ==
=== 一様マトロイド ===
E を有限集合とし、ある[[整数]] r 以下の要素数を持つ 2{{sup|E}} の部分集合をFとするとき、(E, F) はマトロイドとなる。これを、'''{{仮リンク|一様マトロイド|en|Uniform matroid}}''' (''uniform matroid'') と呼び、n=|E|としたとき <math>U_n^r</math> などと書く。<math>U_n^r</math> における基は、要素数がrであるようなEの部分集合であり、サーキットは要素数がr+1であるようなEの部分集合である。また、一様マトロイドの[[直和]]は'''{{仮リンク|分割マトロイド|en|Partition matroid}}''' (''partition matroid'') と呼ばれる<ref group="注">マトロイドの直和もマトロイドになる。</ref>。具体的には、<math>B_1,\ldots,B_k</math>を[[素集合|互いに素な集合]]とし、それぞれに <math>0 \le d_i \le |B_i| \ (0 \le i \le k)</math> を定めたとき、<math>0 \le i \le k</math> それぞれにおいて <math>|I\cap B_i|\le d_i</math> を満たす <math>I\subset \bigcup_i B_i</math> の集合を F とすれば、マトロイドとなる。

=== グラフ理論におけるマトロイド ===
E を無向グラフGの辺集合、F を森<ref group="注">閉路のない辺集合</ref>の集合とするとき、(E, F) はマトロイドとなり、'''{{仮リンク|グラフ的マトロイド|en|Graphic matroid}}''' (''graphic matroid'') または '''閉路マトロイド''' (''cycle matroid'') と呼ぶ。しばしばグラフGがグラフ的マトロイドであることを M(G) と書く。グラフ的マトロイドにおける従属集合は、[[閉路]]を持つグラフの集合であるから、サーキットとは単純閉路となる辺集合である。また（X の）基とは（X の部分集合の中で）できうる最大の森のことで、明らかに（X でカバーされる）点の数 &minus; 1 本の辺で作られる森が最大であり、この森の集合を言う。よって、階数関数は r(X) = (Xがカバーする点数) &minus; 1 と書ける。

他にも、グラフにおけるマトロイドはいくつか知られている。
* E を無向グラフ G の辺集合、F を (G, X) が{{仮リンク|pseudoforest|en|pseudoforest}}<ref group="注">各連結成分において、高々1つの閉路を持つグラフ</ref>となるようなXの集合とするとき (E, F) はマトロイドとなる。これを、'''{{仮リンク|bicircularマトロイド|en|Bicircular matroid}}''' (''bicircular matroid'') と呼ぶ。
* 点集合 U, V、辺集合 X とする2部グラフ {{math2|1=''G'' = (''U'', ''V'', ''X'')}} において、[[マッチング (グラフ理論)|マッチング]]の端点となる点集合 <math>S \subseteq U</math> を要素とする集合をFとするとき、(U, F) はマトロイドとなる。これを、'''[[横断マトロイド]]''' (''transversal matroid'') と呼ぶ。完全2部グラフ <math>K_{n,r}</math> の横断マトロイドは、一様マトロイド <math>U_n^r</math> である。
* 点集合を V とするグラフにおいて、点の部分集合を <math>V',U \subseteq V</math> とする。U への点素な |U| 本の[[道 (グラフ理論)|道]]が存在する V' の部分集合を F の要素とすると、(V', F) はマトロイドとなる。これを、'''{{仮リンク|ガンモイド|en|Gammoid}}''' (''gammoid'') と呼ぶ。特に、(V, F) を'''狭義ガンモイド''' (''strict gammoid'') と呼ぶ。

=== 線形代数におけるマトロイド ===
[[画像:Vamos matroid.svg|thumb|Vámosマトロイドは、網掛け四角の4頂点をサーキット(計5つ)とするマトロイドである。]]
E を[[可換体|体]]上の[[行列]]の列集合、その体上で[[線形独立]]である列の集合を F とするとき、(E, F) はマトロイドとなり、'''ベクトルマトロイド''' (''vector matroid'') と呼ぶ。マトロイドが同等の体 K 上のベクトルマトロイドとして記述できるとき、'''表現可能'''であると呼ばれる。任意の体上で表現可能なマトロイドを'''[[正則マトロイド]]''' (''regular matroid'') と呼び、位数2の[[有限体]]上で表現可能なマトロイドを'''{{仮リンク|2値マトロイド|en|Binary matroid}}''' (''binary matroid'') と呼ぶ。これらは、
* マトロイド ⊃ 2値マトロイド ⊃ 正則マトロイド ⊃ グラフ的マトロイド
という包含関係が成り立つ。一方で、Fanoマトロイドは、2値マトロイドであるが（実数体上では表現できないため）正則マトロイドではない。また、'''{{仮リンク|Vámosマトロイド|en|Vámos matroid}}''' (''Vámos matroid'') は、任意の体上で表現できないマトロイドの最も簡単な例である。

=== その他のマトロイド ===
* '''[[2部マトロイド]]''' (''bipartite matroid'') は、サーキットの大きさがすべて偶数であるマトロイドである。[[2部グラフ]]のグラフ的マトロイドを一般化しており、グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である。
* '''{{仮リンク|シルベスターマトロイド|en|Sylvester matroid}}''' (''Sylvester matroid'') は、すべてのサーキットの大きさが3であるようなマトロイドである。例えば、ランク2の一様マトロイド <math>U_n^2</math> はシルベスターマトロイドである。
* '''{{仮リンク|pavingマトロイド|en|Paving matroid}}''' (''paving matroid'') は、すべてのサーキットの大きさがランクよりも大きいマトロイドである。例えば、一様マトロイド <math>U_n^r</math> のランクはrであり、サーキットの大きさは常に r + 1 であるため、pavingマトロイドである。
* '''{{仮リンク|オイラーマトロイド|en|Eulerian matroid}}'''(''eulerian matroid'') は、要素がサーキットによって[[集合の分割|分割]]できるようなマトロイドである。例えば、一様マトロイド <math>U_n^r</math> は r + 1 が n を割り切るとき、かつそのときのみオイラーマトロイドである。

== 他の公理系 ==
集合Eとその部分集合の[[族]]Fが(A1)から(A3)を満たすときマトロイドと呼ぶことにし、そこから基やランクを定義した。だが、実はこれらの性質を持つ族あるいは関数からマトロイドとなる F を得ることができる。

=== 基族 ===
有限集合 {{mvar|E}} と <math>\mathcal{B} \subseteq 2^E</math> とする。
<math>\mathcal{B}</math> がマトロイド (E, F) の基族であるための[[必要十分条件]]は次の(B1),(B2)が成り立つことである。
*('''B1''') <math>\mathcal{B}\neq\emptyset</math>
*('''B2''') 任意の <math>B',B''\in \mathcal{B}, x \in B' \setminus B''</math> について <math>(B'\setminus \{ x \}) \cup \{ y \} \in \mathcal{B}</math> となる <math>y \in {B''} \setminus {B'}</math> が存在する。

基が1つしかない場合は明らかにマトロイドとなる。そうでない場合、例えば <math> E = \{ 1,2,3 \}, \mathcal{B} = \{\{1,2\},\{2,3\},\{1,3\}\}</math> とすると <math>\mathcal{B}</math> は(B1)および(B2)を満たす。このような基の族を持つマトロイドは、一様マトロイド <math>U_3^2</math> ただ1つに決まることが分かる。また、基族が <math>\mathcal{B}=\{\{1,2\},\{3\}\}</math> のときは(B2)を満たさないため、この基族ではマトロイドにならない。事実、<math>F = \{\{1\}, \{2\}, \{3\}, \{1,2\}\}</math> とすると、この例の基族となるが、(A3)を満たさずマトロイドになっていない。

=== サーキットの族 ===
有限集合 E と C ⊆ 2{{sup|E}} とする。C がマトロイド (E, F) のサーキットの族であるための必要十分条件は次の(C1),(C2),(C3)が成り立つことである。

*('''C1''') <math>\emptyset\not\in{C}</math>
*('''C2''') 任意の C{{sub|1}}, C{{sub|2}} ∈ C について C{{sub|1}} ⊆ C{{sub|2}} ならば C{{sub|1}} = C{{sub|2}} である。
*('''C3''') 任意の C{{sub|1}}, C{{sub|2}} ∈ C は C{{sub|1}} ≠ C{{sub|2}} で c ∈ C{{sub|1}} ∩ C{{sub|2}} とするとき、<math>C_3 \subseteq (C_1 \cup C_2) \setminus \{c \}</math> となる C{{sub|3}} ∈ C が存在する。

=== ランク関数 ===
マトロイドのランク関数は(R1)から(R6)を満たすが、逆にEと(R1),(R2),(R4)を満たす<ref group="注">(R3),(R5),(R6)を満たす関数と(R1),(R2),(R4)を満たす関数は同値</ref>関数 <math>r:2^E\to\mathbb{Z}_+</math> を与えればFは直ちに決まり (E, F) はマトロイドであり、r はランク関数である。

例えば、E = {1, 2, 3} とし、関数 r を
:<math>r(\emptyset)=0,r({1})=1,r({2})=0,r({3})=1,r({1,2})=1,r({2,3})=1,</math>
:<math>\ r({1,3})=2,r({1,2,3})=2\ </math>
と定義すると、r は(R1),(R2),(R4)を満たすことが確認できる。すると、r(X) = |X| となる X の族を F と定義すると F = {{1}, {3}, {1,3}} となり、(E, F) はマトロイドになることが確認できる。このように、r を決めれば対応する F がただ1つに決まる。

=== 閉包関数 ===
(L1)から(L4)を満たす関数 <math>\sigma:2^E{\to}2^E</math> はマトロイドの閉包関数となる。

== マトロイドの構成法 ==
ここでは、1つ以上のマトロイド（あるいは独立性システム）から新たなマトロイドを構成する方法について説明する。

=== 双対 ===
独立性システム (E, F) に対して、F{{sup|*}} を <math>X \cap B = \emptyset</math> となる (E, F) の基 B が存在する <math>X \subseteq E</math> の集合とする。このとき、(E, F{{sup|*}}) を (E,F) の'''双対''' (''dual'') と定義する。

双対には次のような性質がある。
* (E, F{{sup|**}}) = (E,F)
* (E, F) が独立性システムならば、(E, F{{sup|*}}) は独立性システム
* (E, F) はマトロイド <math>\iff</math> (E, F{{sup|*}}) はマトロイド<ref>{{Cite journal |author=Hassler Whitney |date=1935-07 |title=On the abstract properties of linear dependence |journal=American Journal of Mathematics |volume=57 |pages=509-533 |url=http://www.math.osu.edu/~chmutov/wor-gr-su06/ref/Wh.pdf |format=pdf |accessdate=2011-03-19}}</ref>。
* マトロイド (E, F) とその双対 (E, F{{sup|*}}) とし、それぞれのランク関数を r, r{{sup|*}} とすると、r{{sup|*}} は任意の X ⊆ E に対して <math>r^*(X)=|X|+r(E{\setminus}X)-r(E)</math> である。

例えば、 E = {1, 2, 3}, F = {{1}, {2}, {1,2}} というマトロイドに対して基の族 B = { {1, 2} } だから F{{sup|*}} = { {3} } となる。双対のランク関数も、例えば r{{sup|*}}({1, 3}) = 2 + r({2}) - r({1, 2, 3}) = 2 + 1 - 2 = 1 となるように、成り立っていることが分かる。

また、[[平面グラフ]]に対する双対とグラフ的マトロイドの双対の概念は一致する。つまり、任意の平面的グラフ G の閉路マトロイド M(G) の双対は、G の双対平面グラフ G{{sup|*}} のマトロイドと（[[平面埋め込み]]の方法によらず）同一である。

=== 交差 ===
2つの独立性システム (E, F{{sub|1}}), (E, F{{sub|2}}) とするとき、(E, F{{sub|1}} ∩ F{{sub|2}}) を2つの独立性システムの'''交差''' (''intersection'') と定義する。有限個の独立性システムの交差も同様に定義でき、交差もまた独立性システムとなる。任意の独立性システム (E, F) は、有限個のマトロイドの交差で表せる。さらに、p 個のマトロイドの交差ならば、q(E, F) ≧ 1/p。

例えば[[2部グラフ]]の[[マッチング (グラフ理論)|マッチング]]問題の場合、Eを辺集合、Fをマッチング集合とすれば、2部グラフであるから点集合は A ∪ B と書ける。F{{sub|1}} を任意の点 a ∈ A に繋がる辺は高々1本であるという条件とするならば (E, F{{sub|1}}) はマトロイドであり、同様に F{{sub|2}} を任意の点 b ∈ B に繋がる辺は高々1本であるという条件とするならば (E, F{{sub|2}}) もマトロイドである。F = F{{sub|1}} ∩ F{{sub|2}} なので、(E, F) は2つのマトロイド (E, F{{sub|1}}), (E, F{{sub|2}}) の交差である。

=== 合併 ===
2つのマトロイド (E, F{{sub|1}}),(E, F{{sub|2}}) とする。X{{sub|1}} ∈ F{{sub|1}}, X{{sub|2}} ∈ F{{sub|2}} となる X の分割 X = X{{sub|1}} ∪ X{{sub|2}} が存在するとき、X ⊆ E は '''分割可能''' (''partitionable'') であると呼ぶ。<math>F=\{X\subseteq E : X \mbox{ is partitionable}\}</math> とするとき、(E, F) を (E, F{{sub|1}}), (E, F{{sub|2}}) の'''合併'''(''union'') あるいは'''和'''(''sum'') と呼ぶ。有限個のマトロイドの合併も同様に定義できる。
* マトロイドの合併は、マトロイドとなる。
* k個のマトロイド (E, F{{sub|1}}), …, (E, F{{sub|k}}) の各ランク関数を r{{sub|1}}, …, r{{sub|k}} とすると、これらの合併 (E, F) のランク関数は <math>r(X)=\min_{A{\subseteq}X}(|X\setminus{A}|+\sum_{i=1}^kr_i(A))</math> である<ref>{{Cite book |author=Crispin Nash-Williams |year=1967 |chapter=An application of matroids to graph theory |title=Theory of Graphs; proceedings of an international symposium in Rome 1966 |editor=P.Rosenstiehl, ed. |pages=263-265 |publisher=Gordon and Breach |location=New York}}</ref>。

== 組合せ最適化 ==
[[組合せ最適化]]問題の多くは、独立性システム <math>(E,F)</math> とコスト関数 <math>c : E \to \mathbb{R}</math> に対して、<math>\sum_{e \in X}c(e)</math> を最大（あるいは最小）にする <math>X \in F</math> を求める最適化問題に定式化できる。

例えば、以下の中で最小全域木問題はマトロイドになるが、他はマトロイドにはならず、独立性システムとなる。
*[[巡回セールスマン問題]] - Eをグラフの辺、Fは[[ハミルトン閉路]]の部分集合
*[[ナップサック問題]] - Eを荷物、Fは規定の重さを超えない荷物の組合せ
*[[最小全域木問題]] - Eはグラフの辺、Fはグラフの森の集合

=== 貪欲法 ===
マトロイドにおいては[[貪欲法]]で最適解が得られることを示す。なお、マトロイドの貪欲法は組合せ最適化の貪欲法の全てを網羅しているわけではない。たとえば、[[クラスカル法]]はマトロイド上の貪欲法で説明できるが、[[プリム法]]や[[ダイクストラ法]]は異なる。

==== 最良選択貪欲法 ====
'''最良選択貪欲法'''は、<math>c(e)</math> の大きい順に <math>e \in E</math> を暫定解に追加できるならば追加し追加できない場合は次の要素に移ることを繰り返すアルゴリズムである。つまり、
#<math>c(e_1) \ge c(e_2) \ge \cdots \ge c(e_n)</math> となるように <math>E = \{e_1, e_2, \cdots, e_n\}</math> を[[ソート]]する。
#<math>E_{ans} \leftarrow \emptyset</math>
#'''For i = 1 to n''' : <math>E_{ans} \cup \{ e_i \} \in F</math> ならば <math>E_{ans} \leftarrow E_{ans} \cup \{ e_i \}</math>
#<math>E_{ans}</math>を解として出力する。
というアルゴリズムである。

最良選択貪欲法で得られる解のコストを <math>c(G)</math>、最適解のコストを <math>c(OPT)</math> とすると、ランク商 <math>q(E,F)</math> を使って
:<math>q(E,F) \le \frac{c(G)}{c(OPT)} \le 1</math>
が任意のコスト関数に対して成立する<ref>{{Cite journal |author=T.A. Jenkyns |year=1976 |title=The Efficacy of the greedy Algorithm |journal=Proc. of 7th S-E. Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Winnipeg |pages=341-350}}</ref><ref>{{Cite book |author=Bernhard Korte |coauthors=Dirk Hausmann |year=1978 |chapter=An Analysis of the greedy heuristic for independence systems |title=Aogorithmic Aspects of Combinatorics; Annals of Discrete Mathematics |editor=B. Alspach, P. Hell, D.J. Miller, eds. |volume=2 |pages=65-74 |publisher=North-Holland |location=Amsterdam}}</ref>。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム (E, F) がマトロイドであるための必要十分条件は最良選択貪欲法で全ての <math>c:E\to\mathbb{R}_+</math> に対して最大化問題の最適解を求めることができることである<ref>{{Cite journal |author=R. Rado |year=1957 |title=Note on Independence Functions |journal=Proceedings of the London Mathematical Society |volume=7 |pages=300-320}}</ref><ref>{{Cite journal |author=Jack Edmonds |year=1971 |title=Matroids and the greedy algorithm |journal=Mathematical Programming |volume=1 |pages=127-136}}</ref>。これを '''Edmonds-Rado 定理'''という。

==== 証明の概要 ====
<math>c(G) \ge q(E,F)c(OPT)</math> の証明の概要を述べる。 

{{mvar|G}} を最良選択貪欲法で得られる解、<math>OPT</math> を最適解とする。<math>E=\{e_1,\ldots,e_n\}</math> は、<math>c(e_1) \ge c(e_2) \ge \cdots \ge c(e_n)</math> となるようにソート済みであるとし、<math>E_j=\{e_1,\ldots,e_j\}</math> とする。また、
:<math>d_j = \begin{cases}
c(e_n), &\mbox{if } j = n\\
c(e_j) - c(e_{j+1}), &\mbox{otherwise}
\end{cases}</math>
とし、任意の <math>X \subseteq 2^E</math> に対して、<math>X_j = X \cap E_j</math> と置く。このとき、次の事実が成り立つ。
* 任意の <math>X \subseteq 2^E</math> において、<math>c(X) = \sum_{j=1}^n |X_j| d_j</math><ref group="注"><math>(|X_j| - |X_{j-1}|)</math> は、<math>e_j \in X</math> のとき、かつそのときのみ1となるから、<math>c(X) = \sum_{j=1}^n (|X_j| - |X_{j-1}|) c(e_j)</math> が得られる。これを <math>|X_j|</math> でまとめて右辺を得る。</ref>
* 任意の <math>1\le j \le n</math> において、<math>\rho(E_j) \le |G_j|</math><ref group="注">{{mvar|G{{sub|j}}}} は {{mvar|E{{sub|j}}}} の基であり、{{math|ρ}} の定義より得られる。</ref>
* 任意の <math>X \subseteq E</math> において、<math>r(X)q(E,F) \le \rho(X)</math><ref group="注">ランク商の定義より明らか。</ref>
* 任意の <math>1\le j \le n</math> において、<math>|OPT_j| \le r(E_j)</math><ref group="注"><math>OPT_j\in F</math> であることと、階数関数の定義および性質('''R1''')より得られる。</ref>

以上のことから、
:<math>c(G) = \sum_{j=1}^n |G_j| d_j \ge \sum_{j=1}^n \rho(E_j) d_j \ge q(E,F)\sum_{j=1}^n r(E_j) d_j \ge q(E,F)\sum_{j=1}^n |OPT_j| d_j = q(E,F)c(OPT)</math>
となる。

==== 最悪棄却貪欲法 ====
独立性システム (E, F) とコスト関数 <math>c:E\to\mathbb{R}_{+}</math>に対する最小化問題を解く。'''最悪棄却貪欲法'''は、都合の悪い e ∈ E を優先して解から除外する。つまり、
#<math>c(e_1) \ge c(e_2) \ge \cdots \ge c(e_n)</math> となるように <math>E = \{e_1, e_2, \cdots, e_n\}</math> をソートする。
#<math>E_{ans}\leftarrow E</math>
#'''For i = 1 to n''' : <math>E_{ans}\setminus\{e_i\}</math> が基を含むならば、<math>E_{ans}\leftarrow E_{ans}\setminus\{e_i\}</math>
#<math>E_{ans}</math> を解として出力する。
というアルゴリズムである。

最悪棄却貪欲法で得られる解のコストを c(G)、最適解のコストを c(OPT) とすると、ランク商 q(E, F)、双対な独立性システム (E, F{{sup|*}}) の下方ランク関数 ρ{{sup|*}}、ランク関数 r{{sup|*}} を使って
:<math>1\le\frac{c(G)}{c(OPT)}\le\max_{X\subseteq{E}}\frac{|X|-\rho^*(X)}{|X|-r^*(X)}</math>
と書ける<ref>{{Cite book |author=Bernhard Korte |coauthors=C.L. Monma |chapter=Some remarks on a classification of oracle-type algorithms |year=1979 |title=Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen |editor=L. Collatz, G. Meinardus, W. Wetterling, eds. |volume=2 |publisher=Birkh&#228;user |location=Basel |pages=195-215}}</ref>。マトロイドならば ρ{{sup|*}} = r{{sup|*}} なので、常に最適解を得られることが分かる。

==== オラクル ====
組合せ最適化問題において F は明示的に与えられることはまずない。F を列挙しようとすることは無謀であるので、現実には E とコスト関数cのみが与えられる。最良選択貪欲法を実行するには、さらに独立性オラクルを必要となる。独立性オラクルとは、X ⊆ E が与えられたとき X ∈ F であるかどうかを判定する[[神託機械|オラクル]]である。これがないと最良選択貪欲法の3番目のステップは実行できない。同様に最悪棄却貪欲法を実行するためには X ⊆ E が与えられたとき X が基<ref group="注">'''X''' の基でないことに注意</ref>を含むかを判定する基拡張集合オラクルを必要とする。

では、独立性オラクルか基拡張集合オラクルどちらか一方が与えられたとき、そのオラクルを使ってもう一方を[[多項式時間]]で実行可能(多項式等価)だろうか<ref group="注">概念は「[[多項式時間変換]]」に詳しい</ref>。例えば、[[巡回セールスマン問題]]に対する独立性システムの独立性オラクルはつまり、与えられた辺集合がハミルトン閉路の部分集合であるかを判定するものであるが、グラフは[[完全グラフ]]であるので、多項式時間で実行可能である。対して基拡張集合オラクルは与えられた辺集合からいくらか辺を削除することによってハミルトン閉路になるかということを判定しなくてはならない。それはつまり[[ハミルトン閉路問題]]と等価であり、ハミルトン閉路問題はNP完全である<ref>{{Cite book |author=Richard M. Karp |chapter=[http://www.cs.berkeley.edu/~luca/cs172/karp.pdf Reducibility Among Combinatorial Problems] |title=Complexity of Computer Computations |editor=R. E. Miller and J. W. Thatcher eds |publisher=New York: Plenum |pages=85-103 |year=1972}}</ref>ため難しいと言える。このように、独立性システムにおいて独立性オラクルと基拡張集合オラクルは必ずしも多項式等価ではない。

マトロイドにおいては独立性オラクル、基拡張集合オラクル、ランク関数を返すランクオラクル、閉包関数を返す閉包オラクル全て多項式等価である。しかし、与えられた部分集合が基かどうかを判定する基決定オラクルは独立性オラクルより弱い<ref group="注">最良選択貪欲法を使うことによって（本質的には独立性オラクルを複数回使うことによって）基決定オラクルを作れるが、逆に基決定オラクルを多項式回使っても独立性オラクルを作れない</ref>し、与えられた部分集合の最小元数の従属部分集合を返すオラクルは独立性オラクルより強い<ref>{{Cite journal |author=D. Hausmann |coauthors=B. Korte |year=1981 |title=Algorithmic versus axiomatic definitions of matroids |journal=Mathematical Programming Study |volume=14 |pages=98-111}}</ref>。

=== 近似 ===
最適化問題は厳密解を求めることが現実的でないことが多いために、近似の限界についても研究されている。次の問題が効率的に解ける（入力のサイズと 1/ε の多項式時間で解を出力するアルゴリズムが存在する）ことと、誤差が高々 1+ε 倍の解を出力する多項式時間アルゴリズムが存在することは同値である<ref>{{Cite book |author=B. Korte |coauthors=R. Schrader |chapter=On the existence of fast approximation schemes
|title=Nonlinear Programming |Volume=4 |editor=O. Mangaserian, R.R. Meyer, S.M. Robinson, eds. |publisher=Academic Press |location=New York |pages=415-437 |year=1981}}</ref>。

独立性システム (E, F)、コスト関数 <math>c:E\to\mathbb{Z}_+</math>、部分集合 S, S' ⊆ E, ε > 0 が
:<math>\frac{1}{1+\epsilon}c(S) \le c(S') \le (1+\epsilon)c(S)</math>
であるとき、S ⊆ B となる基 B が存在して S' ⊆ B' となる基 B' 全てに対して (1 + ε)c(B) ≧ c(B') が成立するか？

つまり、部分的なコスト（c(S) や c(S')）が高々 1 + ε 倍違う程度ならば、それらからできうる最適解も 1 + ε 倍程度しか違わないだろうか、という問題である。部分が最適ならば全体も最適であるという場合はε=0であり、よく知られているように[[動的計画法]]が存在する。よって、(E, F) をマトロイドに限定するならば多項式時間アルゴリズムは存在する。

[[ナップサック問題]]はこのアルゴリズムが知られている珍しい例で、計算時間が <math>O(n^2\cdot\frac{1}{\epsilon})</math><ref>{{Cite journal |author=Oscar H. Ibarra |coauthors=	Chul E. Kim |date=1975-10 |title=Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems |journal=Journal of the ACM |volume=22 |issue=4 |pages=463-468 |issn=0004-5411 |doi=10.1145/321906.321909}}</ref><ref>{{Cite journal |author=Sartaj K. Sahni |date=1976-01 |title=Algorithms for Scheduling Independent Tasks |journal=Journal of the ACM |volume=23 |issue=1 |pages=116-127 |issn=0004-5411 |doi=10.1145/321921.321934}}</ref><ref>{{Cite book |author=G.V. Gens |coauthorsE.V. Levner |chapter=Computational complexity of approximation algorithms for combinatorial problems |title=Mathematical Foundations of Computer Science |editor=J. Becvar, ed. |publisher=Springer |location=Berlin |pages=292-300 |year=1979}}</ref>や <math>O(n\log(\frac{1}{\epsilon})+\frac{1}{\epsilon^4})</math><ref>{{Cite journal |author=Eugene L. Lawler |year=1979 |title=Fast Approximation Algorithms for Knapsack Problems |journal=Mathematics of Operations Research |volume=4 |pages=339-356 |doi=10.1287/moor.4.4.339}}</ref>で、出力される解の評価が最適解の評価の高々 1 + ε 倍であるアルゴリズムがある。

== マトロイドに関する問題 ==
=== マトロイド交差問題と分割問題 ===
'''マトロイド交差問題''' (''Matroid Intersection Problem'') は、2つのマトロイド (E, F{{sub|1}}), (E, F{{sub|2}}) が与えられたとき、|F| が最大となるような F ∈ F{{sub|1}} ∩ F{{sub|2}} を求める問題である。マトロイド交差問題は多項式時間で解ける。また、3つ以上のマトロイド交差問題も同様に考えることができるが、これは[[NP困難]]問題である。

重み付き版についてもアルゴリズムが知られていて<ref>{{Cite journal |author=A. Frank |year=1981 |title=A weighted matroid intersection algorithm |journal=Journal of Algorithms |volume=2 |pages=328-336}}</ref>、2つの独立性オラクルの計算量の大きい方を α とすると O(|E|{{sup|3}}α) で解ける。

'''マトロイド分割問題''' (''Matroid Partitioning Problem'') は k 個のマトロイド (E, F{{sub|1}}), …, (E, F{{sub|k}}) が与えられたとき |X| が最大になるような分割可能な X ⊆ E を求める問題である。マトロイド交差問題とマトロイド分割問題は等価である。

== 一般化 ==
'''[[グリードイド]]'''はマトロイドと'''[[反マトロイド]]'''を一般化したものである。グリードイドにも[[貪欲法]]が定式化できて、特殊な条件下においては最適解を出力する。だが、グリードイド上での最適化問題は[[NP困難]]であることが知られている。

また、マトロイドのランク関数が[[劣モジュラ関数]]であることは既に述べたが、有限集合Eと劣モジュラ関数 <math>f:2^E\to\mathbb{R}_+</math>を用いて'''[[ポリマトロイド]]''' (polymatroid) と呼ばれる有界[[多面体]]を定義できる。ポリマトロイドとベクトルに対する分離問題は劣モジュラ関数最小化問題に帰着できる。劣モジュラ関数最小化問題は例えば[[フローネットワーク]]における無向グラフの最小カットを求める問題などを一般化している。劣モジュラ関数最小化問題は[[楕円体法]]を用いることで多項式時間で解ける<ref>{{Cite journal |author=M. Gr&#246;tschel |coauthors=L. Lov&#225;sz, A. Schrijver |year=1981 |title=The ellipsoid method and its consequences in combinatorial optimization |journal=Combinatorica |volume=1 |pages=169-197 |url=http://oai.cwi.nl/oai/asset/10046/10046A.pdf |format=pdf |accessdate=2011-03-26}}</ref>ことが知られて以来、Schrijverのアルゴリズム<ref>{{Cite journal |author=Alexander Schrijver |year=2000 |title=A combinatorial algorithm minimizing submodular functions in strongly polynomial time |journal=Journal of Combinatorial Theory, Series B |volume=80 |issue=2 |pages=346-355 |url=https://homepages.cwi.nl/~lex/files/minsubm6.pdf |format=pdf |accessdate=2023-05-14}}</ref>等が知られている。

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Reflist|group="注"}}
=== 出典 ===
{{Reflist|2}}

== 参考文献 ==
#{{Cite book|和書 |author=B.コルテ |coauthors=J.フィーゲン |translator=浅野孝夫、平田富夫、小野孝男、浅野泰仁 |title=組合せ最適化-理論とアルゴリズム |edition=第2版 |date=2012-02-29 |publisher=シュプリンガー・ジャパン |isbn=978-4621062029}}

== 関連項目 ==
=== 分野 ===
*[[組合せ最適化]]
*[[グラフ理論]]
*[[計算複雑性理論]]

=== 数学的対象 ===
*[[ポリマトロイド]]
*[[グリードイド]]
*[[劣モジュラ関数]]

== 外部リンク ==
*{{高校数学の美しい物語|1085|マトロイドの定義と具体例}}

{{Normdaten}}
{{DEFAULTSORT:まとろいと}}
[[Category:マトロイド理論|*]]
[[Category:閉包作用素]]
[[Category:組合せ最適化]]
[[Category:組合せ論]]
[[Category:最適化]]
[[Category:オペレーションズリサーチ]]
[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]