付値マトロイド

【ふちまとろいど (valuated matroid)】

マトロイド $${\mathbf {M} }$$ の基族 $${\mathcal {B}}$$上で定義された関数 $$\omega$$ が以下の${\mbox{(V)}}$を満たすとき, $$\omega$$ を $${\mathbf {M} }$$ の付値といい, $$({\mathbf {M} },\omega )$$ を 付値マトロイドという.

${\begin{array}{l}{\mbox{(V)}}\quad B,F\in {\mathcal {B}},i\in B\backslash F\Rightarrow \exists j\in F\backslash B:\\\qquad \quad \omega ((B\backslash \{i\})\cup \{j\})+\omega ((F\cup \{i\})\backslash \{j\})\\\qquad \qquad \qquad \geq \omega (B)+\omega (F).\end{array}}$

マトロイドの付値は, 離散凸解析におけるM凹関数の特殊な場合に相当する.