付値マトロイド

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

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

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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凹関数の特殊な場合に相当する.