Множества и мультимножества

Не существует формального определения множества; считается что это понятие первичное и не определяется. Так, можно говорить, что множество есть объединение различных элементов, но при этом мы оставляем неопределяемыми понятия "объединение" и "элементы". Дадим следующее определение множеству: множество - это неупорядоченная совокупность различных объектов или структура данных, используемая для представления множества. Мультимножество есть объединение не обязательно различных элементов; его можно считать множеством, в котором каждому элементу поставлено в соответствие положительное целое число, называемое кратностью.

Конечное множество

$S$

будем записывать в следующем виде:

$S = \{ s_1,s_2,\ldots,s_n \},$

где

$s_1,s_2,\ldots,s_n$

- элементы

$S$

, обязательно различные! Мощность множества

$S$

обозначается как

$\left| S\right|$

, для выписанного выше множества мощность записывается так

$\left| S \right| = n$

. Если

$S$

- конечное мультимножество, то будем записывать его в следующем виде:

$S=\{\uns{s_1,s_1,\ldots,s_1}{m_1\text{раз}},\uns{s_2,s_2,\ldots,s_2}{m_2\text{ раз}}, \uns{s_3,s_3,\ldots,s_3}{m_3\text{ раз}}\} = \{ m_1 \bullet s_1, m_2 \bullet s_2,\ldots,m_n \bullet s_n \}.$

Здесь все

$s_i$

различны и

$m_i$

- кратность элемента

$s_i$

. В этом случае мощность

$S$

равна

$\left| S \right| = \sum\limits_{i = 1}^n {m_i }.$

Наиболее общими операциями на множествах и мультимножествах являются операции объединения и пересечения. Для множеств эти операции будем обозначать

$\cup$

$\cap$

, а для мультимножеств -

$\mathop \cup \limits^ +$

$\mathop \cap \limits^ +$

. Последовательное и связанное представление последовательностей можно использовать для множеств и мультимножеств очевидным способом. Индуцируя искусственный порядок элементов множества или используя собственный порядок, если он существует, можно рассматривать множество как последовательность. Аналогично, как последовательность можно рассматривать и мультимножество, или, для того чтобы сэкономить место, его можно рассматривать как последовательность пар, каждая из которых состоит из элемента и его кратности.

Как и для последовательностей, наилучший метод представления множеств или мультимножеств существенно зависит от операций, которые выполняются над ними. Предположим, например, что имеем дело с непересекающимися подмножествами множества

$S = \{ s_1,s_2,\ldots,s_n \}$

и что над ними необходимо выполнить две следующие операции: объединение двух множеств и отыскание подмножества, содержащего данное

$s_i$

.

Содержание Вперед