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

Следовательно, наибольшее паросочетание таково:

.

Отсюда - первые «двуэлементные цепочки»:

Используя транзитивность частичного порядка, склеим некоторые из этих цепочек:

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

© 2011-2024 Контрольные работы по математике и другим предметам!