Комбинаторные алгоритмы для программистов



             

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


Таким образом, в любой момент времени имеем разбиение
S
на непустые непересекающиеся подмножества. Рассмотрим эти операции в конце данной лекции.

С целью идентификации считаем, что каждое из непересекающихся подмножеств множества

S
имеет имя. Имя - это просто один из элементов подмножества, или, иначе, - представитель подмножества. Когда мы будем ссылаться на имя подмножества, то будем под этим подразумевать его представителя. Рассмотрим, например, множество

S = \{ 1,2,3,4,5,6,7,8,9,10,11\},

разбитое на четыре непересекающихся подмножества

 \begin{gathered} \{ 1,6,\langle 7\rangle,8,11\} \{ \langle 2\rangle \} \{ \langle 3\rangle,4,5\} \{ 9,\langle 10\rangle \} \end{gathered}

(6.1)

В каждом из подмножеств, взятый в скобки элемент является его именем. Если нам нужно найти подмножество, в котором содержится восьмерка, искомым ответом будет 7, то есть имя подмножества, содержащего восьмерку. Если нужно взять объединение подмножеств с именами 2 и 10, получим разбиение множества

S

следующего вида:

 \begin{gathered} \{ 1,6,\langle 7\rangle,8,11\} \{ \langle 3\rangle,4,5\} \{ \langle 2\rangle \} \cup \{ 9,\langle 10\rangle \} \end{gathered}

Именем множества

\{ \langle 2\rangle \}
\cup

\{ 9,\langle 10\rangle \}
может быть или 2, или 10.Предполагаем, что вначале имеется разбиение множества
S = \{s_1,s_2,\ldots,s_n \}

на

n
подмножеств, каждое из которых состоит из одного элемента

\{ \langle s_1 \rangle \} \{ \langle s_2 \rangle \}.,.\langle s_n \rangle \}

(6.2)

и имя каждого из них есть просто этот единственный элемент. Это разбиение преобразуется путем применения операций объединения вперемешку с операциями отыскания. Такая кажущаяся на первый взгляд надуманной задача чрезвычайно полезна в определенных комбинаторных алгоритмах; пример ее полезности виден в "жадном" алгоритме (лекция 16).

Для реализации операций и объединения, и отыскания опишем процедуры (операции)

UNION(x,y)
и
FIND(x)
. Процедура (операция)
UNION(x,y)
по именам двух различных подмножеств
x

и

y
образует новое подмножество, содержащее все элементы множеств
x
и
y
. Процедура (операция)
FIND(x)

выдает имя множества, содержащего

x
. Например, если нужно множество,содержащее
a
, объединить с множеством, содержащим
b
, необходимо выполнить следующую последовательность операторов:

 x \leftarrow FIND(a)\\ y \leftarrow FIND(a)\\ \text{\it if $x \ne y$ then $UNION(x,y)$}. \end{gathered}

Предположим, что мы имеем

u
операций объединения, перемешанных с
f
операциями отыскания, и что начинаем алгоритм с множества
S=\{s_1 ,s_2,\ldots,s_n \}
, которое разбито на подмножества, состоящие из одного элемента (см. 6.2.). Найдем такую структуру данных для представления непересекающихся подмножеств множества
S
, чтобы последовательность операций можно было производить эффектно.


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