階数関数

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

独立集合族${\mathcal {I}}\,$をもつ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N \,} 上のマトロイド $\mathbf {M} =(N,{\mathcal {I}})\,$ において, $\rho (X)=\max\{|I|\mid I\subseteq X,\,I\in {\mathcal {I}}\}\,$ で定められる関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho:2^N\to \mathbf{Z} \,} を階数関数という. 階数関数 $\rho \,$ は次の (R0)--(R3) を満たしている:

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

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

(R2) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\subseteq Y \Rightarrow \rho(X)\leq\rho(Y) \,} ,

(R3) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \forall X,Y\subseteq N \,} : 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho(X)+\rho(Y)\geq\rho(X\cap Y)+\rho(X\cup Y) \,} .

逆に, (R0)-(R3) を満たす関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho \,} によってマトロイドを定義することもできる.