08. Цепи и антицепи в частично-упорядоченном множестве. Теорема Дилворта. Алгоритм разбиения частично-упорядоченного множества на минимальное число цепей
Пусть частично упорядоченное множество (сокращенно: ЧУМ). Это значит, что задано некоторое подмножество
Такое, что выполнены следующие условия: для всякого
обязательно
(это, так называемая, Рефлексивность); если
и
, то обязательно
(это, так называемая, Транзитивность); если
и
, то обязательно
(это, так называемая, Антисимметричность). Само множество
называется Частичным порядком. На одном и том же множестве
может быть много частичных порядков.
Если частичный порядок таков, что для любых двух элементов
либо
либо
, то говорят, что множество
Является Цепью; если же частичный порядок
таков, что для любых различных
ни одно из включений -
,
- не выполняется, то говорят, что
является Антицепью. Очевидно, что если
- ЧУМ, то и любое подмножество в
является частично-упорядоченным. По определению по-лагают, что всякое одноэлементное подмножество является одновременно и цепью и анти-цепью.
Рассмотрим пример. Пусть (это означает, что элемента-ми множества
являются наборы указанных натуральных чисел). Определим частичный по-рядок
, объявив, что
, если
. Нетрудно проверить, что это - действительно частичный порядоок. В этом частичном порядке
- цепь, а
- анти-цепь.
Существует классическая задача: Разбить ЧУМ На минимальное число цепей. Это значит надо найти в
цепи
такие, что у любых двух из них нет общих элементов, что их объединение совпадает с
и при всем при этом число
минимально возможное. Имеется по этому поводу классическая Теорема Дилворта, утверждающая следующее:
Минимальное число цепей, на которые можно разбить данное частично упорядоченное множество, равно максимальному числу элементов, составляющих антицепь.
Мы приведем сейчас алгоритм, позволяющий отыскать одно из возможных Минималь-ных цепных разбиений ЧУМа, т. е. найти набор попарно неперсекающихся цепей , объ-единение которых совпадает с
и при этом
миниально возможное.
Для удобства мы будем в будущем выражать тот факт, что в ЧУМе
сим-волом
или просто
, причем если к тому же
, то будем писать
.
Итак, пусть - ЧУМ; требуется найти минимальное цепное разбиение.
Шаг 0. Построим двудольный граф следующим образом. Положим
; это означает, что в графе будет ровно
вершин. Далее, ребра в графе будут иметь лишь следующий вид:
, причем
тогда и только тогда, когда
.
Шаг 1. Выберем в построенном графе G наибольшее паросочетание . Для каждого ребра
фиксируем пару элементов
, составляющих, естественно, цепь, так как по определению ребер в G обязательно
.
Шаг 2. Многократно используя свойство транзитивности частичного порядка, объеди-ним двухэлементные цепи из предыдущего шага в неудлиняемые цепи. В результате получится некоторый набор цепей в данном множестве, причем, как нетрудно проверить, эти це-пи попарно общих элементов не имеют. Добавив к этому списку цепей одноэлементные цепи, полученные из всех элементов данного множества, не вошедших в объединение
, мы получим некоторое цепное разбиение данного множества
. Можно доказать, что Это цепное разбиение минимально.
ПРИМЕР. Пусть множество состоит из следующих наборов чисел (каждый набор заключен в круглые скобки):
Æ (пустое множество; это - тоже лемент из
);
(1),
(2),
(3),
(4),
(1,2),
(1,3),
(1,4),
(2,3),
(2,4),
(3,4),
(1,2,3),
(1,2,4),
(1,3,4),
(2,3,4),
(1,2,3,4).
Частичный порядок на будет считаться по включению:
тогда и только тог-да, когда
.
Найдем минимальное цепное разбиение этого множества. Вначале построим двудольный граф для данной задачи. Вот его матрица:
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 | |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
3 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
13 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
14 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
15 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
16 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Найдем наибольшее паросочетание:
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
100 |
111 |
122 |
133 |
144 |
155 |
166 | ||
Х |
1 | ||||||||||||||||
2 |
Х |
Х |
Х |
Х |
Х |
1 |
Х |
Х |
Х |
Х | |||||||
3 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
1 |
Х |
Х | |||||||
4 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
1 |
Х | |||||||
5 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
1 |
Х |
Х | |||||||
6 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
1 |
Х |
Х |
12 | ||
7 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
1 |
Х |
14 | ||
8 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
1 |
Х |
134 | ||
9 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
1 |
15 | ||
10 11110 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
1 |
16 | ||
11 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
- | |||
12 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
- | |
13 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
- | |
14 4 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
- | |
15 5 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
- | |
16 6 |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
Х |
- |
7 |
6 |
11 |
11 |
11 |
Следовательно, наибольшее паросочетание таково:
.
Отсюда - первые «двуэлементные цепочки»:
Используя транзитивность частичного порядка, склеим некоторые из этих цепочек:
Поскольку не осталось элементов данного множества вне указанных цепей, этот набор цепей и является минимальным цепным разбиением.
< Предыдущая | Следующая > |
---|