Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Цепи и антицепи в частично-упорядоченном множестве. Теорема Дилворта. Алгоритм разбиения частично-упорядоченного множества на минимальное число цепей.




Пусть частично упорядоченное множество (сокращенно: ЧУМ). Это значит, что задано некоторое подмножество такое, что выполнены следующие условия: для всякого обязательно (это, так называемая, рефлексивность); если и , то обязательно (это, так называемая, транзитивность); если и , то обязательно (это, так называемая, антисимметричность). Само множество называется частичным порядком. На одном и том же множестве может быть много частичных порядков.

Если частичный порядок таков, что для любых двух элементов либо либо , то говорят, что множество является цепью; если же частичный порядок таков, что для любых различных ни одно из включений - , - не выполняется, то говорят, что является антицепью. Очевидно, что если - ЧУМ, то и любое подмножество в является частично-упорядоченным. По определению по-лагают, что всякое одноэлементное подмножество является одновременно и цепью и анти-цепью.

Рассмотрим пример. Пусть (это означает, что элемента-ми множества являются наборы указанных натуральных чисел). Определим частичный по-рядок , объявив, что , если . Нетрудно проверить, что это - действительно частичный порядоок. В этом частичном порядке - цепь, а - анти-цепь.

Существует классическая задача: разбить ЧУМ на минимальное число цепей. Это значит надо найти в цепи такие, что у любых двух из них нет общих элементов, что их объединение совпадает с и при всем при этом число минимально возможное. Имеется по этому поводу классическая теорема Дилворта, утверждающая следующее:

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

Мы приведем сейчас алгоритм, позволяющий отыскать одно из возможных минималь-ных цепных разбиений ЧУМа, т.е. найти набор попарно неперсекающихся цепей , объ-единение которых совпадает с и при этом миниально возможное.

Для удобства мы будем в будущем выражать тот факт, что в ЧУМе сим-волом или просто , причем если к тому же , то будем писать .

Итак, пусть - ЧУМ; требуется найти минимальное цепное разбиение.

Шаг 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).

Частичный порядок на будет считаться по включению: тогда и только тог-да, когда .

Найдем минимальное цепное разбиение этого множества. Вначале построим двудольный граф для данной задачи. Вот его матрица:

 

 

 

 

Найдем наибольшее паросочетание:

 

   
  х                              
х х х х х     х х х       х    
х х х х х   х х   х     х      
х х х х х х   х   х   х        
х х х х х х х х     х          
х х х х х х х х х х х   х х  
х х х х х х х х х х х   х х  
х х х х х х х х х х х х   х  
х х х х х х х х х х х   х х  
10 11110 х х х х х х х х х х х х   х  
х х х х х х х х х х х х х       -
х х х х х х х х х х х х х х х   -
х х х х х х х х х х х х х х х   -
14 4 х х х х х х х х х х х х х х х   -
15 5 х х х х х х х х х х х х х х х   -
16 6 х х х х х х х х х х х х х х х х -  
                         

 

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

.

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

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

 

 

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

 







Дата добавления: 2015-09-04; просмотров: 1644. Нарушение авторских прав; Мы поможем в написании вашей работы!


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2021 год . (0.006 сек.) русская версия | украинская версия