ポリマトロイド

提供:ORWiki
移動: 案内, 検索

【ぽりまとろいど (polymatroid)】

有限集合 N\, と以下の条件 (P0)--(P2) を満たす関数 \rho:2^N\to{\mathbf R}\, の組 (N,\rho)\, をポリマトロイドという.
(P0) \rho(\emptyset)=0\,.
(P1) X\subseteq Y \Rightarrow \rho(X)\leq\rho(Y)\,.
(P2) \forall X,Y\subseteq N\,: \rho(X)+\rho(Y)\geq\rho(X\cap Y)+\rho(X\cup Y)\,.

個人用ツール