Новиков Ф.А. Дискретная математика для программистов (860615), страница 19
Текст из файла (страница 19)
Решётка с дополнениемВ ограниченной решётке элемент а' называется дополнением элемента а, еслиа П а' = 0 и a U а' = 1. Если Va 6 М (За' € М (а П а' = 0 & a U а' = 1)), тоограниченная решётка называется решёткой с дополнением. Вообще говоря, дополнение не обязано существовать и не обязано быть единственным.ТЕОРЕМА(о свойствах дополнения)с дополнением выполняетсяВ ограниченной дистрибутивнойрешёткеследующее:1. Дополнение а' единственно.2.
Дополнение инволютивно: а" = а.3. Грани дополняют друг друга: 1' = 0, 0' = 1.4. Выполняются законы де Моргана: (а П b)' = a' U b', (a U Ь)' = а' П Ь'.ДОКАЗАТЕЛЬСТВО[ 1 ] Пусть х, у — дополнения а. Тогда х = х П 1 = х П (a U у) = (а; П a) U (х П у) == 0и(хПу)= хПу = уПх = Ои(уПж) = (уГ\а)и(уПх) =уП(аИх)=уП1=у.[2] (a U а' = 1 = > a' U а = 1, а П а ' = 0 = > а ' П а = 0 ) = ^ а = а".[ 3 ] (1 П 0 = 0,0' П 0 = 0) =>> 1 = 0', (1 U 0 = 1,1 и 1' = 1)0 = 1'.[ 4 ] (а П Ь) П (a' U Ь') = (а П Ъ П a') U (а П Ь П Ь') = (0 П Ъ) U (а П 0) = 0 U 0 = 0,(а П b) U (a' U Ь') = (a U a! U Ъ') П (6 U a' U Ъ') = (1 U Ь') П (1 U а') = 1 П 1 = 1,(a U Ь) П (а' П Ь') = (аПа'П Ь') U (6 П а' П У) = (0 П Ъ') U (а' П 0) = 0 U 0 = 0,(a U Ь) U (а' П Ь') = (a U b U а') П (a U b U 6') = (1 U Ъ) П (1 U а) = 1 П 1 = 1.•98Глава 2. Алгебраические структуры2.5.4.
Частичный порядок в решёткеВ любой решётке можно естественным образом ввести частичный порядок, а именLDef^ ,но: а -< b = а П о = а.ТЕОРЕМА 1Отношение -< является отношением частичного порядка.ДОКАЗАТЕЛЬСТВО[ Рефлексивность ] а Па — а ==> а -< а.[ Антисимметричность ] аb Sz b -< а ==> а = аГ\Ь[ Транзитивность ] а -< b & b -< с= ЬПа= Ь.аПс — ( а П Ь ) П с = а П ( Ь П с ) = аПЬ = а =>•а -<: с.•Наличие частичного порядка в решётке не случайно, это её характеристическоесвойство.
Более того, обычно решётку определяют, начиная с частичного порядка,следующим образом. Пусть М — частично упорядоченное множество с частичным порядкомНапомним, что элемент х называется нижней границей для аи Ь, если х -< а к х -< Ь. Аналогично, у называется верхней границей для а и Ь,если а -< у к Ь -< у. Элемент х называется нижней гранью (наибольшей нижнейграницей) элементов а и Ь, если х — нижняя граница элементов а и Ь и для любой другой нижней границы v элементов а и Ь выполняется v -< х. Обозначение:х = inf(a, Ь). Аналогично, у называется верхней гранью (наименьшей верхней границей) элементов а и 6, если у — верхняя граница элементов а и Ь и для любойдругой верхней границы и элементов а и b выполняется у -< и.
Обозначение:у = sup(a, b) (см. также 1.8.4).ТЕОРЕМА 2Если ыилсняя (верхняя) грань существует, то она единственна.ДОКАЗАТЕЛЬСТВОх = inf(a, b) k y = inf(a, b) => у -< x & x -< уx = y.•Если в частично упорядоченном множестве для любых двух элементов существуют нижняя и верхняя грани, то это множество образует решёткуотносительно inf и sup.ТЕОРЕМА 3Положим х П у = f i n f ( х , у ) , х U у = f sup(x,y)полнение аксиом решётки.ДОКАЗАТЕЛЬСТВОи проверим вы-[ 1 ] inf (х, х) = х ==> х П х = х, sup(X, х) = х ==> X U I = I .[ 2 ] inf (х, у) = inf (у, х) => х Пу = у П х, sup(x, у) = sup(7/, х) ==> х U у = у U х.[ 3 ] inf(a;, inf(y, г)) = inf(inf(cc, у), z)х П (у П z) = (х П у) П г,sup(x, sup (у, z)) = sup(sup(x, у), z) =$> х U (у U z) = (х U у) U z.[ 4 ] sup(inf(a, b), а) =а = > (afl6)Ua = a, inf (sup(a, b), a) = a =>• (aUb)Da = a.•992.5.
Решётки2.5.5. Булевы алгебрыДистрибутивная ограниченная решётка, в которой для каждого элемента существует дополнение, называется булевой алгеброй. Свойства булевой алгебры:1. aU а = а, аГ\ а = апо определению решётки.2. a U 6 = bU а, аГ\Ь = ЬПапо определению решётки.3. а U [Ъ U с) = (а U b) U с, а П (Ъ П с) = (а П Ь) П спо определению решётки.4. (а П Ъ) U а = а, (а U 6) П а = апо определению решётки.5. а U (6 П с) = (а U 6) П (а U с), а П (6 U с) = (а П 6) U (а П с)по дистрибутивности.6. а и 1 = 1, а П 0 = 0по ограниченности.7.
a U 0 = а, а П 1 = апо следствию из теоремы 2 подраздела 2.5.2.8. а" = апо теореме подраздела 2.5.3.9. (а П Ь)' = а' U 6', (а U Ь)' = а'ПЬ'по теореме подраздела 2.5.3.10. a U а' = 1, а П а ' = 0по определению.Примеры1. ( 2 м ; П , и , ~ ) — булева алгебра, причём М — верхняя грань, 0 — нижняя грань,С — естественный частичный порядок.2. (£ 2 ; &, V, -•) — булева алгебра, где к — конъюнкция, V — дизъюнкция, —отрицание, причём 1 — верхняя грань, 0 — нижняя грань, а импликация—естественный частичный порядок.3. Пусть Т — некоторое конечное множество взаимно простых чисел.
Пусть Р —множество всех возможных произведений различных чисел из Т, включаяпустое произведение, по определению равное 1. (Заметим, что Р ~ 2 Т ). Тогда (Р; НОД, НОК, ДОП) — булева алгебра, где НОД — наибольший общийделитель, Н О К — наименьшее общее кратное, аДОП(п) = f — <7,пяетпричём П Я ~ верхняя грань, 1 — нижняя грань, отношение «п делится наrrv> — естественный частичный порядок.100Глава 2.
Алгебраические структуры2.6. Матроиды и жадные алгоритмыВ этом разделе рассматривается следующая простая и часто встречающаяся экстремальная задача. Задано конечное множество Е, элементам которого приписаны положительные веса, и семейство £ с 2Е подмножеств множества Е. Требуется пайти в семействе £ элемент (подмножество Е ) максимального суммарноговеса.
Оказывается, что если семейство £ обладает особой структурой (являетсяматроидом), то для решения задачи достаточно применить очень простой и эффективный алгоритм (жадный алгоритм). Ясное понимание природы и областиприменимости жадных алгоритмов совершенно необходимо каждому программисту. Матроиды, рассматриваемые в этом разделе, вообще говоря, не являютсяалгебраическими структурами в том смысле, который придан этому понятию впервом разделе данной главы.
Однако матроиды имеют много общего с рассмотренными алгебраическими структурами (в частности, с линейно независимымимножествами в векторных пространствах и модулях) и изучаются сходнымиметодами.2.6.1. МатроидыМатроидом М — (Е, £) называется пара, состоящая из конечного множества Е,\Е\ = п, и семейства его подмножеств £ с 2Е, таких, что выполняются следующиетри аксиомы:Mi:0 G £;М3:А, В Е £ к \В\ = \А\ + 1 => Зе Е В\ А (А + е Е £).Элементы множества £ называются независимыми, а остальные подмножества Е(то есть элементы множества 2е \ £) — зависимыми множествами.ЗАМЕЧАНИЕАксиома М1 исключает из рассмотрения вырожденный случай £ = 0.Пример Семейство линейно независимых множеств векторов любого векторного пространства является матроидом.
Действительно, по определению можносчитать, что пустое множество векторов линейно независимо. Всякое подмножество линейно независимого множества векторов линейно независимо. ПустьA: = { a i , . . . , a m } и В : = { b i , . . . , b m + i } — линейно независимые множества векторов. Если бы все векторы из множества В выражались в виде линейной комбинации векторов из множества А, то множество В было бы линейно зависимым последствию к теореме 2 подраздела 2.4.3.
Стало быть, среди векторов множестваВ есть по крайней мере один вектор Ь, который пе входит в множество А и певыражается в виде линейной комбинации векторов из множества А. Добавлениевектора b к множеству А образует линейно независимое множество.ЗАМЕЧАНИЕСамо понятие матроида возникло в результате исследования линейной независимостив векторных пространствах.1012.6.
Матроиды и жадные алгоритмы2.6.2. Максимальные независимые подмножестваПусть М = (Е, £) — матроид и ! с £ - произвольное множество. Максимальным независимым подмножеством множества X называется множество У, такое,чтоrcX&r<E£&VZe£(YcZcX=>Z= Y).Множество максимальных независимых подмножеств множества X обозначим X'.XD={YcE\YcXkYeikVZe£(Y С Z С X => Z = Y)} .Рассмотрим следующее утверждение:М4:VX(Y G XkZ G X =$> \Y\ = \Z\),то есть все максимальные независимые подмножества данного множества равномощны.ТЕОРЕМАПусть М = (Е, £) и выполнены аксиомы М\ и М 2 . Тогда аксиомаутверждение М4 эквивалентны, то естьА, В <Е £ к |Я| = \А\ + 1 = • З е € В\Аи(А + ее £)тогда и только тогда, когдаMX {Y е X k Z € X|У| =\z\).ДОКАЗАТЕЛЬСТВО[ =>• ] Пусть выполнены утверждения М ь М 2 , М 3 (то есть М — матроид).
Покажем от противного, что выполняется и М 4 . Пусть У, Z € X, |У| Ф \Z\ и дляопределённости |У| > \Z\. Возьмем Y' С У, так что |У'| = \Z\ + 1. Тогда посвойству Мз имеем Зе е Y' \ Z (W: = Z + е е £). Таким образом, имеемZ с W, W С X, Z ф W, что противоречит предположению Z е Х_.[] Пусть выполнены утверждения М ь М 2 , М 4 . Покажем от противного, чтовыполняется и М 3 . Возьмем Л, Б е £, так что |Б| = |Л| + 1. Допустим, что->3е е В\А (А + е е £), то есть Ve 6 В\А {А + е $ £).
Рассмотрим С : = A U В.Имеем А е С. Но В е £, поэтому ЗВ' (В с В' к В' е £ к В' е С). По условиюМ 4 имеем \В'\ = \А\. Но \А\ = \В'\ ^ \В\ = \А\ + 1 — противоречие.•ЗАМЕЧАНИЕТаким образом, М\, М 2 , М4 — эквивалентная система аксиом матроида.2.6.3. БазисыМаксимальные независимые подмножества множества Е называются базисамиматроида М = (£,£). Всякий матроид имеет базисы, что видно из следующегоалгоритма.102Глава 2. Алгебраические структурыАлгоритм 2.1 Построение базиса матроидаВход: Матроид М = (Е,£).Выход: Множество В с Е элементов, образующих базис.В : = 0 { вначале базис пуст }for е е Е doif В + е е 8. thenВ : — В + е { расширяем базис допустимым образом }end ifend forПусть ВО = 0, В\,..., В к = В — последовательность значений переменной В в процессе работы алгоритма. По построению Vг (Bi е £). Пусть В #£ Е, то есть В не является максимальным.
Тогда 3 В' (В с В' к В' ф В & В' е £)Возьмем В" с В' так что \В"\ = \В\ +1, В с В" и В" е £. Рассмотрим ееВ'\В.Элемент е не попал в множество В, но алгоритм просматривает все элементы,значит, элемент е был отвергнут на некотором шаге г, то есть (Bi-1 + е) ^ £. Ноее В" к Bi-1 с В"(В^ 1 + е) € £. По аксиоме М 2 имеем (Вг-i + е) е £ —противоречие.•ОБОСНОВАНИЕСЛЕДСТВИЕВсе базисы матроида равномощны.2.6.4. Жадный алгоритмСформулируем более точно рассматриваемую экстремальную задачу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
