付値マトロイドのソースを表示

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

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


<math>\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}</math>
</center><br><br>

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