Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 83
Текст из файла (страница 83)
5.41, а); при его построении учитываем, О 1 2 3 4 3 б 7 'Л »сз ") "злз О ! 2 з а Рис. Ь.40 Рис. 5.4! что две вершины, о;(Х>н) и о (Х,,), (о;(Х,„), о.(Х,,)) б У„р, смежны, если найдется вершина оь(Хь) другого яруса, которая соединена с вершиной о;(Х>н) неинверсным ребром, а с вершиной и.(Х,,) — инверсным (рнс. 5.41, б). Граф Сир(Х,) содержит ква- зицолный цодграф Я(3, 0): Щ(3, 0)) = (1, 3, 4). Согласно характеризационному анализу минимальное число красок равно трем: а = (0) 2) 4) 6)) Ь = 11, 5, 7), с = 13). Теорема 5.7 свраведлива. После кодирования красок с помо- щью символов >рь>рз (а — 00, Ь вЂ” 01, с — 10) получаем декомпо- 'зицию заданной функции у(хь, хз, ..., хь) вида 2 (хь> х2) °, хь) = Р(ч)2(х!) х2) хз)) )рз(х!) х2) хз)) х4) хь), )рз(хз, х, хз) ~ = г'(3), И !рз(хз, хз, хз) ~ = Ъ'(1, 5, 7).
Функция Р(>рз) >рз, х4, хз), определяется матрицей Вейча (табл. 5.34), полученной в результате соответствующего раскраске- 458 Л! Лв Э Рис. 5.42 Таблила 5.3б Таблила 5.37 Гл. 5. Приклвднал теорие алгоритмов склеиванию строк матрицы Вейча, определяемой по выбранному Тевлина 5.34 Таблила 5.35 Разложению пРостРаиства Р(х1, хв, ..., хв) (табл. 5.35): ! 1 на 1,3,4,9,10, ! 0 на О, 2, 5, 6, 8, 11. В дальнейшем функции у1, ьвт будем называть внутренними, а функцию Р— внешней; множества переменных, вошедших в различные сомножители при разложении заданного пространства, назовем взаимно дополнлюиьими до полного множества. В рассматриваемом случае множества Х, = 1Х1, хт, хз) и Хь = = 1хя, хб) являются взаимно дополняющими друг друга до полного множества Х = 1Х1, хэ,, хб).
Очевидно, что условия декомпозируемости по столбцевым переменным будут аналогичными (5.3). Булеза функция у(Х) декомпозируема в виде у(Х) = Р(Х„О!(Хь), 02(Хь) ...,Ч,(Хь)) тогда и только тогда, когда [1о82 Л[ь ар(Хь))] < |Хь!: у(Х) = Р(Х., „,(Хь), О,(хь), ..., п,(Хь)) ~ м [1обзЛф р(Хь))] < |Хь!, (54) где в = [1о82 Л(С~р(Хь))]. Рассмотрим булеву функцию 11 на О, 4, 12, 16, 17, 19, 21, 26, 30, ~(*1 хз " х') 1,О на 1, 3, 5, 6, 9, 10, 23, 24, 28, 31. Представим исходное пространство Р(хь, хз, ..., хб) в виде декартова произведения пространств Р(Х,) х Р(Хь), где Х = 1Х1, хг), Хь = 1хз, хв, хб).
Тогда получим граф Кенига и матрицу $5 7. Решение проблемы повторное декомпозиции 459 Вейча соответственно в виде рис. 5.42, а и табл, 5.36. О 1 2 Э Я 5 б 7 о лзл4л5 Минимальная раскраска графа противоречивости Сар(Хь) (рис. 5.42, б) а = (О, 4), Ь = 11, 2, 3, 5, 6), с = 7 определяет соответствующее склеивание столбцов (табл. 5.37); при эхом коды красок имеют следующие значения: а — 00, Ь вЂ” 01, с — 10.
Утверждение (5.4) справедливо. Получаем декомпозицию вида ,! (х1, хт, ..., хб) = Р(х1~ хз) 171(хз, хв) хб), Щ(хз, хв) хб)) ~ где в!1(хз, хв, хб) = р'(7), 11 пт(хз, хв, хв)] = Ц1,2, 3, 5, 6). 11 Внешняя функция Р(х1, хт, п1, пт) определяется матрицей Вейча (см. табл. 5.37) 11 на 0,4,8,9,13, (Х1' хт' 01' '!2) ),О на 1 5 10 12 14.
Теорема 5.8 (А.В.Горбатов). Булева Яункцил ДХ) декомпозируема в виде у(Х) = Р(Ьр1(Х,),!рт(Х,), .. вдарь(Х,),гд(Хь), пз(Хь),..., ту,(Хь)) тогда и только тогда, когда ([1об, Л(а„,(Х.))] < |Х.|)5 ([1об, Л(а.,(хь))] < |Х,|): 460 о б Рис. 5.43 Гл.5. Приклоднол >пеориа алгоритмов 1(Х) = Р(Р1(Х.), рз(Х.) " рь(Х.) Л1(Хь) Л (Хь) ". ..., О,(Хь)) (-) ([1ойз 5(С„р(Х,))1 < ~Ха~)й 55([Ьобз 5(Сир(Хь))] < ~Хь!) (5.5) пРи совмшеспьноб РаскРаске гРай>ов С„р(Х,) и Сцр(ХЬ); пРи эпьом У »" Уь = >с . Рассмотрим булеву функцию ~1 на 0,4,12,16,17,19,21,24,26,28,30, '10 на 1,3,5,6,9,10,23,31.
Представление исходного пространства Р(х1, хз, .. и хб) выберем и виде Р(х1, хз> ..., хб) = Р(х1, хз) х Р(хз, хе, хб). Таблица Вейча, саответстауюшая этому разбиению, имеет вид табл. 5.38. Таблица 5.38 Граф противоречивости С„р(Хь) = ((О, 1,2>..., 7), с>лр), соответстлуюший табл. 5.38, представлен на рис. 5.43, а; С„р(Хь) Э о Э ф3, 0), следовательно, й(С„р(ХЬ)) = 3: в=(0,4), Ь=(1,2,3,5,6), с=(7), в, Ь, с — краски.
Кодируем краски: а — 00, Ь вЂ” 01, с — 10, и соответственно раскраске склеиваем столбцы и табл. 5.38; получаем табл. 5.39. 5 5.7. Решение проблемы повторнов декомпоэиции 461 Внутренние функции 01(хз х4, хб), пз(хз х4, хб) имеют соответственно пид >11(хз> ха, хб)~ = У(7), 11 Оз(хз> х4, хб)~ = У(1, 2, 3, 5, 6). >1 Для склеивания строк строим граф противоречивости С„р(Х,) (рис.
5.43, б); анализируя табл. 5.39, получаем й(Слр(Хв)) = 2, а =(О, 1), Ь= (2, 3). Склеиваем строки и табл. 5.39 согласно раскраске графа С„р(Х,); получаем матрицу Вейча (табл. 5.40), апределяюшую Таблица 5.39 Таблица 5.40 внешнюю функцию Р(>р1, >11, От); при этом краска а кодируется символом О, краска Ь вЂ” симпалом 1. Получаем >1 на 0,4,5, Р (х, хт)~ =У(2,3), Р(р1, Ом Оэ) =] О н 1'6' Теорема 5.7 слразедлипа; получаем декомпозицию вида у(х1> хя» ... хб) = Р(>Р1(х1> хя)> щ(хз> хь> хб), >13(хз> х4> хб)) ° Утверждения (5.3)-(5.5) являются теоретико-графовым разлитием теоремы Шеннона о разложении булевой функции по заданным переменным и определяют построение бесповтарнай декомпозиции (случай, когда У, >"> Уь = И; на практике же этому ограничению, как правило, булевы функции не удозлетворяют).
Предложим характеризационный подход, позволивший впервые решить проблему, поставленную К. Шенноном в 1936 г. проблему синтеза оптимальных повторных декомпозиций системы булевых функций заданной размерности. Подход основан на спедении поиска декомпозиции к раскраске введенных графов противоречивости заданным числам красок.
Согласно характеризационнаму анализу запрещенными фигурами раскраски графа С в >7 красок является квазиполный граф кзазиплатнасти д + 1. Отсюда нетрудна доказать теорему 5.9. 15.7. Решение проблемы повторной декомпозиции 463 Гл.5. Прикладная теория алгоритмов 462 Теорема 5.9. Запрещенными фигурами бесповторной декомпозиции булевой функции У(хь, хг,,х„) являются квозиполные гРафы Я (О!), Яе(й!) С бар(Х»), и ЯЬ(дУ), ЯЬ(ду) С С 0,»р(Хь) для зеоторых [1об й*(Я.)1+ [1обгйу(Чь)1 = и (5.6) при совместной раскраске соответствующих графов противоречивости.
Рассмотрим булеву функцию 11 на 0,5,7,9,10,14,20,21,25,27, 10 на 1, 4, 8, 11, 12, 13, 22, 31 и разложение пространства Р(хь, хг, ..., ха) в виде Р(хь, хг, ... ..., хь) = Р(хь, хг, хз) х Р(хе, хь). Граф Кенига, соответствующий этому разложению, имеет вид, представленный на рис. 5.44, а. Строчный граф противоречивости Сар(Х,) (рис.
5.44, 6) имеет хроматическое число, равное 5, так как вершины, соответствующие точкам пространства О, 1, 2, 3, 5, образуют носитель пол- "! "г«э б «е«5 О 1 2 3 2 3 в а Рис. 3.44 ного подграфа плотности 5, а столбцевой граф противоречивости Оар(Хь) — хроматическое число, равное 4 (рис. 5.44, в).
Следовательно, [1обгб)+ [1обг4) = 5, и согласно утверждению (5.6) рассматриваемая функция не имеет бесповторной декомпозиции. Предложим стратегию построения повторных декомпозиций, т. е. когда Ъ; ! ! 1ь ф О. Стратегия основана на редукции хроматических чисел графов противоречивости бар(Х ) с«ар(Хь) с целью выполнения соотношения [1обг й!Яе)1 + [1обг йу®ь)1 < и. (5.7) Это неравенство осуществляется при сужении сигнатуры графов противоречивости, которое в свою очередь осуществляется на основе расширения носителя графа противоречивости сопряженного надпространства за счет увеличения его размерности.
Увеличение размерности осуществляется с помощью взаемаь переменных из другого сопряженного пространства. Продолжим рассмотрение примера. Синтезируем повторную декомпозицию, и в конце параграфа оформим эту стратегию в виде соответствующих процедур. Для выполнения соотношения (5.7) понизим хроматическое число Ь(с«ар(Х,)) удалением одного из ребер полного подграфа с носителем (О, 1, 2, 3, 51 (рис. 5.45,о). Каждое ребро на этом «!«г« «1 «»«5 од,г !у ох ~~» о„! 2 3 а б Рис. 3А3 подграфе взвешено векторами сопряженного пространства Р(Хь), которыми соответствующие точки рассматриваемого пространства Р(Х,) сцеплены.
Очевидно, что при оптимальном решении необходимо удалить ребро с минимальным цо мощности весом. Для определенности удаляем ребро (1, 51, расщепляя сцепляющий их вектор О в сопряженном пространстве Р(Хь) (рис. 5.45, 6) на 0' и 0". Вектоо 0' есть результат конкатенации 0 и Х! (О = Ох!), а вектор 0" — резуль- г ь а ! тат конкатенации,О и х! (Оа = Ох!). Векторы 1 и 5 в подпространстве Р(Х,) отли- чаютсЯ пеРеменной хь: 1 — хьхгхз, 5 в Ь а Ь2 хьхгхз. Следовательно, инверсное ребро (1, 01 в графе Кенига (см. рис. 5.44, о) после расщепления преобразуется в инверс- 41,! ное ребро (1, 0'1, ребро (5, 01 — в ребро (5, Оа) (см.
рис. 5.45,6). Такое удаление реализуется расщеплением ребра (1, 5) в графе Вар(Х,). Размерность пространства Р(Хь) увеличилась на единицу: Р(хе, хь) -+ -Ь Р(Хг, Х4, Хь). ХрОМатнЧЕСКОЕ ЧИСЛО Ь(С«ар(Х,)) УМЕНЬШИЛОСЬ на единицу (рис. 5.46): о = (О, 41, 5 = (2, 71, с = (31, И = = (1, 5, 61 (о, 6, с, И вЂ” краски), и соотношение (5.7) стало выполняться: (1обг4)+ Мг 4) < 5. Рассмотрим функциональную декомпозицию в подпространстве Р(Хь), Хь = (хь, х4, хь). Столбцевой граф противоречивости 464 з о а 2' 2ла б 3" зле з'-зг, 5 б «г «зязее я~ л з о'ох,о" а, 1 2 З е Рис. $.47 Таблила $.41 Ь 11, 2', 5, б) ГО, 2", 3",7) с 13'1 р!рз -1о.2) Р (о,г,з) Рис.
$АЗ Гл.б. Прикладная теория алгоритмов сяпр(Хь) имеет вид, представленный на рис. 5.47, а. Уменьшаем хРоматическое число )г(бпр(ХЬ)) да 2. ЗапРещенными фигУРами 1 о'22 2 о' 2 являются циклы нечетной длины: (Я1) = ((О', 1, 3), (О', 1, 2), (О', 2, 3), (1, 2, З)1. Строим семантическую таблицу (табл. 5.41). Первая подтаблица показывает распределение ребер графа Спр(Хь) по запРешенным фигУРам.
ПокРытие стРок столбцами по- 15.7. Решение проблемм повторной декомпозиции 465 казывает, какие ребра необходимо удалить. Имеем трн покрытия: кг — — ((О', 1), (2, 3)), 1= ((О', 2), (1, ЗН, ггз = ((О 31 (1 2)). Вторая падтаблица показывает, какими переменными отличаются тачки пространства Р(Хь), образуюшие ребро в графе 0пр(Хь), взвешенное сцеплЯющими вектоРами Х, (тРетьЯ подтаблица), Покрытие столбцов, составляющих покрытие первой подтаблицы, строками второй подтаблицы состоит из переменных, с помощью которых расщепляются тачки пространства Р(Х,), соответствуюшие векторы которых сцепляют векторы пространства Р(Хь). В рассматриваемом случае пространства Р(Х,), Х, = = хгхтхз, расширяется: — для первого покрытия хг — переменной ха, с помощью которой расщепляются точки О, 1, 2 пространства Р(Х,); — для второго покрытия гг2 — переменной хв, с помощью которой расщепляются точки 2, 3 Е Р(Х,); — для третьего покрытия кз — одной из переменной хв или хб, которой расшепляются точки 1, 3, 5 Е Р(Х,).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
