階数関数

【かいすうかんすう (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}})\,$ において, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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} \,} を階数関数という. 階数関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho \,} は次の (R0)--(R3) を満たしている:

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

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

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

(R3) $\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) を満たす関数 $\rho \,$ によってマトロイドを定義することもできる.