階数関数

出典: ORWiki

【かいすうかんすう (rank function)】

独立集合族\mathcal{I} \,をもつN \,上のマトロイド \mathbf{M}=(N,\mathcal{I}) \, において, \rho(X)=\max\{|I|\mid I\subseteq X,\, I \in\mathcal{I}\} \, で定められる関数 \rho:2^N\to \mathbf{Z} \, を階数関数という. 階数関数 \rho \, は次の (R0)--(R3) を満たしている:

(R0) \rho(\emptyset)=0 \,,

(R1) \forall X\subseteq N \,: \rho(X)\leq |X| \,,

(R2) X\subseteq Y \Rightarrow \rho(X)\leq\rho(Y) \,,

(R3) \forall X,Y\subseteq N \,: \rho(X)+\rho(Y)\geq\rho(X\cap Y)+\rho(X\cup Y) \,.

逆に, (R0)-(R3) を満たす関数 \rho \, によってマトロイドを定義することもできる.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E9%9A%8E%E6%95%B0%E9%96%A2%E6%95%B0" より作成