WikiDer > Функция субаддитивного набора - Википедия

В математике функция субаддитивного набора это установить функцию чье значение неформально имеет свойство, заключающееся в том, что значение функции на объединении двух наборов является не более чем суммой значений функции на каждом из наборов. Это тематически связано с субаддитивность свойство вещественных функций.

Определение

Позволять ${ displaystyle Omega}$ быть набор и ${ displaystyle f двоеточие 2 ^ { Omega} rightarrow mathbb {R}}$ быть установить функцию, куда ${ displaystyle 2 ^ { Omega}}$ обозначает набор мощности из ${ displaystyle Omega}$. Функция ж является субаддитив если для каждого подмножества ${ displaystyle S}$ и ${ displaystyle T}$ из ${ displaystyle Omega}$, у нас есть ${ Displaystyle е (S) + е (T) geq f (S чашка T)}$.^[1][2]

Примеры субаддитивных функций

Каждый неотрицательный функция субмодульного набора субаддитивен (семейство неотрицательных субмодулярных функций строго содержится в семействе субаддитивных функций).

Функция, подсчитывающая количество наборов, необходимых для крышка данный набор субаддитивен. Позволять ${ Displaystyle T_ {1}, dotsc, T_ {m} substeq Omega}$ такой, что ${ Displaystyle чашка _ {я = 1} ^ {m} T_ {i} = Omega}$. Определять ${ displaystyle f}$ как минимальное количество подмножеств, необходимое для покрытия данного набора. Формально, ${ Displaystyle f (S)}$ это минимальное количество ${ displaystyle t}$ такие, что есть множества ${ displaystyle T_ {i_ {1}}, dotsc, T_ {i_ {t}}}$ удовлетворение ${ Displaystyle S substeq чашка _ {j = 1} ^ {t} T_ {i_ {j}}}$. потом ${ displaystyle f}$ является субаддитивным.

В максимум из аддитивные функции множества является субаддитивным (вдвойне минимум аддитивных функций супераддитив). Формально для каждого ${ Displaystyle я в {1, dotsc, м }}$, позволять ${ displaystyle a_ {i} двоеточие Omega to mathbb {R} _ {+}}$ быть аддитивными функциями множества. потом ${ Displaystyle е (S) = макс _ {я} влево ( сумма _ {х в S} а_ {я} (х) вправо)}$ является функцией субаддитивного набора.

Дробно субаддитивные функции множества являются обобщением субмодульных функций и частным случаем субаддитивных функций. Субаддитивная функция ${ displaystyle f}$ кроме того, является дробно субаддитивным, если он удовлетворяет следующему определению.^[1] Для каждого ${ Displaystyle S substeq Omega}$, каждый ${ Displaystyle X_ {1}, dotsc, X_ {n} substeq Omega}$, и каждый ${ displaystyle alpha _ {1}, dotsc, alpha _ {n} in [0,1]}$, если ${ displaystyle 1_ {S} leq sum _ {i = 1} ^ {n} alpha _ {i} 1_ {X_ {i}}}$, тогда ${ Displaystyle е (S) leq сумма _ {я = 1} ^ {n} альфа _ {я} f (X_ {i})}$. Набор дробно субаддитивных функций равен набору функций, которые можно выразить как максимум аддитивных функций, как в примере в предыдущем абзаце.^[1]

Смотрите также

• Функция субмодульного набора
• Полезные функции для неделимых товаров

Цитаты