付値マトロイド

出典: ORWiki

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

マトロイド ${\mathbf M}$ の基族 ${\mathcal B}$ 上で定義された関数

ω

が以下の

(V)

を満たすとき,

ω

を ${\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}$