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

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