劣モジュラ関数
任意の S ⊆ Ω {\displaystyle S\subseteq \Omega } に対して、 f ( S ) {\displaystyle f(S)} が、 e = ( u , v ) , u ∈ S , v ∈ Ω − S {\displaystyle e=(u,v),u\in S,v\in \Omega -S} を満たす辺 e {\displaystyle e} の数を返す関数となるとき f {\displaystyle f} をカット関数と呼ぶ。
上記の条件を満たす辺重みの合計を返すような関数として定義する場合がある。 辺重み無しの場合を上記で考える場合、重み 1: 辺が存在する、重み 0: 辺が存在することを表す。
任意の集合 X ⊆ Ω {\displaystyle X\subseteq \Omega } と x 1 , x 2 ∈ Ω ∖ X , x 1 ≠ x 2 {\displaystyle x_{1},x_{2}\in \Omega \backslash X,x_{1}\neq x_{2}} に対して、 f ( X ∪ { x 1 } ) + f ( X ∪ { x 2 } ) ≥ f ( X ∪ { x 1 , x 2 } ) + f ( X ) {\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)}
非負の劣モジュラ関数は劣加法的であるが、劣加法的関数が必ずしも劣モジュラとは限らない。