付値マトロイド

【ふちまとろいど (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凹関数の特殊な場合に相当する.