劣モジュラ関数
マトロイドの階数関数は劣モジュラ関数。
劣モジュラ関数 f {\displaystyle f} が全ての S ⊆ T {\displaystyle S\subseteq T} に対して f ( S ) ≤ f ( T ) {\displaystyle f(S)\leq f(T)} を満たすとき単調と呼ぶ。 以下、単調関数の例である。
f ( S ) = ∑ i ∈ S w i {\displaystyle f(S)=\sum _{i\in S}w_{i}} という形で表せる全ての集合関数。
この場合、 ∀ i , w i ≥ 0 {\displaystyle \forall i,w_{i}\geq 0} なら単調。