Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 42
Текст из файла (страница 42)
3.54, а. Анализируя этот мограф, устанавливаем, что запре- щенными фигурами типа А являются следующие подмографы: Я( — — (хг(3, 6), хэ(б, 5), гз(5, 3) ~, Я2 = (х2(3, 6), хв(6, 2), х((2, 1), гэ(1 4), хз(4 3) ), Яз — — (хэ(6, 5), хз(5, 4), гэ(4, 1), хд(1, 2), хв(2, 6)). Запрещенной фигурой типа Б является подмограф ((х2, хв, хэ), (ХМ Хе~и (Хэг ХЗГ, (Х51 Хвх У. Гл.з. Теория графае и маграфаа 232 33.9. Характериэацил частичиага уларлдаченил маграфа 233 Фигуру типа Б в дальнейшем будем задавать соответствующим треугольником. В данном случае четвертая запрещенная фигура имеет следующий вид: 1.)4 з (х4(2, 6), хб(5, 6), хг(3, 6)). Основное свойство запрещенных фигур типов А и Б заключается в том, что при расщеплении любой вершины фигуры типа А и любой вершины треугольника фигуры типа Б эти подмографы перестают быть запрещенными фигурами. Таким образом, подобные расщепления — это способы преобразования запрещенных фигур типа А и Б в разрешенные.
Процедура семантического эквивалентирования мографа в частично упорядочиваемый стандартная. В семантической таблице строкам соответствуют запрещенные фигуры типа А илн Б, столбцам — расшецляемые вершины мографа, Семантическая таблица для рассматриваемого примера приведена в табл. 3.11. Твблилв 3.11 Для уменьшения трудоемкости определения покрытия семантической таблицы будем удалять поглошаюшиеся строки и столбцы. В данном случае правила поглощения следующие. Столбец а гзаглои4ается столбцом )у, если не найдется третьего столбца, взвешенного той же буквой, что и столбец а, и векторное произведение столбцов а и 11 равно столбцу а.
Строка а гзоглои4ается строкой )У, если векторное произведение этих строк равно строке )3. В рассматриваемом случае первый и восьмой столбцы поглощаются шестым. Вычеркивая поглошающиеся столбцы, имеем шесть покрытий семантической таблицы: (хт(3, 6), х4(2, 6)), (хт(3, 6), ха(5, 6)), (хт(З, 6), хз(4, 5)), (ха(2, 6), хб(5, 6)), (хз(З, 4), хб(5, 6)), (хз(3, 5), ха(2, 6)). Каждое из этих покрытий порождает два расщепления. Следовательно, мощность расширения носителя модели зг, равна 2, и абсолютно минимальная реализация рассматриваемой тупиковой ДНФ содержит 11 ключей: 1 = )М,)+ )г'ЬМ,( = 11. Для определенности рассмотрим последнее покрытие, и будем отличать букву хз в третьем слове от хз в пятом слове, добавляя штрих в верхнем индексе: х'.
В дальнейшем это переименование будем называть изтрихоекой буквы в соответствующем слове. Аналогично произведем штриховку буквы хе во втором слове. В результате получаем модель зр,: зРв = (Ма~ ат~ ~3) ~ ( Ма = (Х1~ Х11 Х2~ ХЗ1 ХЗ1 Х31 Х41 Х41 Х4~ Хе~ Хб)~ ат = ЦХ1, Х4), (Х2, Хз)), Яз = ( зх1~ Уз~ хб)~ (х11 хз1 х5)1 (хзз Уев х5)ю (х21 х4~ хб)). Она эквивалентна заданной и интерпретируется в терминах ча- стично упорядоченного множества (рнс. 3.54, б): х1 44 о(х1), хт 4+ ю(х2), хз 44 ю(хз), х1 4+ о(У1), ХЗ ет Ю(ХЗ), ХЗ 4ч Ю(ХЗ), Х4 4"у Ю(Х4), Хе 4"г О(Х4), Х4 ет о(Х4), Хб ет о(Х5), У5 4ч о(Х5); при этом х1, хзхб ++ ю(х1) ( и(Уз) ( ю(У5), Х1Х4 4"У и(Х1) С О(Х4), ХЗХЗ 4-з и(Х2) С Ю(ХЗ)1 У1ХЗХ5 44 0(ХЗ) с- и(Х1) ч- Ю(Х5)1 хЗУахб 4+ о(хз) ~ о(хе) ( ю(хб)~ хтхехб б+ и(хт) С о(ха) С ю(хб).
Если в покрытие первой таблицы вошли хотя бы две буквы, лексикографически одинаковые, то слова, в которых происходит пх штриховка, определяются покрытием столбцов (букв) строками (идентификаторами слов), в которые буквы входят. Таким образом, знание семантики преобразования злм — г Н позволило заменить перебор 5184 фактически строящихся диа- грамм Н; анализом шести покрытий семантической таблицы.
В общем случае трудоемкость при знании семантики уменьшается в помбинаторное число раз по сравнению с количеством всех экви- валентных решений. Рассмотрим примеры, иллюстрирующие теорему 3.47. Пример 3.12. Мсграф зз™ = (зг', Яг, Яз), М = (а, Ь, с, И, е), Яг = Ца, е), (Ь, д), (И, сЦ), Яз — — ((а, Ь, с)), 1 г з з аалерикт авлрещеииые фигуры 12з —— (Ь(2, 4), с(4, 3), Ы(3, 2)), 12г зз (а(4, 1), Ь(4, 2), с(4, 3)) (рис. З.бб,а), кстарые кораилают семантическую таблииу (табл.
3.12). Таблица 3.12 1 3.9. Харакше изацил частличного упор адаченил мографа 235 Гл.з. Теория графов и мографае 234 е(1) 1а(1) ) ) с(4) Ы4 Я, 3) Ы4, 2 с(4, 3 ) (4, 3 ) И(2, 3) 412, 3) 3 13) а1 Рис. 3.55 Пример 3.18. Мограф ззм = ()г, яз, яз)1 )г = (а, ь, с, зг), Яз = ((а, й), (Ь, й,(с, 43), Яз = ((а, Ь, с)), 1 з 3 з содервоп три заврешенные фигуры типа А и одну пша Б1 4)~ = (а(1, 4), 6(2, 4), й(1, 2)), 43, = (6(2,4),.(З, 4), й(2, З)), )31 = (а(1, 4), с(3, 4), а(1, 3)), Яз = (а(1, 4), Ь(2, 4), с(3, 4)); они вороадают семантическую таблнду (табл. 3.13). Таблила 3.13 Табл. 3.13 имеет шесть вскрытий: 111 = (а(1, 4), Ь(2, 4)), 1гз — (а(1, 4), с(З, 4)), лз = (Ь(2, 4), с(3, 4)), кз = (а(1, 4), й(2, 3)), кз = (Ь(2, 4), й(1, 3)), 1гз = (с(З, 4), а(1, 2)); каадое нз ник вороадает лиагрююеу Хассе слоаности 6.
Для олределенности выберем вервое вскрытие, ар«изведя штриковву буквы Табл, 3.12 имеет три покрытия: кз =(Ь(2, 4)), 1гз =(с(З 4)Ь кз = (а(1 4), а(2, 3)); с комошью ннк нскодный могрзф монна привести к интерлретируемому виду тремя свое«бами, доказанными иа рис. 3.55,6. а в нервом слове, буквы Ь вЂ” во втором. В резулыате волучаем мограф С~=()~,Яз,йз), )'м(а,а',Ь,ь~,с,а), Я, = ((а', Н), (6', 11), (с, И)), Яз = ((а, Ь, с)), зквивалентируюшнй заданныйишпервретируемый в категорияк частично уво- ряяоченногомноиества ()г, <): (а', а) ++ «(а') < «(а), (Ь', а) 44 «(Ь') < «(Н), (с, з)) ++ «(с) < «(11), (а, 6, с) ез «(с) < «(а) < «(Ь).
Рассмотрим устойчивость запрещенных фигур в зависимости от граничных условий, т. е. от условий пересечения запрещенной фигуры с остальной частью мографа. Условие неустойчивости запрещенной фигуры т и п а А. Композиция эапрг«4гнной фигуры типа А и слога, но- сители которых совпадают, не нарушает условий интерпрг- тируемости мографа а кагпсгоридх частично упорядоченного мнохсгста а.
Рассмотрим мог раф С (з'1 ЯЗ)1 г — (х)1 х21 х21 х31 х41 хз)1 Яз = ((хд, хт, ха), (хт, хз, хе), (хд, хз, хб, (хт, хз, хб)), 1 2 з 4 содержащий запрещенную фигуру хипа А Ял = (х)(1, 3), хз(3, 2), х4(2, 1)). При преобразовании зтого мографа в структурный граф необ- ходимо расщепить одну из букв х), хз, хе.
Для определенности расшеиляем хе во втором слове; в результате получаем мограф М С = ()'1 уз)1 Ьг = (хы хт, х21хз х41 хе, хб), Яз = 1 х11 х21 х4)1 (х21 хз1 хе)1 х11 хз1 хб 1 х21 х31 хб)11 1 г з 4 интерпретируемый а категориях частично упорядоченного множе- ства (рис. 3.5б, а).
Введем понятие пары внешне неустойчивых вершин. Парой внешне неустойчивых вершин относительно подмографа (См)' мографа См называется пара вершин «6, «и взвешенных пер- вичными термами х;, х;, «6(х;), «)(хг), таких, что объединение вершин, смежных с «6(х;) согласно идентификатору а, и вершин, смежных с «)(х)) согласно идентификатору )), включает носитель подмографа (СМ)'.
В рассматриваемом примере имеется пара внешне неустойчи- вых вершин «(х2), и(хт) относительно носителя выделенной за- прещенной фигуры Я. Роль сг играет идентификатор 1, роль |3— либо 2, либо 4. 13.9. Хорактеригачия частичного упорядочения мог афа 23Т 236 Гл. 3. Теория графов и могрофов Согласно соотношению Порециого Ах Ч Вх = Ах Ч Вх Ч АВ в мограф, не нарушая эквивалентности задания им булевой функ- ции, можно добавить слово АВ.
В случае наличия в мографе лары внешне неустойчивых вер- шин слово АВ имеет внд (сг ~ х;) 0 (Д 1 х;). В денном случае это х)хзхг, тан как мограф является дистрибу- тивной решеткой. Добавление слова (х), хз, х41 вызывет неустойчивость запре- щенной фигуры (х)(1, 3), хз(2, 3), хг(1, 2) ); в результате мограф сх = (У1 тз), У = 1х11 хз) х2, хз~ хг~ хз), г = Н* ~,*~) (*,*у)) (*,*ъ ч.), 1 2 з (Х2, Хз, Хг, (Х1, Хз, Хе~~1 4 5 является интерпретируемым в категориях частично упорядочен- ного множества (рис. 3.66, б). При добавлении слов в случае пары внешне неустойчивых вер- шин относительно запрещенной фигуры следует рассмотреть и добавление связей, которые могут привести и появлению допол- ,2) х)(1 х,(1, 2, Я) хт(3, 4) х„ хЗ о ,(З, Я) б Рис.
3.55 нительных запрещенных фигур. Добавление связей (ребер) в мографе имеет место в случае, когда добавляемое слово строго включает носитель запрещенной фигуры. Условия неустойчивости запрещенной фигуры т и п а Б. 1. Запрещенная фигура типа Б неустойчива, если идентификатор слова, взвешивающий висячую вершину, по которому она смежна с вершиной треугольника фигуры, взвешивает еще одну вершину треугольника, Рассмотрим мог раф = (У З2 Зз), У = (х), хв, хз хз, хг, хз), ~2 = 1(х1~ хе~~ (х31 ха~у, хз = 1 х1~ хз, хз, 1хз, хз, хб)1, 1 2 з удовлетворяющий этому условию. Он не содержит устойчивых запрещенных фигур: взаимно однозначное соответствие между первичными термами (буквами мографа) и вершинами струнтур- ного графа, при котором каждое слово взаимно однозначно соот- ветствует пути, имеет вид тх1, Хбу +) Ю(Х1) ( Ю(ХВ)1 1ХЗ) Хгу Я) Ю(ХЯ) ( Ю(ХЗ), (**::**::**:) =")**.'Ы Й:(1ФГ 2.
Запрещенная фигура типа Б неустойчива, если условие 1 выполняетса для двух висячих вершин, и устойчива, если оно выполняется для всех п)рех вершин. Рассмотрим мог раф См = (1' Зз), У = (а, Ь, с, ((, е, у), Зз = На, с, (О, (а, Ь, е), (Ь, с, Л, (а, Ь, су), 1 2 З содержащий неустойчивую запрещенную фигуру типа А Ял = 1а(1, 2), Ь(2, 3), с(1, 3) у и устойчивую запрещенную фигуру типа Б, основанием которой является треугольник с вершинами а, Ь, с и висячими вершинами ((, е, у. Эта фигура будет неустойчивой при добавлении одного из слов (Ь, е, )'), (с, ((, (), (а, ((, г'у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
