マトロイド
マトロイド交差問題 (Matroid Intersection Problem) は、2つのマトロイド (E, F1), (E, F2) が与えられたとき、|F| が最大となるような F ∈ F1 ∩ F2 を求める問題である。マトロイド交差問題は多項式時間で解ける。また、3つ以上のマトロイド交差問題も同様に考えることができるが、これはNP困難問題である。
重み付き版についてもアルゴリズムが知られていて、2つの独立性オラクルの計算量の大きい方を α とすると O(|E|α) で解ける。
マトロイド分割問題 (Matroid Partitioning Problem) は k 個のマトロイド (E, F1), ..., (E, Fk) が与えられたとき |X| が最大になるような分割可能な X ⊆ E を求める問題である。マトロイド交差問題とマトロイド分割問題は等価である。
とし、任意の X ⊆ 2 E {\displaystyle X\subseteq 2^{E}} に対して、 X j = X ∩ E j {\displaystyle X_{j}=X\cap E_{j}} と置く。このとき、次の事実が成り立つ。
任意の X ⊆ 2 E {\displaystyle X\subseteq 2^{E}} において、 c ( X ) = ∑ j = 1 n | X j | d j {\displaystyle c(X)=\sum _{j=1}^{n}|X_{j}|d_{j}}
任意の 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} において、 ρ ( E j ) ≤ | G j | {\displaystyle \rho (E_{j})\leq |G_{j}|}
任意の X ⊆ E {\displaystyle X\subseteq E} において、 r ( X ) q ( E , F ) ≤ ρ ( X ) {\displaystyle r(X)q(E,F)\leq \rho (X)}
組合せ最適化問題の多くは、独立性システム ( E , F ) {\displaystyle (E,F)} とコスト関数 c : E → R {\displaystyle c:E\to \mathbb {R} } に対して、 ∑ e ∈ X c ( e ) {\displaystyle \sum _{e\in X}c(e)} を最大(あるいは最小)にする X ∈ F {\displaystyle X\in F} を求める最適化問題に定式化できる。
例えば、以下の中で最小全域木問題はマトロイドになるが、他はマトロイドにはならず、独立性システムとなる。
巡回セールスマン問題 - Eをグラフの辺、Fはハミルトン閉路の部分集合
ナップサック問題 - Eを荷物、Fは規定の重さを超えない荷物の組合せ
最小全域木問題 - Eはグラフの辺、Fはグラフの森の集合
(R1) r ( X ) ≤ | X | {\displaystyle r(X)\leq |X|}
(R2) X ⊆ Y ⇒ r ( X ) ≤ r ( Y ) {\displaystyle X\subseteq Y\Rightarrow r(X)\leq r(Y)}
(R3) r ( ∅ ) = 0 {\displaystyle r(\emptyset )=0}
さらに、 ( E , F ) {\displaystyle (E,F)} がマトロイドならば次の性質も持つ。
(R4) r ( X ∪ Y ) + r ( X ∩ Y ) ≤ r ( X ) + r ( Y ) {\displaystyle r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)}
(R5) r ( X ) ≤ r ( X ∪ { x } ) ≤ r ( X ) + 1 {\displaystyle r(X)\leq r(X\cup \{x\})\leq r(X)+1}
(R6) r ( X ∪ { x } ) = r ( X ∪ { y } ) = r ( X ) ⇒ r ( X ∪ { x , y } ) = r ( X ) {\displaystyle r(X\cup \{x\})=r(X\cup \{y\})=r(X)\Rightarrow r(X\cup \{x,y\})=r(X)}
特に(R4)に示されているように、階数関数が劣モジュラであることは、マトロイドの極めて重要な性質である。