「劣モジュラ関数」の版間の差分

2008年11月14日 (金) 09:44時点における最新版

【れつもじゅらかんすう (submodular function)】

分配束 ${\mathcal {D}}\,$ 上の関数 $f\,$ が, 任意の $X,Y\in {\mathcal {D}}\,$ に対して

$f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)$

を満たすとき, $f\,$ を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である.

@@ 1行目: / 1行目: @@
 '''【れつもじゅらかんすう (submodular function)】'''
-分配束 <math>{\cal D}\,</math> 上の関数 <math>f\,</math> が, 任意の <math>X,Y\in{\cal D}\,</math> に対して
+分配束 <math>{\mathcal D}\,</math> 上の関数 <math>f\,</math> が, 任意の <math>X,Y\in{\mathcal D}\,</math> に対して
-\[
+<center>
-f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)
+<math>f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)</math>
-\]
+</center>
 を満たすとき, <math>f\,</math> を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である.
+[[Category:グラフ･ネットワーク|れつもじゅらかんすう]]