Аддитивные сет-функции и меры

Сет-функция — действительная числовая функция <math> f\mbox{: } 2^\Omega \rightarrow \ \mathbb{R} </math> , определенная на <math> 2^\Omega\ </math> — множестве всех подмножеств некоторого произвольного конечного множества <math> \Omega\ </math> измеримого пространства <math> (\Omega, \mathcal{F}) </math> и принимающая свои значения на числовой оси <math>\mathbb{R}</math>.

Аддитивная сет-функция — сет-функция, для которой выполняется равенство:

<math> f(x \cup y) + f(x \cap y)=f(x)+f(y)</math>

для любых подмножеств <math> x \subseteq \Omega </math> и <math> y \subseteq \Omega </math>.

Мера — аддитивная сет-функция, для которой верно: <math> f(\emptyset)=0</math>.

Значение любой меры <math> f\ </math> на произвольном подмножестве <math> x \subseteq \Omega </math> можно представить в виде суммы её значений на моноплетах <math> \{\omega\}: \omega \in x </math>:

<math> f(x) = \sum_{\omega \in x} f(\{\omega\}) \mbox{, } x \subseteq \Omega </math>.

Считается, что <math> \sum_{\omega \in \emptyset} f(\{\omega\})=0, \prod_{\omega \in \emptyset}f(\{\omega\})=1 </math>.

Библиография

• Lovasz L. (1983) Submodular functions and convexity. In: A. Bachem, M. Grotschel, and B.Korte, editors, Mathematical Programming — The State of the Art}, Springer-Veriag, 235—257.
• Fujishige S. (1984) Theory of submodular programs, A Fenchel-type min-max theorem and subgradients of submodular functions, Mathematical Programming, 29, 142—155.
• Foldes Stephan, Hammer Peter L. (2002) Submodularity, Supermodularity, Higher Order Monotonicities. Rutcor Research

Report, 10-2002, March, 2002.

• Hammer, P.L., and S.Rudeanu} (1968) Boolean Methods in Operation Research and Relared Areas, Springer-Verlag, Berlin, Heidelberg, New York.

Отрывок, характеризующий Аддитивные сет-функции и меры

Наложенные верхом возы с домашней посудой, стульями, шкафчиками то и дело выезжали из ворот домов и ехали по улицам. В соседнем доме Ферапонтова стояли повозки и, прощаясь, выли и приговаривали бабы. Дворняжка собака, лая, вертелась перед заложенными лошадьми.
Алпатыч более поспешным шагом, чем он ходил обыкновенно, вошел во двор и прямо пошел под сарай к своим лошадям и повозке. Кучер спал; он разбудил его, велел закладывать и вошел в сени. В хозяйской горнице слышался детский плач, надрывающиеся рыдания женщины и гневный, хриплый крик Ферапонтова. Кухарка, как испуганная курица, встрепыхалась в сенях, как только вошел Алпатыч.
– До смерти убил – хозяйку бил!.. Так бил, так волочил!..
– За что? – спросил Алпатыч.
– Ехать просилась. Дело женское! Увези ты, говорит, меня, не погуби ты меня с малыми детьми; народ, говорит, весь уехал, что, говорит, мы то? Как зачал бить. Так бил, так волочил!
Алпатыч как бы одобрительно кивнул головой на эти слова и, не желая более ничего знать, подошел к противоположной – хозяйской двери горницы, в которой оставались его покупки.
– Злодей ты, губитель, – прокричала в это время худая, бледная женщина с ребенком на руках и с сорванным с головы платком, вырываясь из дверей и сбегая по лестнице на двор. Ферапонтов вышел за ней и, увидав Алпатыча, оправил жилет, волосы, зевнул и вошел в горницу за Алпатычем.
– Аль уж ехать хочешь? – спросил он.