「階数関数」の版間の差分
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
'''【かいすうかんすう (rank function)】''' | '''【かいすうかんすう (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> によってマトロイドを定義することもできる. | + | 独立集合族<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:グラフ･ネットワーク|かいすうかんすう]] | ||
2008年11月7日 (金) 14:56時点における最新版
【かいすうかんすう (rank function)】
独立集合族をもつ上のマトロイド 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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} \,} を階数関数という. 階数関数 は次の (R0)--(R3) を満たしている:
(R0) ,
(R1) : ,
(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 \,} によってマトロイドを定義することもできる.