劣モジュラ関数

単調関数

劣モジュラ関数 ${\displaystyle f}$ が全ての ${\displaystyle S\subseteq T}$ に対して ${\displaystyle f(S)\leq f(T)}$ を満たすとき単調と呼ぶ。以下、単調関数の例である。

線形関数

${\displaystyle f(S)=\sum _{i\in S}w_{i}}$という形で表せる全ての集合関数。

この場合、${\displaystyle \forall i,w_{i}\geq 0}$なら単調。

バジェット加法型関数

${\displaystyle f(S)=\min \left(B,\sum _{i\in S}w_{i}\right)}$ という形で表せる関数のうち、${\displaystyle w_{i}\geq 0,B\geq 0}$を満たす関数。

被覆関数

集合${\displaystyle \Omega =\{E_{1},E_{2},\ldots ,E_{n}\}}$が何らかの元集合${\displaystyle \Omega '}$の部分集合族であるとする。これに対して、${\displaystyle f(S)=|\bigcup _{E_{i}\in S}E_{i}|}$ for ${\displaystyle S\subseteq \Omega }$ という形で表せる関数。

エントロピー関数（${\displaystyle \Omega }$は確率変数の集合）

任意の ${\displaystyle S\subseteq \Omega }$ に対して、${\displaystyle S}$ のエントロピーを返すような関数 ${\displaystyle H(S)}$。

マトロイド階数関数（${\displaystyle \Omega }$ はマトロイドの台集合）

マトロイドの階数関数は劣モジュラ関数。

非単調関数

単調関数でない劣モジュラ関数。

対称な劣モジュラ関数

任意の ${\displaystyle S\subseteq \Omega }$ に対して ${\displaystyle f(S)=f(\Omega -S)}$ を満たす劣モジュラ関数を対称であるという。 以下、対称な劣モジュラ関数の例である。

カット関数（${\displaystyle \Omega }$ はグラフの頂点集合）

任意の ${\displaystyle S\subseteq \Omega }$に対して、${\displaystyle f(S)}$ が、${\displaystyle e=(u,v),u\in S,v\in \Omega -S}$ を満たす辺 ${\displaystyle e}$ の数を返す関数となるとき ${\displaystyle f}$ をカット関数と呼ぶ。

上記の条件を満たす辺重みの合計を返すような関数として定義する場合がある。 辺重み無しの場合を上記で考える場合、重み 1: 辺が存在する、重み 0: 辺が存在することを表す。

相互情報量（${\displaystyle \Omega }$ は確率変数の集合）

任意の ${\displaystyle S\subseteq \Omega }$ に対して、${\displaystyle f(S)=I(S;\Omega -S)}$（${\displaystyle I(S;\Omega )}$は相互情報量）となる関数。

非対称な劣モジュラ関数

単調でも対称でもない劣モジュラ関数。 以下、非対称な劣モジュラ関数の例である。

有向グラフのカット関数（${\displaystyle \Omega }$ は有向グラフの頂点集合）

この集合 ${\displaystyle \Omega }$ に対して定義されたカット関数は非対称な劣モジュラ関数である。

出る辺に関するカット関数と、入る辺に関するカット関数は対称でないことからこのことが分かる。

ロバース拡張

ベクトル ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$ であって、各要素が ${\displaystyle 0\leq x_{i}\leq 1}$ となるものに対し、${\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i:x_{i}\geq \lambda \}))}$ で定義される関数を集合関数 ${\displaystyle f}$ のロバース拡張（Lovász extension）という。この関数は閉区間 ${\displaystyle [0,1]}$ 上の一様分布から ${\displaystyle \lambda }$ 以上のものを選んだ時の期待値を返すような関数になっており、この関数は凸関数になる。