階数関数のソースを表示

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

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

(R0) <math>\rho(\emptyset)=0 \,</math>,

(R1) <math>\forall X\subseteq N \,</math>: <math>\rho(X)\leq |X| \,</math>,

(R2) <math>X\subseteq Y \Rightarrow \rho(X)\leq\rho(Y) \,</math>,

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

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

[[Category:グラフ･ネットワーク|かいすうかんすう]]