「デルタマトロイド」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
("デルタマトロイド" を保護しました。 [edit=sysop:move=sysop])
 
10行目: 10行目:
  
 
デルタマトロイドの実行可能集合族 <math>{\mathcal F}\,</math> 上では, 貪欲アルゴリズムによって線形目的関数の最適化が可能である.
 
デルタマトロイドの実行可能集合族 <math>{\mathcal F}\,</math> 上では, 貪欲アルゴリズムによって線形目的関数の最適化が可能である.
 +
 +
[[Category:グラフ・ネットワーク|でるたまとろいど]]

2008年11月13日 (木) 12:40時点における最新版

【でるたまとろいど (delta-matroid)】

有限集合 において, 部分集合の対称差を取る二項演算を で表す. 部分集合族 が, 以下の (D0)--(D1) を満たすとき, をデルタマトロイドという.

(D0)  .
(D1)  ,: .

デルタマトロイドの実行可能集合族 上では, 貪欲アルゴリズムによって線形目的関数の最適化が可能である.