ランク、階数関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
独立性システム (E,F) の階数 (rank) 関数 r : 2 E → R {\displaystyle r:2^{E}\to \mathbb {R} } は、 X ⊆ E {\displaystyle X\subseteq E} に対して r ( X ) := max { | Y | : Y ⊆ X , Y ∈ F } {\displaystyle r(X):=\max\{|Y|:Y\subseteq X,Y\in F\}} と定義される。マトロイドならば、公理(A3) から E {\displaystyle E} の部分集合 X {\displaystyle X} に対して X {\displaystyle X} のどの基も元数は等しいため、階数関数を X {\displaystyle X} の基の大きさと定義しても構わない。 例えば、E={1,2,3},F={{},{1},{2},{1,2}}というマトロイドならばr({1})=1,r({1,2})=2,r({1,2,3})=2,r({1,3})=1等となる。 独立性システム ( E , F ) {\displaystyle (E,F)} の階数関数 r : 2 E → R {\displaystyle r:2^{E}\to \mathbb {R} } は任意の X , Y ⊆ E {\displaystyle X,Y\subseteq E} と x , y ∈ E {\displaystyle x,y\in E} について次の性質を持つ。 (R1) r ( X ) ≤ | X | {\displaystyle r(X)\leq |X|} (R2) X ⊆ Y ⇒ r ( X ) ≤ r ( Y ) {\displaystyle X\subseteq Y\Rightarrow r(X)\leq r(Y)} (R3) r ( ∅ ) = 0 {\displaystyle r(\emptyset )=0} さらに、 ( E , F ) {\displaystyle (E,F)} がマトロイドならば次の性質も持つ。 (R4) r ( X ∪ Y ) + r ( X ∩ Y ) ≤ r ( X ) + r ( Y ) {\displaystyle r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)} (R5) r ( X ) ≤ r ( X ∪ { x } ) ≤ r ( X ) + 1 {\displaystyle r(X)\leq r(X\cup \{x\})\leq r(X)+1} (R6) r ( X ∪ { x } ) = r ( X ∪ { y } ) = r ( X ) ⇒ r ( X ∪ { x , y } ) = r ( X ) {\displaystyle r(X\cup \{x\})=r(X\cup \{y\})=r(X)\Rightarrow r(X\cup \{x,y\})=r(X)} 特に(R4)に示されているように、階数関数が劣モジュラであることは、マトロイドの極めて重要な性質である。
※この「ランク、階数関数」の解説は、「マトロイド」の解説の一部です。
「ランク、階数関数」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
- ランク、階数関数のページへのリンク
