マトロイドとは

マトロイドとは、「独立構造」を含んだ集合の組のこと。


A) 独立集合族での定義：マトロイド({E},{I})は、
　i) \emptyset\in{I}
　ii) A\in{I} , B\subseteq A ならば、B \in {I}
　iii)A,B \in{I} で、|B|\gt|A| ならば、\exists e \in B \setminus A , A \cup \{e\} \in {I}


B) 基族での定義：マトロイド({E},{B})は、
　i) {B} \neq \emptyset
　ii) \forall B',\forall B'' \in{B} で、i \in B' \setminus B'' ならば、\exists j \in B'' \setminus B' , (B' \setminus \{i\} ) \cup \{j\} \in {I}


C) 階数関数ρ(X) での定義：マトロイド({E},{\rho})は、
　i) \rho(\emptyset) = 0
　ii) \forall X \subseteq {E} ,\rho(X) \leq |X|
　iii) \forall X,\forall Y \subset {E} で、\rho(X)+\rho(Y) \geq \rho(X \cap Y) + \rho (X \cup Y)


最後のC) のiii)を劣モジュラーであるという。