Множества и мультимножества
Не существует формального определения множества; считается что это понятие первичное и не определяется. Так, можно говорить, что множество есть объединение различных элементов, но при этом мы оставляем неопределяемыми понятия "объединение" и "элементы". Дадим следующее определение множеству: множество - это неупорядоченная совокупность различных объектов или структура данных, используемая для представления множества. Мультимножество есть объединение не обязательно различных элементов; его можно считать множеством, в котором каждому элементу поставлено в соответствие положительное целое число, называемое кратностью.
Конечное множество
будем записывать в следующем виде:
где
- элементы
,
обязательно различные! Мощность множества
обозначается как
, для выписанного выше множества мощность записывается так
. Если
- конечное мультимножество, то будем записывать его в следующем виде:
Здесь все
различны и
- кратность элемента
. В этом случае мощность
равна
Наиболее общими операциями на множествах и мультимножествах являются операции объединения и пересечения. Для множеств эти операции будем обозначать
и
, а для мультимножеств -
и
. Последовательное и связанное представление последовательностей можно использовать для множеств и мультимножеств очевидным способом. Индуцируя искусственный порядок элементов множества или используя собственный порядок, если он существует, можно рассматривать множество как последовательность. Аналогично, как последовательность можно рассматривать и мультимножество, или, для того чтобы сэкономить место, его можно рассматривать как последовательность пар, каждая из которых состоит из элемента и его кратности.
Как и для последовательностей, наилучший метод представления множеств или мультимножеств существенно зависит от операций, которые выполняются над ними. Предположим, например, что имеем дело с непересекающимися подмножествами множества
и что над ними необходимо выполнить две следующие операции: объединение двух множеств и отыскание подмножества, содержащего данное
.
Таким образом, в любой момент времени имеем разбиение
на непустые непересекающиеся подмножества. Рассмотрим эти операции в конце данной лекции.
С целью идентификации считаем, что каждое из непересекающихся подмножеств множества
имеет имя. Имя - это просто один из элементов подмножества, или, иначе, - представитель подмножества. Когда мы будем ссылаться на имя подмножества, то будем под этим подразумевать его представителя. Рассмотрим, например, множество
разбитое на четыре непересекающихся подмножества
В каждом из подмножеств, взятый в скобки элемент является его именем. Если нам нужно найти подмножество, в котором содержится восьмерка, искомым ответом будет 7, то есть имя подмножества, содержащего восьмерку. Если нужно взять объединение подмножеств с именами 2 и 10, получим разбиение множества
следующего вида:
Именем множества
может быть или 2, или 10.Предполагаем, что вначале имеется разбиение множества
на
подмножеств, каждое из которых состоит из одного элемента
и имя каждого из них есть просто этот единственный элемент. Это разбиение преобразуется путем применения операций объединения вперемешку с операциями отыскания. Такая кажущаяся на первый взгляд надуманной задача чрезвычайно полезна в определенных комбинаторных алгоритмах; пример ее полезности виден в "жадном" алгоритме (лекция 16).
Для реализации операций и объединения, и отыскания опишем процедуры (операции)
и
. Процедура (операция)
по именам двух различных подмножеств
и
образует новое подмножество, содержащее все элементы множеств
и
. Процедура (операция)
выдает имя множества, содержащего
. Например, если нужно множество,содержащее
, объединить с множеством, содержащим
, необходимо выполнить следующую последовательность операторов:
Предположим, что мы имеем
операций объединения, перемешанных с
операциями отыскания, и что начинаем алгоритм с множества
, которое разбито на подмножества, состоящие из одного элемента (см. 6.2.). Найдем такую структуру данных для представления непересекающихся подмножеств множества
, чтобы последовательность операций можно было производить эффектно.
Такой структурой данных является представление в виде леса с указателями отца, как показано на рис. 4.5 лекции 4. Каждый элемент
множества будет узлом леса, а отцом его будет элемент из того же подмножества, что и
. Если элемент не имеет отца, то есть является корнем, то он будет именем своего подмножества. В соответствии с этим разбиение 5.1 может быть представлено так:
Рис. 6.1. Представление разбиения
При таком представлении процедура (операция)
состоит в переходах по указателям отцов от
до корня, то есть имени, его подмножества. Процедура (операция)
состоит в связывании вместе некоторым образом деревьев, имеющих корни
и
. Например, такую связь можно осуществить, сделав
отцом
.
После
операций объединения наибольшее из возможных подмножеств, получающихся в результате разбиения
, будет содержать
элементов. Поскольку каждое объединение уменьшает число подмножеств на единицу, последовательность операций может содержать не более
объединений, откуда
. Так как каждая операция объединения изменяет имя подмножества, содержащего некоторые элементы, можно считать, что каждому объединению предшествует по крайней мере одно отыскание, в связи с чем естественно предположить, что
. Выясним, насколько эффективно можно выполнить последовательность из
операций объединения, перемешанных с
операциями отыскания. Время, требуемое на операции объединения, очевидно, пропорционально
, потому что необходимая для каждой операции объединения переделка некоторых указателей требует фиксированного количества работы. Поэтому сосредоточим свое внимание на времени, требуемом для
операций отыскания.
Если операция
выполняется путем назначения
отцом
, то после
операций объединения может получиться лес, показанный ниже.
В этом случае, если
операций отыскания выполняются после всех операций объединения и каждый поиск начинается внизу цепи из
элементов множества, то ясно, что время, требуемое на операции отыскания, будет пропорционально
. Очевидно, оно не может быть больше, чем константа, умноженная на
.Можно существенно уменьшить эту оценку.
Содержание раздела
