付値マトロイド

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

マトロイド $${\mathbf {M} }$$ の基族 $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal B}} $上で定義された関数 $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega} $ が以下の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{(V)}} を満たすとき, $$\omega$$ を $${\mathbf {M} }$$ の付値といい, $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle ({\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凹関数の特殊な場合に相当する.