Разбиения множеств

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

Начнем с массива Parent, в котором под каждый элемент множества, с которым мы собираемся работать, отведена одна ячейка. Вначале мы полагаем значения всех элементов равными -1. Знак - означает здесь, что каждый элемент является корнем разбиения, а абсолютное значение 1 - что соответствующая часть разбиения состоит из одного элемента. При работе алгоритма значения ячеек будут меняться, и, скажем, значение -7 указывает на то, что соответствующий элемент является корнем части, состоящей из семи элементов. При добавлении элемента к части значение соответствующей ему ячейки добавляется к значению корня. Если, к примеру, пятый элемент добавляется к части, корень которой - восьмой элемент массива Parent, то в пятую ячейку записывается значение 8, а отрицательное содержимое восьмой ячейки будет увеличено по абсолютной величине, чтобы указать на появление дополнительного элемента. При объединении двух частей разбиения происходит изменение только корневых ячеек этих частей, поэтому каждый элемент массива ссылается на своего непосредственного предка.

УПОРЯДОЧЕНИЕ [ordering] — такое множество, элементы которого подчинены правилу предшествования, или следования. Натуральный ряд чисел — пример множества, упорядоченного по величине.

Частично упорядоченное множество — математическое понятие, которое формализует интуитивные идеи упорядочивания, расположения в определенной последовательности и т. п. Неформально говоря, множество частично упорядочено, если указано, какие элементы следуют (больше и т. п.) за какими. При этом в общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».

В качестве абстрактного примера можно привести совокупность подмножеств множества из трех элементов {x,y,z}, упорядоченное по отношению включения.

В качестве примера строгого частичного порядка «из жизни» можно привести множество людей, упорядоченное по отношению «быть предком».

14. Прямое произведение. Проекция множества.

Прямое или декартово произведение множеств — множество, элементами которого являются все возможные упорядоченные пары элементов исходных двух множеств. Данное понятие употребляется не только в теории множеств, но также в алгебре, топологии и прочих разделах математики благодаря тому, что прямое произведение часто наследует структуры (алгебраические, топологические и т. д.), существующие на перемножаемых множествах.