Введение в прикладную комбинаторику, Кофман А. (984071), страница 29
Текст из файла (страница 29)
1,П1, (0), 1,()1,=1В, С, О), 1, П14=1А), 1, П1,— (А1, 1~ П17= 0 17 П1,= (В), П1,=О, 14П14= (О), 1„П 1, =' (О), 14 П 1.— (0), 1В П 1в = (А1 1,П1, О, ВП,-(.), '17 П '1В Я > Л,() Л = (Ь, 7(, е, ?): дает 11 М, 11, (37.14) л,() лв= (ь,447, е, 1'): дает 1)м, 11, 1~П1В=(74 17П14=141 17П14=0 Л, () Л, = (а, с): -дает 11 Мв 11, 14П1,= О, л4() лв=(ь, с, ?): дает 1)м411, Л, () Л, = (Ь, с, 1): дает 11 М, 11, Л,() Л,= (Ь, с, ?): дает 11 М, 11, л, () л„= (ь, о7, е, ?): дает 11 м, 11, Рис 1ЕО. Шпг 6 (правило 11). Действуя по правилу 11, мы приходим к тому же покрытию.
Следовательно, мы нашли все основные матрицы (см. рис. 159), Я!4 Отыскание минимальных подмножеств сочленений. На примере графа на рис. 160 проиллюстрируем процесс отыскания минимальных подмножеств сочленения. Выписываем булеву матрицу |~ М ~~ симметрического графа б = (Е, Г) без петель, соот. ветствующего графу иа рис. 160, и дополнительную к ней матрицу (37.16) 1~ М 11 = 1 — (( М 11, где Ц У ~~ — квадратная матрица, все элементы которой единицы: А В С Р Е и О Н (3?. 17) 11 м 11 = е е А В С Р Е Х 0 Н 1 (37.
18) 215 Подматрица в )) М)), определяемая строками, соответствующими В!, и столбцами, соответствующими Вз (в обозначениях (37,1)), содержит только единицы (в силу (37.1,г)), следовательно, она полная. Покажем, что она и основная. Действительно, если это не так, то подмножество (37. 19) А=Š— (В!() В,) не минимальное (в этом случае к В~ !) Вз можно присоединить В! 6'з . Г'' А' ('г 7 Рис.
16!. по крайней мере одну вершину Хь так что (37.1,г) еще выпол- няется) и, следовательно, А'= Š— (В,)) В,)) )Х!)) ~ А (37.20) Таким образом, задача сводится к отысканию основных подматриц в )) М)), определяемых подмножествами В, и В, с В,:»Е! и В,~Е,. Пример. Если Е!=)с), Е,=)В, С) (рис. 160), то ))М,)) определяется с помощью (37.21) а )1 Мс1) — с помощью (37.22) Отсюда следует, что А=)Е,1), ) А)=-2, А' )О, Е), ) А')=2 (37.23) (37.24) — минимальные подмножества сочленения (см. рис.
161 и 162). 2Щ l I I 1 1 ! х Р 1 1 1 'Н Рис. 162. В, = )А, В, С, О) и В, = )Р, 6, Н), В( )А, В, С) и Взс=)(с,б, Н, У). УПРАЖНЕНИЕ 37А. Перечислить минимальные подмножества сочленении графов: В Г б) а) 5 38. Прадерево, Дерево Прадерево. Прадеревом с корнем Хо называется граф 0=(Е, Г), если: 1) (31Хоеп Е)1 (Хо) = 01 (38. 1) 2) ()УХг ен Е)1Г (Хс) 1= 1 (Хоче Хо)' (38 2) 3) граф не содержит контуров. Иначе говоря, существует единственная вершина Хсь в которую не заходит ни одна дуга; в каждую другую вершину заходит в точности одна дуга; граф не имеет контуров.
На рис. 163 представлено прадерево. Вершина Х; висячая, если ГХг = 8. Будучи графом без контуров, прадерево всегда обладает порядковой функцией. На рис. 164 и 166 даны возможные порядковые функции прадерева на рис. 163. Бифуркант. Прадерево называется бидоуркантом, если (УХ~ нн Е)! Г (Хг) ~=0 нли 2, (38.3) Пример бифурканта приведен на рис. 166. Частичное прадерево графа.
Пусть 0,=(Е, Г,) — частичный граф без петель графа 0 = (Е, Г). Если Ог — прадерево с 2!7 корнем Хь то этот частичный граф называют частичным пра. деревом б с корнем Хь Например, можно показать, что существует шесть частичных прадеревьев графа 0 на рис. 167 с корнем А. Используя результаты из (81, дадим метод пересчета прадеревьев. С Рис. 166. Рис. 167. Рассмотрим булеву матрицу Ц а Ц, соответствующую графу б, и определим матрицу Ц а Ц: (38.4) и матрицу ЦЬЦ Ц Ь Ц = Ц а Ц вЂ” Ц а Ц.
(38.6) Для каждого !' обозначим через Л! минор матрицы Ц Ь Ц, получающийся вычеркиванием в ней 1-й строки и !ьго столбца. Тогда значение минора Л! дает число прадеревьев е корнем Хь Например, для графа на рис. 167 имеем АВСВ (38.6) (38.7) 6-1 О О 2 — 1 — 1! Π— 1 2 — 1!' О О -1 В~ (38.8) (! ЬЦ= 219 А ЦаЦ= В 0 А (1 2Ц= В С В О!О О О О!6 ООО АВСВ оооо 0200 ОО2О ООО6 Число прадеревьев с корнем А (рис.
168) равно 2 — 1 — 1 Д = — 1 2 -1 =6. А Π— 1 З (38,9) Очевидно, что для этого графа существуют частичные прадеревья только с корнем А. Рис. 168. В етвление. Граф, все связные компоненты которого — прадеревья, называют ветвящимся. Пример такого графа приведен на рис. 169. Дерево.
Неориентированный граф Н=(Е, !!) называется деревом, если для него выполняется одно из условий (эк- вивалентных между сонг бой): 1) Н связный и не содер- Б жит циклов; Е А 8 р 2) Н содержит а — 1 ре- бер н не содержит циклов и У К (и =!Е1)! 3) Н связный и содер- 7 К жит и — 1 ребер; 4) Н не содержит циклов, а добавление одного ребра между любыми двумя вершинами приводит к по- У Рис. 169. явлению одного и только од- ного цикла; 5) Н связный, а удаление любого ребра делает его несвязным; 6) любая пара вершин соединена единственной цепью. 220 Пример дерева приведен на рис. 170. Частичное дерево графа 6. Рассмотрим неориентированный граф 6 = (Е, Ц)); б связный тогда и только тогда, когда он допускает частичный граф О =(Е, Пг), являющийся деревом.
Это дерево называют частичным деревом графа 6. Рис. 171. Рис. !70. Для построения частичного дерева графа достаточно найти ребро, удаление которого не нарушает связности графа; если такого ребра нет, то граф — дерево; если ребро найдется, то удаляем его и процедура повторяется. Рис, 173. Рис. 172. Например, на рис. !71 указан порядок удаления ребер, приводящий к дереву. Подсчет частичных деревьев графа производится аналогично подсчету прадеревьев ориентированного графа. Пусть б = = (Е, Г) — симметрический граф без петель, соответствующий 6.
Полагаем (38.10) (38.11) Ц Ь П = П с( П вЂ” Ц а Ц, где П а Ц вЂ” булева матрица графа 6, 221 Величина любого минора Л; (см. стр. 219) дает искомое число (так как граф симметрический). П р и м ер. На рис. 172 и 173 изображены соответственно 6 и 6. Имеем АВСР о ! о О О!О О (38.12) Рис. !74. АВСО Азооо ОЗОО 0020 ОООЗ (38.13) А !! Ы~ = !! а ~~ — 1~ а 11 = 0 (38.14) -! -! †! Тогда з — ! — ! 2 — 1 — — з Л4 (38.15) Эти восемь деревьев представлены на рис.
174. 222 А !! ~~=с В 0 1!д!1= В С 0 А В С Р 2 — ! Π— 1 †! 3 †! †! Π— 1 2 †! УПРАЖНЕНИЯ 38А. Указать возможные порядковые функции прадерева. 3 КУЗАР 38Б. Указать функциго Гранди для прадерева из упражнения 38А. Что можно сказать о функции Гранди для прадерева? 38В. Каково число частичных прадеревьев с корнем А графов: А А А 38Г. Перечислить частичные прадеревья графа а) из упражнения 38В.
38Д. Каково число частичных деревьев неориентированных графов, соответствующих графам из упражнения 38В. 38Е. Перечислить частичные деревья графа, соответствующего графу б) из упражнения 38В. 5 39. Конечные структуры Структуры играют существенную роль при изучении упорядоченных множеств*), Мы будем рассматривать конечные структуры, которые являются графами, обладающими некоторыми ') См., например, Л.
А. Скорняков, Элементы теории структур, «Наука», 1970. (Приме перев.) 223 свойствами. Большинство определений и свойств, рассматриваемых в этом параграфе, остаются справедливыми и для бесконечных структур. Напомним вкратце некоторые определения. Упорядоченное множество. Упорядоченное множество — это множество Е, на котором определено отношение порядка ~(. Оно обозначается (Е, ((). Рассматриваемые в этом параграфе отношения порядка (еслн не уточнено) не строгие. Сравнимые элементы.
Два элемента а и Ь упорядоченного множества Е называют сравнимыми, если для них выполняется одно из условий: а( Ь или Ь (~а, Следовательно, а сравним с самим собой. е Линейно упорядоченное множество. э Линейно упорядоченное множество— в это упорядоченное множество, любые два элемента которого сравнимы. Частично упорядоченное множек ство. Частично упорядоченное множество — это упорядоченное множество, не являющееся линейно упорядоченным.
Рис. 17Э Цепь '). Цепь — это линейно упорядоченная часть упорядоченного множества. П р и м е р (рис. 175). Введем отношение порядка: Х; ( Хь если Х; еи ГХь Так как не все элементы сравнимы (например, В н Н), то множество вершин частично упорядочено. Подмножества (В, С, Р, Е, г), (Н, 6, г), (Н, А) — цепи.
Минимальный (макснмальный) элемент. Минимальным (максимальным) элементом упорядоченного множества Е называется элемент У, для которого в Е не существует строго меньшего (строго большего) элемента, т. е. соответственно (1УХ7 ы Е) (Х7 ~ (У) Ф(Хс = У), (39.1) (асгХс еи Е) (Х~ )~ У) )ь(Х7 = У). (39.2) Например, на рис. 175 элементы В и Н минимальные, а А и Р максимальные. Наименьший, или первый (наибольший, или последний), элемент. Наименьшим (наибольшим) элементом упорядоченного множества Е называется элемент, меньший или равный (боль. ший или равный) любому другому, т. е, соответственно (1УХ1) (Х! еи Е) Ф (У ~ КХ!), (39.3) (УХ,) (Х, Е)=>(У~Х,).
(39.4) ~) Не следует смешивать с понятием ив 5 32. Например, упорядоченное множество на рис. 175 не обладает ни наименьшим (так как В и Н несравнимы), ни наибольшим (так как Е и А несравнимы) элементами, Упорядоченное подмножество (В, С, О, Е, Е, 6, Н) обладает наибольшим элементом Е, а наименьшего элемента нет. Множество на рнс. 176 обладает как наименьшим элементом А, так и наибольшим элементом В. Миноранта (мажоранта). Рассмотрим упорядоченное подмножество А упорядоченного множества Е с введенным в Е отношением порядка.
Минораятой (лажорантой) подмножества А называется элемент Уен Е, не больший (не меньший) любого элемента из А, т. е, соответственно (ЧХ~) (Х~ ен А) Ф(У ~ (Х ), (39.5) (ЧХ~) (Х~ ен А) ~(У ~ )Х~). (39.6) Говорят, что А минорируется (мажорируется) в Е. Например, на рис. 175  — миноранта (О, Е, Е), Š— мажоранта (В, С,О), А — мажоранта Н, Н вЂ” мино- ранта (А, О, Е). Заметим, что если У вЂ” миноранта (мажоранта) А и У ен А, то он является Рис шб. наименьшим (наибольшим) элементом А, Нижняя (верхняя) грань.
Обозначим через М (М') множество минорант (мажорант) подмножества Ас: Е. Если М(М') допускает наибольший (наименьший) элемент У, то У называют нижней (верхней) гранью А. В частности, если А обладает наименьшим (наибольшим) элементом У, то он и является нижней (верхней) гранью А. Например, на рис. 175 М = (В, С, О) — множество минорант для подмножества А = (О, Е, Е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
