付値マトロイド

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

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

\[ \begin{array}{l} \mbox{(V)} \quad B, F\in {\cal B}, i \in B \backslash F \Rightarrow \exists j \in F \backslash B: \\ \hspace*{10mm} \omega((B\backslash\{i\})\cup\{j\})+\omega((F\cup\{i\})\backslash\{j\}) \\ \hspace*{20mm} \geq \omega(B)+\omega(F). \end{array} \]

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