Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 85
Текст из файла (страница 85)
При этом возможны два случая: й = з = 2 и (с(а) = 3, з((с) = 1. В первом случае запрешенными фигурами построения декомпозиции булевой функции вида зс(Х) = Р((рь(Х ), ьаз(Х ), е(ь(ХЬ), т(2(Хь)) являются квазиполные графы квазиплотности 5 Я(р;, (с;) С С бар(Хв), Сар(ХЬ) (р; — платность, /с; — порядок квазиплотнаго графа Я): Я(5, 0), Я(4, 1), Я(3, 2), Я(2, 3).
Минимальные ресурсы — вершинный, реберный, локальнотопологический (степени вершин графа), — определяюшие запрешенные фигуры Я(5), приведены в табл. 5.45. 475 474 Таблица 5.46 Таблица $.45 Минимальное анааеиие Тил аалре. гленнов фи- гурыч(оу) Мини. мальнал Моглиости Степени аершины графа структура Ж у') носители сигматуры ье(9), д(9, о) 36 пвааи- ьг(2 1)+ + Я(б, О) полные графы квазиплстности 9,а+1=9 50 О(2, г)+ +Я(5,0) ье(2, 1)+ +О(г, 1)+ +4)(3, 0) 13 68 10 1;)(2, 3)+ + 14(4, 0) 169 1е(2, 2)+ +14(2, 1)+ +се(г, 0) 113 18 10 ее(2, 1)+ +О(2, 1)+ +д(г,1) 1$ 90 12 14(2, 4)+ + се(3, 0) 50 380 1'„>(2, 3)+ +б)(г, 1)+ +О(1,о) 29 $07 10 1Х2, 2)+ +Ц(2, 2)+ +4)(1, 0) 183 ь)(2, $)+ + о(г,о) 946 Щ2,4)+ + д(2„1) 10 14(2, 3)+ + 14(2, 2) б)(2, 6)+ + Я(1, 0) 344 192 2551 Е(2,7) 7271 383 Гл.б.
Приклодмол теория олеоритмое Во второмгслучае при Ь = 3, з = 1 запрещенными фигурами являются квазиполные графы квазиплотнасти 9: Я(9) = (Я(9, О), Я(8, 1), (;)(7, 2), Я(6, 3), Я(5, 4), Я(4, 5), Я(3, 6), Я(2, 7)1, Я(9) С слир(Х,); и квазнполные графы квазиплатнасти 3: Я(3) = (Я(3, О), Я(2, 1) ), Я(3) С Спр(Хь).
При Ь = 1, в = 3 запрещенные фигуры Я(9) принадлежат графу Спр(Хь): Я(9) С Спр(Хь); а запрещенные фигуры О(3) принадлежат (тпр(Х,)1 Я(3) С С„р(Х,). Минимальные ресурсы, при наличии которых возможно существование запрещенных фигур Я(9) и ЩЗ) в графах противоречивости С„р(Х,) и Спр(Хь), представлены в табл. 5.46 и табл. 5.47 соответственна. Разбиваем исходное пространства Р(Х) на два надпространства, Р(Х,) и Р(Хь), так, чта Р(Х) =Р(Х ) х Р(Хь), Х Г)Хь = ~г~, ]Х,! = (О 5!Х!], (Хь! = ]Х! — 10 5!Х,)], (5 11) где ]Х! = в. Оцениваем каждое из С(в, (0,5в]) разбиений пространства Р(Х) суммой двоичных логарифмов верхних оценок хроматических чисел Ь(Спр(Х;)), Ь(0пр(Ху)): В(Р) = (1062 Ь(0„р(Х;))] + 11062 Ьфпр(Ху))], (5.12) 15.9.
Симгвез фумкциомольмоб декомпозиции 477 476 Т в б л н л в $.47 Гл.б. Прикладнал творил алгоритмов где С(и, (О, 5и)) — число сочетаний из я по (О, бя); С(Х;) — строчный граф противоречивости; О(Х ) — столбцевой граф противоречивости, используя верхние семантические оценки хроматического числа графа Ь(а) < ] (;„+ 1+ ((з ел+ Ц'+ + 8]У] — 4Щ з„,;„) ) 2 1[, (5.13) где зт;„— минимальная степень вершины графа С = ($; У), ) [ — целая часть числа.
Выражение (5.13) более точно определяет оценку хроматического числа, если известна плотность р(0) графа С. В этом случае вместо графа С необходимо рассмотреть частичный подграф С' = (Ъ", У'), 0' С сз, полученный после удаления вершин и, со степенями, меньшими, чем р(0) — 1: в(и;) < р(0) — 1. Кроме оценки (5.13), можно использовать и другие оценки хроматического числа, рассмотренные в гл. 3, например, оценку, учитывающую отклонение степеней вершин графа от среднего значения: ио)<](~,+ц г-'+ ф „+ц 2-') + + (~~ ]з,р — з(и;)!) 2 ') ~, (5.14) где з,р — среднее значение степени вершин графа С = (У, Щ, равное ]Г7] (2 ]Ц); з(и;) — степень 1-й вершины.
Оценку (5.14) получаем более точной, если вместо графа рассматриваем его частичный подграф С' = (У', Гу'), С' С О, полученный после удаления вершин и; со степенью, меньшей, чем р(С) — 1. 5 5.9. Синтез функциональноп декомпозиции Разбиение вида (5.11) определяется использованием субмикронной технологии, так как в этом случае дебаланс активизируемых цепей в нейронной сети будет оптимальным. Исследование такого разбиения показало, что оценки (5.12), с помощью которых выбирается оптимальное разбиение, близки друг к другу.
Действительно, порождение различных разбиений переменных булевой функции у(хм хэ,..., х„) эквивалентно применению преобразований Джевонса к этой функции. Все соответствующие графы Кенига определяют функции, принадлежащие одному и тому же типу (в смысле Джевонса), но все однотипные булевы функции имеют одни и те же теоретико-структурные свойства, которые в конечном счете объективно определяют декомпознционные свойства функции. Рассмотрим синтез функциональной декомпозиции, реализующей булеву функцию у(х1, хт, ..., хо), описывающую функционирование одного из узлов машины логического вывода, при заданных ограничениях 7е + а < 4: 1 на 3,4,7,9,16,18,22,24,25,26, 34, 36, 37, 48, 50, 53, 58, 59, 62, 63, 0 на 0,2,12,13,19,23,28,31,40, 43, 44, 45, 46, 49, 55. В результате оценки разбиений согласно (5.12) было выбрано разбиение вида Р(х1, хт, ...,хе) = Р(хм хэ, хз) х Р(хв, хэ, хе)," соответствующая таблица Вейча представлена в виде табл.
5.48 и граф Кенига — на рис, 5.57. Т волна в Э.ла Строчный граф противоречивости свар(Х,) представлен на рис. 5.58, а; он содержит запрещенную фигуру Я(5, О) — полный подграф плотности 5 (рис. 5.58, б). Для определения минимального сужения сигнатуры графа противоречивости и его оп- 478 479 «с«з«з Хс: «с «г«з «с«5«з Рис. 5.57 Хз: тзт «зц, Х 2тз 2" 2.«з а о 1 2 Ф Ф з а (а, 71 Р (1, 51 у 12, 3) 3 Ф Ь= (4, 61 с з Хс. «с«г«з с е а. р, у, Ь, с — краски трефе сзкр(Хс) Рис.
5.55 Хз: «з«с«з«з Рис. 5.60 Г«.5. Прикладная изеорил алгоритмов тимальной реализации построим матрицу смежности 5(с«ар(Х,)): а 1 2 3 4 5 э 7 о 1 2 3. 4 5 5 7 Здесь в клетке (с, у] указаны векторы пространства Р(Хз), которыми сцеплены векторы Х... Хат пространства Р(Х,). Для устранения запрешеннай фигуры Я(5, 0) выбираем ребро, которому соответствует минимальное количество сцепляюших векторов. В данном случае выбираем ребро (и(0), а(7)), так как векторы Х„равные О и 7, сцеплены одним вектором Хз, Хз = 2.
Штрихуем вектор 2 пространства Р(Хз): 2'=2 хз, 2и=2 ° хз чта эквивалентна удалению ребра (и(0), и(7)) из строчного графа противоречивости с'ар(Х,); прн этом хроматическое число 3 5.9. Синтез функциональной декомпозиции Ь(0ар(Х,)) понижается да 4 (рис, 5.59): ст = (О, 7), ~3 = (1, 5), у = (2, 3), б = (4, 6). В результате проведенного преобразования пространства Р(Хз), Хз = (хс, хз, хе) расширилось до про- в странства Р(хз, хе, хз, хв) размерности 4 (рис. 5.60, а). После склеивания соцветных вершин в графе с«„р(Х,) и кодирования красок в пространстве Р(срз, узг) получили 2 у первую компоненту искомой декомпозиции (рис.
5.60, б): Р5 эу 1оз(хз, хг, хз)~ = Ъ'(2, 3, 4, 6), 1з 6 а, Р, у, 6 — крвски ~рг(хз, хг, хз)~ = Ъ'(1, 5, 4, 6). срвфксу И,) !1 Синтезируем внутренние функции в сопряженном пространстве Р(Хз). Граф противоречивости б„р(Х'), Хз — — Х50 с".зХк, Хз = (х4, хз, хе), ЬХк = (хз) (рис. 5.61,а), со- держит запрещенную фигуру Я(5, 0) (рнс.
5.61, б), следовательно, его хроматическое число сз(Вар(Хзс)) равно 5: ст = (1, 2"), ~3 = (О, 2 ) 5), 7 = (3, 7), 6 = (6), е = (4). 481 430 Рис. 5.62 в о. (Ь В б, в — кРвскн эувфв оротнворечниоспю Овр (Хб ! Рис. 5.6э (ця У- Эх, Фа рбрххб Т вблиив 5.49 Фь!рэрб (1,2» 61 (о, 21 (3,71 (4,Я Рис. 5.63 5'=5хб 5" 5хб у=ЭХ, Э-Эх, Хб. ХЭхэхэхб Хь . 'Хэ хб х5 / 2' 2тэ2" 2 э Рис. 5.64 !б к.
к !ьрбатоа Гл.б. Прокладках Эиеорил алгориоэмов Для редукции хроматического числа достаточно удаления одного из ребер графа ф5, О). Для нахождения оптимального сужения сигнатуры графа противоречивости С(ор(Хэ) строим матрицу смежности Яфор(ХЭ)) с р указанием сцепляюших векторов пространства Р(Ф,), Ф, = 1!рэ, !р21 (табл. 5.49). Удаляем ребро 1о(1), и(6) 1, взвешенное сцепляю- щим вектором 1, (1 4-ь хэхтхз) (рис. 5.62,а).
В результате число красок графа противоречивости Сор(ХЭ!) уменьшается до 4 (рис. 5.62, б): а = 11!2в!6)! 8 = (0>2бу! 7=13!7), 5 = (4,5). Склеиваем соцветные вершины и кодируем краски а, Д, Т, б соответственно векторами О, 1, 2, 3 пространства Р(<рз, <р4). Получаем, что внешняя функция определяется пятью переменными, !рэ, !рт, !рз, !рб, хб (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
