Теорема Дилворта

Теорема Дилворта


Сначала введем (или напомним) некоторые определения и обозначения. Пусть на некотором конечном множестве А введено отношение порядка , т.е. отношение, обладающее свойствами транзитивности (состоящее в том, что если для элементов а, 6 и с множества А выполняются условия и антисимметричности (если другими словами, не существует двух различных элементов а и 6, для которых одновременно выполняются условия . Всем известными примерами отношений порядка являются отношения <, >, заданные на любом подмножестве числовой прямой, и отношение делимости на множестве натуральных чисел. Множество вместе с введенным на нем отношением порядка называют упорядоченным. Теорема Дилворта Подмножество упорядоченного множества называют цепью, если в нем любые два элемента сравнимы по данному отношению, и антицепью, если никакие два различные элемента этого подмножества не сравнимы по данному отношению. Например, в множестве {2,3,6,7,55}, упорядоченном, отношением делимости, есть цепи {2,6}, {3,6} и антицепи {2, 3, 7,55}, {6, 7, 55}. Одноэлементное множество — одновременно и цепь, и антицепь. Число элементов цепи (антицепи) будем называть ее длиной. Очевидно, что любая цепь пересекается с любой антицепью не более чем по одному элементу. Отсюда следует, что если в упорядоченном множестве А имеется антицепь длины m, то число цепей, покрывающих А (т. е. их объединение есть Л), не может быть меньше m. Покажем, что индексы всех вершин в указанном множестве различны, то есть Ведем рассуждение от противного. Предположим, что для каких-то t и I имеет место равенство i. Существует ребро вида xhyc, где ус $ Г, так как в противном случае множество } таимсе является вершинным покрытием, что противоречит минимальности Т. Аналогично, существует и ребро вида Xdyh для некоторой вершины Xd £ Т. Для указанных с и d имеем откуда в силу транзитивности Значит, в графе есть ребро хауе> соединяющее вершины, не принадлежащие множеству Т. Но тогда Т не является вершинным покрытием — противоречие! Таким образом, вершины множества Т представляют в точности r + s элементов множества А. Венгерская теорема, напомним, говорит о том, что наибольшая мощность паросочетания равна минимальной мощности вершинного покрытия; в наших обозначениях получаем к = г + s. Заметим теперь, что элементы, не представленные в множестве Г, попарно несравнимы, т.е. образуют антицепь, а число таких элементов равно Из существования антицепи мощности m вытекает, что максимальная длина антицепи Y не меньше т. Итак,. Вспоминая, что , окончательно имеем: Теорема Дилворта Замечание. Доказательство теоремы дает алгоритм нахождения минимального цепного покрытия, основанный на выделении наибольшего паросочетания в соответствующем двудольном графе. Теорема (двойственная к теореме Дилворта) Если в формулировке теоремы Дилворта заменить слово «цепи» на «антицепи», а «антицепь» на «цепь», то получим также верное утверждение, которое доказывается очень просто. Теорема 4. Минимальное число непересекающихся антицепей, покрывающих упорядоченное множество А, равно максимшьной длине цепи. Пусть m — максимальная длина цепи, а Р — цепь длшы т. Так как любая антицепь имеет с цепью Р не более одного общего элемента, исходное множество А покрывает не менее m антицепей. Обозначим через 1(a) наибольшую длину цепи, начинающейся с элемента а (то есть элемент а предшествует всем другим элементам данной цепи). Очевидно, если а то 1(a) > 1(b). Таким образом, элементы в и 6, для которых 1(a) = 1(b), не сравнимы, а множество является антицепью. Осталось заметить, что в наших предположениях функция I на элементах множества Р принимает все значения от 1 до т, и т — наибольшее значение функции I. Значит, имеем m непересекающихся антицепей , покрывающих упорядоченное множество Из доказанной теоремы вытекает следующий интересный факт. Теорема 5. Если упорядоченное множество А содержит не менее элементов, то в нем существует цепь длины не менее р или антицепь длины не менее q. Если в множестве А нет цепи длины р, то есть максимальная длина цепи не превосходит р — 1, то, согласно предыдущей теореме, найдется не более р - 1 антицепей, покрывающих множество А. Если бы каждая из них содержала не более q - 1 элементов, то в их объединении было бы не более {р - l)(g - 1) элементов, и они не покрывали бы множество А. Стало быть, длина некоторой антицепи не меньше числа Замечание. Теорема 5 легко выводится и из самой теоремы Дилворта, но, как уже заметил читатель, она доказывается не столь просто, как двойственная теорема. Теорема Дилворта В последующих параграфах данной главы мы рассмотрим некоторые приложения минимаксных теорем.