階数関数とは？

用語解説|動画|文献|全文検索

Weblio 辞書 > 学問 > OR事典 > 階数関数の意味・解説

OR事典

階数関数

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

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

(R1) $\forall X\subseteq N \,$ : $\rho(X)\leq |X| \,$ ,

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

(R3) $\forall X,Y\subseteq N \,$ : $\rho(X)+\rho(Y)\geq\rho(X\cap Y)+\rho(X\cup Y) \,$ .

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

「OR事典」の他の用語

グラフ･ネットワーク：

辺連結度連結度連結度増大問題配送計画問題階数関数離散凸解析離散分離定理

索引トップ用語の索引ランキングカテゴリー

>> 「階数関数」を解説文に含む用語の一覧

>> 「階数関数」を含む用語の索引

階数関数のページへのリンク

「階数関数」の関連用語

共通マトロイド問題

OR事典

96% |||||

劣モジュラ関数

OR事典

54% |||||

除数法

OR事典

50% |||||

マトロイド

OR事典

32% |||||

劣モジュラ最適化

OR事典

14% |||||

階数関数のお隣キーワード

階数関数

検索ランキング

▼TOP10

▼11～20

▼21～30

1		沓名環希
2		出不精
3		リーガル・ハイ
4		クルーゾン症候群
5		捗る
6		TPP
7		薩長同盟
8		アセスメント
9		ダイバーシティ
10		タカラダニ

▼TOP10

▼11～20

▼21～30

11		ピーター・カール・ファベルジェ
12		福利厚生
13		田島優成
14		聖武天皇
15		thee michelle gun elephant
16		赤口
17		未満
18		注意喚起
19		こざとへん
20		遡及

▼TOP10

▼11～20

▼21～30

21		熊本市交通局1080形電車
22		初夏
23		リツイート
24		あざとい
25		ご指導ご鞭撻
26		共益費
27		法人
28		言葉
29		壮行会
30		火曜サプライズ