劣モジュラシステム

出典: ORWiki

【れつもじゅらしすてむ (submodular system)】

有限集合 $N\,$ の部分集合族 $\mathcal{D}\subseteq 2^{N}\,$ に関して, $\emptyset,N\in \mathcal{D}\,$ かつ $X,Y\in\mathcal{D}\Rightarrow X\cup Y, X\cap Y\in{\mathcal D}\,$ が成り立つものとする. このとき, ${\mathcal D}\,$ は分配束をなす. 劣モジュラ関数 $f:{\mathcal D}\to{\mathbf R}\,$ が $f(\emptyset)=0\,$ を満たすとき, $(\mathcal{D},f)\,$ を劣モジュラシステムという.