付値マトロイド

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

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