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

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