Введение в прикладную комбинаторику, Кофман А. (984071), страница 31
Текст из файла (страница 31)
(39.62) Итак, В = С. Например, для структуры на рис, 193 имеем 0=0, А,=А„А;=Л„Л,=А„ либо А,„либо Ам Лл= Ая (7=0, а элементы А„А,, А,, Ал структуры на рис. 194 не обладают дополнениями. Т е о р е м а. Если элеллент А дистрибртивной структуры Т обладает дополнениелс, то оно единственно. Структура с дополнениями.
Говорят, что Т вЂ” структура сдополнениями, если: 1) она обладает нулевым элементом (О =1п1Т) и универсальным элементом (У = зор Т), 2) каждый элемент из Т обладает по крайней мере одним дополнением. Например, структура на рис. 195 является структурой с дополнениями: О=У, А=С, В=С, С=А или В, О=О. (3963) Структура на рис. 190 также является структурой с дополнениями, в то время как структура на рис. !94 нс будет таковой. '!г с7 Рис. 195.
0 Рис. 196. (Х) =Х. Это следствие теоремы 1. Теорема 111. Для любых двух элементов Х структуры выполня;отса соотношения: ХЛУ =- Хт7У, Х с;У У = Хсх У. (39.65) и У булевой (39.66) (39.67) Булевы структуры. Дистрибутивная структура с дополнения- ми называется булевой, Например, на рис. 196 диаграммой Хассе представлена такая структура. Деиствительно, (39.64) О=У, А,=Ао А,=А„А,=А,, Аз=А,, А,=А, А,=А,, О=О, и легко проверить, что она дистрибутивна. Теорема 1, Каждый элемент булевой структуры обладает одним и только одним дополнением.
Доказательство следует непосредственно из того, что каждый элемент обладает по крайней мере одним дополнением (струк- тура с дополнениями) и это дополнение единственно в силу ди- стрибутивности структуры. Т е о р е м а Н. Для каждого элемента Х булевой структуры справедливо Так как эти соотношения двойственны, то достаточно проверить одно из них. Для этого достаточно показать, что (Х ~~ У) Л (Х ~7 У) = О, (39.68) (Х 2 У)ту(ХхуУ) = (7. (39.69) Аналогично (ХЛУ)т7(Хт7У)=(Х 7(Х~У))ту(Утт(Х~у)) (дистрибутивность), = ((Х х7 Х) т7 У) ~ (Х ~ (У ту У)) (ассоциативность и коммутативность т7), =(ит7У) Л(Х~ и) (так как Хту Х= (7 и У 7У=О), (по определению (7), = (7 (идемпо- ентность Л). (39.7!) =или Примеры.
Структура на рис. 197 дистрнбутнвна, но не является структурой с дополнениями, поэтому опа не булева. Структура У(Е) подмножеств, упорядоченных по включению, булева, если дополнение для А еи Р(Е) определить как А = СеА. (39.72) Действительно, (Х Ь У) Ь (Х сУ У) = ((Х Л У) Ь Х) х7 ((Х Л У) Л У) (дистрибутивность), = (ХЛ(У Л Х)) т7(ХЛ(УЛ У)) (ассоциативность Е ), =(ХГ (У" Х))~7(Х~' 0) (так как УЛУ=О), = (Х Л (У Л Х)) х7 0 (так как Х Л 0 = 0), = (Х Л (Х сХ У)) т7 0 (коммутативность 2 ), = ((Х Л Х) с."~ У) ~7 0 (ассоциативность Л), = (О Ь У) х7 0 (так как ХЛ Х=О), = Ох70 (так как ОЛ У = О), =0 (идемпотентность). (39.70) Формулы (39.66) н (39.67) принимают вид Се(А () В) = СеА() СвВ, Св (А Ц В) = СеА () Св — известные в теории множеств формулы де Моргана. 236 (39.?3) (39.74) На рис. !98 — 201 приведены У(Е) с Е= (А), Е= (А, В), Е= (А, В, С), Е= (А, В, С, В) (39 78) соответственно.
Теорем а 1Ч. Всякая конечная булева структура представляется как структура подмножеств (по включению) некоторого множества и обратно. и' Е ! и/ (в,г О Рис. 197. Рис. 199. Утверждение следует из того, что свойства (39.72) — (39.74) выражают то же самое, что и свойства, с помощью которых оп- Е (В,С) ~ЛВ1 ~с~ 1'л,В,) .З Рис. 201. Рис. 200. ределяется дистрибутивная структура с дополнениями, а именно: 1) (ЧХив Е) 31Х, (39.76) 2) Х ~ У Х '~7 У, (39.77) Х'~у У ХгХ У. (39.78) Отсюда следует, что алгебра подмножеств множества, называемая булевой алгеброй подмножеств, имеет строение булевой структуры.
Это играет важную роль в теории множеств. Подструктуры булевой структуры. Всякая подструктура булевой структуры Т называется булевой подструктурой для Т, если она содержит О и (7 и обладает свойствами булевой структуры, 237 Например, подмножества (см. рис. 203) Ь=(0, (В), (С), (А, О), (В, С), (А, В, В), (А, С, О), Е) (39.79) множества Е=(А, В, С, В) (39.80) образуют булеву подструктуру булевой структуры на рис.
202. Гиперкуб. Рассматривая рис. 199 и 200, легко заметить, что это — квадрат и куб (вообще говоря, ромб и параллелепипед). По аналогии принимаем, что на рис. 201 представлен гиперкуб порядка 4, а на рис. 198 — гиперкуб порядка 1, Назовем точку гиперкубом порядка О, отрезок — гиперкубом порядка 1,квадрат— Е МЮ ~с 4 Р(дю Д))) (и',В/ Рис 203. Рис. 202. С~-л 2л-х ~~ 2л-л Ы (и — а)1 (39.84) 238 гиперкубом порядка 2, куб — гиперкубом порядка 3 и т, д, Вершины гиперкуба можно распределить по уровням (которые аналогичны уровням, рассматривавшимся при определении порядковой функции) и у гиперкуба порядка и их и+1. Имеется С'„ вершин уровня т, и общее число вершин равно ~ С'„= 2".
(39.81) Подсчитаем число ребер диаграммы Хассе для гиперкуба порядка и. Из каждой вершины исходит п ребер, поэтому их всего л — ~ С'„= — 2" = и . 2" (39.82) ~са (так как каждое ребро учитывалось при подсчете дважды). Очевидно, что число граней (гиперкубов порядка 2) гиперкуба порядка п подсчитывается аналогично: л (л ) л~д С! (л ) 2л ( ) 2л 2 (39 83) ю=о Вообще число гиперкубов порядка й в гиперкубе порядка п равно Таким образом, гиперкуб на рис. 201 содержит 8 кубов, 24 квадрата, 32 отрезка, 18 вершин. Векторные структуры. Пусть заданы и конечных множеств А=(А„А,, ..., А,), В=(В„В,, ..., В ), ..., Б=(7.о (.„..., й ). (39.85) Предположим, что они линейно упорядоченные: А,) А,) ...
)А„ в)в)...)в,..., ~)(.)...)В. Определим отношение доминирования для элементов (Ао Вен..., С,) =АХВХ ... ХБ. Полагаем (Ао Во ..., (ч))(АС, Всь ..., 1.С), (39.87) если все элементы п-выборкн в левой части меньше или равны соответствующим элементам и-выборки в правой части и по (М (бС,С) ЬСмС) (СУ,1) (Щ) (ССУ) Вг,Сг) (йС)С) Рис.
205. (.'гг Сг,Сг Рис. 204. 239 крайней мере в одном случае имеет место строгое неравенство, Тогда А Х В Х ... Х Б становится структурой относительно введенного отношения и называется векторной структурой. Пример такой структуры приведен на рис. 204: А = (А~ Ав) А1) Ав' В = („„Ва), В, ) Вв ) Ва; (39.88) С = (С„Св), С, ) Св.
Булева структура векторная '), отношение доминирования определяется отношением включения. Лексикографические векторные структуры. Это — векторные структуры с линейным порядком (как слова в словаре). Рассмотрим следующее отношение доминирования. Считаем, что ') Не следует смешивать понятие векторной структуры с понятием векторного пространства и модуля. и-выборка (Ль Вп ..., 74) доминирует п-выборку (Л,, В,..., ..., 7.! ), если первые г элементов (считая слева) этих выборок совпадают, а (г+ 1)-й элемент первой выборки больше (в смысле заданного порядка) (г+1)-го элемента второй выборки.
Например, (3, 5, 7, 2, 5) доминирует (3, 5, 7, 1, 9), (Р, М, Н) доминирует (Р, Е, Б), если буквы упорядочены, как в русском алфавите. Другой пример лексикографической векторной структуры дает система счисления с основанием 10; например, 35725 больше 35719. На рис. 205 изображена диаграмма Хассе трехмерной лексикографической векторной структуры, образованной числами О, 1, 2, ..., 7 в двоичной записи.
У П Р А Ж Н Е Р! И Я 39А. Для упорядоченных множеств, представленных на рис. а), б), а), г) ниже: 1) перечислить цепи, 2) указать минимальные и максимальные элементы, 3) указать наименьшие и наибольшие элементы, 4) в б) указать мино- ранты (г", 6, Н) и мажоранты (В, О), верхнюю и нижнюю грани множеств (г, О, Н) и (В, й), 5) указать максимальные цепи в а) и г). б) 1 2 3 4 5 6 7 В 9 10 1 2 3 4 5 6 7 8 9 240 39Б. Для каждой из структур а), б), а), г) ниже построить диаграмму Хассе, а) 1 2 3 4 5 б 7 8 9 !О ! 2 3 4 5 6 7 8 9 10 в! 39В.
Перечислить все подструктуры для структур б) и г) из упражнения 39Б. 39Г. Сколько можно построить различных дистрибутивных структур на множестве пз пяти элементов. 39Д. То же, что и в упражнении 39Г, но на множестве из шести элементов. 39Е. Сколько можно построить различных структур с дополнениями на множестве из пяти элементов '), 39Ж.
То же, что и в упражнении 39Е, ио на множестве из шести элементов. 393. Сколько можно построить различных модулярных структур на множестве из шести элементов ')? 39И. То же, что и в упражнении 393, но на множестве из семи элементов. 39К. Построить диаграмму Хассе для булевой структуры подмножеств множества Е = (А, В, С, О, Е). 39Л. Является ли цепь дистрибутивной струнтурой? ') С точностью до нумерации элементов. ЗОМ.
Какие иа следующих диаграмм Хассе соответствуют дистрибутивным структурам. б) а) ЗОН. Рассмотрим цепь, образованную (и+ 1) элементами Хо, Хь ° ° ° ~ Х ° При каком и эта цепь будет еще структурой с дополнениями? (х, 390. Сколько в гиперкубе порядка 6 содержится гиперкубов порядка й,й<6? ЗОВ.
Рассыотрим три линейно упорядоченных множества. А=(А, В, С), А)В) С; В = (о, Ь), а ) Ь; С = (а, В, у, Ь), а ) () ) у ) Ь. Построить диаграмму Хассе для векторной структуры, соответствующей А Х В Х С. ЗОР. То же, что и в упрагкнении ЗОП, но А = (1, 2), В = (1, 2, 3).
Является ли полученная векторная структура: а) дистрибутивной, б) структурой с дополнениями, в) модуляриой? 39С. Построить 4-мерную лексикографическую модулярную структуру, искодя иа чисел 0 и 1. ГЛАВА 1Ч ПЕРЕЧИСЛЕНИЕ*) $40. Введение В начале $ 8 мы показали, как понятие производящей функции может быть использовано в задачах о перечислении. Но такой процесс применим только в случае неупорядоченных г-выборок; в случае же упорядоченных г-выборок пришлось бы ввести такие производящие функции, которые приводят к некоммутативной алгебре.
Хотя это и возможно, но даже прямое перечисление оказывается более эффективным. Эта глава посвящается вопросу о разумных способах перечисления. Когда количество перечисляемых элементов велико, часто отказываются от составления полного списка н вводят некоторые характеристики, с помощью которых его можно получить.
Следует иметь в виду, что процесс перечисления часто связан с пересчетом. Метод «латинской композициищ или «сцепления», который мы приводим здесь, — не единственный метод перечисления; существуют и другие, например перечисление с помощью понятия «груды», как в работе П э р а (34). Другой метод предложен Фоулксом (см. [2), стр. 281); в нем используется разложение на максимальные сильно связные подграфы, встречающиеся во многих задачах. За недостатком места мы лишены возможности изложить все эти методы. й 4!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
