ランク商
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
下方ランク (lower rank) 関数 ρ ( X ) {\displaystyle \rho (X)} を X {\displaystyle X} に含まれる基の最小元数とする。つまり、 ρ ( X ) := min { | Y | : Y ⊆ X , Y ∈ F {\displaystyle \rho (X):=\min\{|Y|:Y\subseteq X,Y\in F} かつ ∀ x ∈ X ∖ Y {\displaystyle \forall {x}\in X\setminus Y} に対し Y ∪ { x } ∉ F } {\displaystyle Y\cup \{x\}\not \in F\}} と定義する。すると、ランク商 (rank quotient) は次のように定義される。 q ( E , F ) := min X ⊆ E ρ ( X ) r ( X ) {\displaystyle q(E,F):=\min _{X\subseteq {E}}{\frac {\rho (X)}{r(X)}}} マトロイドのとき q ( E , F ) = 1 {\displaystyle q(E,F)=1} である。独立性システムのとき q ( E , F ) ≤ 1 {\displaystyle q(E,F)\leq 1} であり、 A ∈ F , b ∈ E {\displaystyle A\in F,b\in E} に対して A ∪ { b } {\displaystyle A\cup \{b\}} が高々 p {\displaystyle p} 個しかサーキットを持たないならば 1 / p ≤ q ( E , F ) {\displaystyle 1/p\leq q(E,F)} であることが知られているのでランク商を見積もることが可能である。
※この「ランク商」の解説は、「マトロイド」の解説の一部です。
「ランク商」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
- ランク商のページへのリンク
