Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика
Подождите немного. Документ загружается.
§ 3.8. Квазиполные модели, их структура и свойства
221
Для иллюстрации (3.30) построим замещающий Н(Ф^(3)) и
замыкающий слои П(с(Ф<3(3))) для квазиполного графа Ф<3(3):
Фд(3) = ({<*, Ь, с, d, е}; {{а, 6}, {6, с}, {с, d), {d, е}, {а, е}}),
2(ФЧ(3)) = ({а', 6', с', d\ е', а, Ь, с, d, е}; {{а', е}, {а', Ь},
{а, Ь'}, {Ь\ с}, {Ь, с'}, {с', d}, {с, d'}, {d\ е}, {a', е}, {d, е'}}>,
П(Н(Ф«(3))) = ({/, а', Ь', с', <*', е'};
{{а', /} , {*', /}, W, /} , К , /} , {е', /}}).
Построенный замыкающий слой имеет минимальную мощ
ность (добавилась одна буква — вершина) /; будем говорить, что
вершина / конусирует вершины замещающего слоя. Максималь
ная мощность этого слоя будет равна числу сочетаний из мно
жества букв в замещающем слое {а', Ь', d с1, е'} по q элементов,
q = 3. В нашем случае имеем (|) = 10, в замыкающем слое доба
вятся {/,/ г = 1,2,..., 10}, и он будет иметь следующий вид:
0(Е(Ф<Э(3))) = <{/г, / 2, .. , До, а', Ь', с', d! , е'};
{{Л, а'}, {Л, Ь'}, {Л, с'}, { /2, а'}, { /2, Ь'}, { /2, d'},
{/з, а'}, {/з, Ь'}, {/з, с'}, {/4, а'}, {/4, с'}, {/4, d'},
{/5, а'}, {/5, с'}, {/5, е'}, {/6, а'}, {/6, d'}, {/6, е'},
{/т, Ь'}, {/т, с'}, {/7 , d'}, {/8, 6'}, {/8, с'}, {/8, е'},
{/э, 6х}» .{А» {/э, е'}, {/ю , с'}, {/ю , d'}, { / 10, е'}}).
Граф с минимальной мощностью замыкающего слоя предста
влен на рис. 3.44, в, с максимальной мощностью — на рис. 3.45.
222
Гл. 3. Теория графов и мографов
Теорема 3.44.
Ф = Ф«(д + 1) Ф = Ф<3(д)иН(Ф<3(д)) иП(2(Ф<3(д))). (3.31)
Доказательство. Необходимость.
Дано: Ф = Фд(д + 1).
Требуется доказать, что Ф = Фд(д)иЕ(Фд(д))иО(Е(Фд(д))).
Для доказательства (3.31) необходимо показать, что:
а) Ф = Ф<3(д + 1) ЭЭФд(д);
б) Ф = Ф«(д+ 1) ЭЭ Е(Фд (д));
в) Ф = Ф«(д + 1) ЭЭП(Е(Ф<5(д)));
г) Ф«(д+1)\ (Ф<5(д)иЕ(Ф<5(д))иП(Е(Ф<5(д))) = 0.
Докажем а)-г) по очереди.
а) Предварительно заметим очевидное утверждение, что при
вычеркивании одной буквы из модели Ф число красок (Ф)| мак
симально может уменьшиться только на 1.
Вычеркиваем произвольную букву тпа в одном из элементов
(слов) ца из Фд(д + 1); тогда согласно определению квазиполной
модели и вышеприведенному утверждению имеем
д((Фа = Ф д(9 + 1)) \ ФР(ФР = Ма \ Шв)) = д.
Вычеркиваем в оставшейся модели Фа(д) еще одну произвольную
букву тщ из любого элемента ць] тогда
<?((Фб = Фа \ ФР (Ф Р = Mb)) U (fXb \ ТПЬ))
равняется q — 1 либо д.
Если д(Фь) = д — 1, то букву тпь снова приписываем к элементу
ць
и ее отмечаем.
Если д(Фь) = д, то букву не приписываем к цъ.
Продолжаем этот процесс, т. е. вычеркиваем в оставшейся мо
дели произвольную неотмеченную букву из любого элемента. Если
при этом квазиплотность равна д, то букву не приписываем, и так
далее до тех пор, пока все оставшиеся буквы не будут отмечены.
Полученная модель и есть Фд(д); действительно, ее квазиплот
ность равна д, а при вычеркивании любой буквы равна д — 1, так
как все буквы отмечены.
б), в) Согласно определению квазиполной модели |1^(Фд (д +
+ 1))| = д + 1, и чтобы это равенство было выполнено, очевидно,
необходимо, чтобы при любой Дщт(Фд (9 + 1)) существовала бук
ва т ш, которая была бы смежна с q буквами (входила с ними в
слово), среди которых нет хотя бы двух соцветных букв то„ и тпь
(тпа ф mj); в противном случае
д(Фд(д + 1» т^д+1.
§3.8. Квазиполные модели, их структура и свойства
223
Бели эти g букв при любой минимальной раскраске принадле
жат одной и той же модели типа Ф^(д), то буквы типа тш, обра
зующие множество Мш во-первых, таковы, что
(Vmw € MJ)(т ы g М(Фд (д) = (М, 5Ь 52, . . 5т»),
так как противное утверждение противоречило бы определению
квазиполной модели; во-вторых, ФQ(q) можно рассматривать в
качестве Н(Ф^(д)) по определению замещающей модели и выше
приведенному утверждению (в начале б), в)) Фи.(Фа- = (М^, 5Ы1,
Swz, ..., 5Ыт)) образует замыкающий слой П(Н(Ф^(д))) согласно
(3.30).
Если q букв рассмотренного типа принадлежат различным мо
делям типа ФQ(q), которые, кстати, могут быть выделены с ис
пользованием процедуры, приведенной в а), то согласно (3.28) и
определению Ф*Э(д + 1) среди квазиполных моделей квазиплотно
сти q существует модель Фо(д) = (М0, Solt So2, • • •, Som) такая,
что
(3m_„ 6 К Ш % = (К . Si,, Si,
.......
J%_>) к (П C »?(»))),
((з?'($'=зад # *м. ((*'=К) -* (”• » . i ад».
так как в противном случае согласно (3.28)
(3-Rmin (^о(9)))К^т/э)((т/3 € Мо)к(та ф mp)kN(man тр)))
и N(mJ) = N(ma) = N(mm та) и д(Ф<3(д+ 1)) = д, что проти
воречит заданию.
Следовательно, согласно определениям замещающего и замы
кающего слоев имеем Н(Ф^(д), П(5(Ф^(д))), и при любом
Дтт(Ф®(?) и *(Ф^(д)) U П(Н(Ф^(д))) необходимо g + 1 красок.
г) Ф^(д + 1) \ Фд(д) U Е(Ф^(д)) U П(Н(Ф^(д))) = 0 справед
ливо, так как в противном случае после вычеркивания хотя бы
одной произвольной буквы, входящей в любой элемент разности,
минимальное число красок равнялось бы д+1 согласно доказатель
ству б), в), но это противоречит определению квазиполной модели
квазиплотности д + 1, которая задана.
Достаточность.
Дано: Ф = Ф«(д) U Е(Ф«(д)) U П(5(Ф«(д))).
Требуется доказать, что Ф = Ф^(д + 1).
Согласно определениям замещающего и замыкающего слоев и
определению квазиполной модели имеем |^(Ф)| = g + 1, т. е.
Ф = Ф(д + 1), Ф = Ф9(g) и 5(фв(д)) U П(2(Ф«(д))).
Покажем, что теперь Ф(д + 1) = Ф^(д + 1).
224
Гл. 3. Теория графов и мографов
Это справедливо, так как нельзя вычеркнуть ни одной буквы
тпа из какого-нибудь элемента
Ма = ФГсФ9(д), Н(Ф«(д)), П(2(Ф« (,))),
так, чтобы квазиплотность осталась равной д + 1.
Действительно, если мы вычеркиваем тпа € ца {ца € Фд(д)),
то согласно (3.28) для Вт1п((Ф^(д)\Ф^)и(^а\т)) достаточно д- 1
красок, и при Дщт(0(Е(Фд(д)))) потребуется дополнительный д-й
порядковый номер и д(Ф) = д, что несправедливо, так как д(Ф) —
= д +1.
Аналогично показывается справедливость этого утверждения
при та в ца(ца = Фа, Фа С 5(Фд (д)), П(Е(Фд (д)))).
Для иллюстрации (3.31) рассмотрим увеличение квазиплот
ности на 1, взяв в качестве основания квазиполный граф Q(3)
(рис. 3.46, а). Замещающий слой E(Q(3)) и замыкающий слой
Рис. 3.46
П(Н(<2(3))) представлены на рис. 3.46, б,в соответственно, резуль
тат Q(3) UH(Q(3)) U fi(E(Q(3))) = Q(4) — на рис. 3.46, г.
Рассмотрим некоторые свойства, характеризующие структуру
квазиполных моделей.
§ 3.8. Квазиполные модели, их структура и свойства
______
225
Согласно (3.31) для квазиполных моделей справедливо свой
ство включаемости
Ф «(рД ):Ф ? ({,;), г = 2,3, .., р, j = 0, 1, ..., к. (3.32)
Проиллюстрируем это свойство рассмотрением квазиполной мо
дели <2(3, 2) (см. рис. 3.46,г). Для этой модели имеем
<2(3, 2) ЭЭ <2(3, 1) ЭЭ Q(3, 0),
<2(3, 2) ЭЭ <2(2, 2) ЭЭ <2(2, 1) ЭЭ <2(2, 0),
<2(3, 1) ЭЭ {{а, Ь}, {Ь, /}, {а, /}, {Ь, с}, {с, /},
{с, d}, {d, /}, {d, е}, {е, /}, {а, е}},
<2(3, 0) ЭЭ {{а, &}, {Ь, /}, {а, /}},
<2(2, 2) = {{а, 6}, {Ь, с}, {с, d}, {d, е}, {а, е}, {а', Ь}, {а', е},
{а, ft'}, {*', с}, {Ь, с'}, {с', d}, {с, d'}, {d', е}, {d, е%
{а, е'}, {а', /}, {Ь', /}, {с', /}, {d', /}, {е', /}},
Q(2, 1) = {{а, Ь}, {Ь, с}, {с, d}, {d, е}, {а, е}},
<2(2, 0) = {а, Ь}.
При одной и той же структуре замещающего и закрывающего
Ч#(3), \М.\ = 5 W^(3). lAfcl = 3 Ч#(3+1), \Ма\ =6 Ч#(3+1), 1М„1 =4
ЕОУ6) =4*4 IMQI = 1
Рнс. 3.47
слоев согласно (3.28) и (3.31) для квазиполных моделей имеет ме
сто свойство монотонности
> М (* ? (« ) = (mi, si,, s
.......
s;,»| «
« | М .(Ф ?(? + 1) = (М ., S „„ S.,
........
.S .,))| >
> + 1) = (Mi, Sh , Sh, . . Si,))|. (3.33)
Проиллюстрируем выражение (3.33) на рис. 3.47.
8 В. А. Горбатов
226
Гл.З. Теория графов и мографов
При рассмотрении замещающего и замыкающего слоев как ре
зультата применения операции соответственно замещения Е и за
мыкания 12 над квазиполной моделью Ф^(д) нетрудно показать
свойства идемпотентности операции замещения
K(3(S.. .(S (*«(,))...))) = *(= (*-«(,))) (3.34)
и отсутствие такого у операции замыкания П.
Согласно (3.31) и (3.34) имеем
Ф«(д) U ~ (Ф«(д)) U Е(~(Ф«(д))) U ... U Е(^Е:(Ф<Э(д))).. .)и
п раз
иП(Н(~...(Н(ф9(д)))...) =ф9(д+1). (3.35)
п раз
Проиллюстрируем формулу (3.35) с помощью рис. 3.48. Для д = 4
ф9(4) = Ф^(3) U 5(Ф^(3)) U Е(5(Ф^(3))) U
и = (= (= (^ (3)))) и п(г(=(Е(Фг (з))))).
Очевидно, что всякая квазиполная модель первого порядка
содержит не менее трех слов и всякий квазиполный граф (ква-
Рис. 3.48 Рис. 3.49
зиполная модель плотности 2) первого порядка плотности р
содержит не менее р + 3 вершин (рис. 3.49):
Gq(4,1) = (V,U), \V\ = 7, \V\ = p + 3.
Теорема 3.45.
ф = ф9(р, А)^Ф = Ф<3(р, 1) U
U {~(Ф9(р, 0) U П(Е(Ф<Э(р, i)))/ i = 1, 2, ..., k - 1}.
§ 3.9. Характеризация частичного упорядочения мографа 227
§ 3.9. Характеризация частичного упорядочения мографа
Рассмотрим семантику (смысл) преобразования мографа GM
в диаграмму Хассе (структурный граф) Н при логической интер
претации.
Прежде чем установить причины, приводящие к тому, что од
ному первичному терму сопоставляют две (и более) вершины в
структурном графе (расщепляют первичные термы), рассмотрим
преобразование мографа в структурный граф при задании тупико
вой ДНФ булевой функции
f(xi, х2, ..., х5) = _ _
= Х1 Х3 Х5 V Х1 Х4 V х2 хзV Х1 Х3 Х5 V Х3 Х4 Х5V Х2 Х4 Х5 ,
1 2 3 4 5 6
которая определяется моделью
Фа = (М, 52, S3), М = {xi, хъ х2, х3, х3, х4, х4, х5, ж5},
S2 = {{xi, х4}, {*2, *з}},
S3 = {{^ i, ®з, *s }, {*1, 2:3, *5}, {^з, * 4, 2:5}, {^2, 2:4, 2:5}}.
Мограф См (Фа) изображен на рис. 3.50, а.
Рассмотрим подмограф (GM)' (рис. 3.50, б), задающий третью,
пятую и шестую простые импликанты. Сопоставим третьей им-
пликанте Х2Х3 цепь и(х2) < и(хз). Пятой простой импликанте
Рис. 3.50
*3*42:5 сопоставим цепь и(х3) < и(ж4) < u(xs), шестой импли
канте 122:42:5 — цепь и(я2) < и(х4) < «(is). При таком задании
отношения упорядоченности получаем, что и(х2) < v(x3) < v(x4),
т. е. и(хг) сравнима с и(ж4), и(х2) < 1^(14), что противоречит
заданию. -
228
Гл. 3. Теория графов и мографов
Чтобы ответить на вопрос, является ли такое задание отно
шения < просто неудачным, не зная семантики преобразования,
необходимо построить полностью синтаксическое дерево этого пре
образования, висячим вершинам которого соответствуют диаграм
мы Hi, и рассмотреть при этом не только эти три простые импли-
канты, но весь заданный мограф (7м (Фа). Число висячих вершин
этого дерева равно 2!-2!-3!-3!-3!*3! = 5184. Фактическим построе
нием такого количества диаграмм можно убедиться, что не суще
ствует способа задания отношения < в рассматриваемом мографе
См (Фа), при котором имеет место взаимно однозначное соответ
ствие между первичными термами х°' и вершинами диаграмм Н
такое, что каждая цепь v(xai) < v(xa2) < ... < v(xak) взаимно
однозначно соответствует простой импликанте х01х02.. .хак.
Трудоемкость выявления таких противоречий, а следовательно,
и построения абсолютно минимальной схемы, значительно мень
ше, если известна семантика преобразования, определяемая рас
пределением запрещенных фигур, т. е. решена проблема характе
ризации преобразования GM(f)
Введем понятие гомоморфных моделей.
Разложением, слова /х = {m ,j/ j = 1, 2, ..., s} на глубину к,
О < к < s - 2, называется замена этого слова на (,!*) слов, каждое
из которых образуется взятием s - к букв из слова ц, причем лек
сикографически одинаковые буквы, входящие в полученные слова,
считаются различными и переименовываются. Например, после
разложения слова ц = {у, х, а} на глубину, равную 1, получаем
три слова: {у', я}, {х', а}, {а у}.
Разложением на глубину к подмодели Ф', состоящей из одного
слова ц в модели Ф, называется замена ее подмоделью, образован
ной разложением слова ц на глубину к и повторением каждого
слова ца (ца € Ф \ Ф') вида ц П ца ф 0 столько раз, сколько раз
были повторены буквы (до их переименования при разложении
слова ц), принадлежащие цГ\ ца, причем при построении ца эти
буквы записываются каждый раз в переименованном виде. На
пример, рассмотрим модель
Фа = (М, S2, S 3),
М = {у, х, а, с, о, р},
S2 = {{У, с}, {о, х}, {а, р}}, S3 = {{у, х, а}}.
Разложим ^подмодель Ф^ = {{у, х, а}}, состоящую из слова
ц = {у, х, а}, на глубину, равную 1. В результате разложения этой
подмодели слово ц заменяется словами {у', х}, {х', а}, {а', у};
слова {у, с}, {о, х), {а, р} — словами {у, с}, {у', с}, {о, х}, {о, х'},
{а, р}, {а', р). Окончательно в результате разложения подмодели
§ 3.9. Характеризация частичного упорядочения мографа 229
Ф^ на глубину, равную 1, получаем модель
Фр = (Af, Sj), М = {у, х, а, у', х', а', с, о, р},
= {{у', а:}, {*', а}, {а', у}, {у, с}, {у', с}, {о, я},
{о, х'}, {а, р}, {а', р}}.
Две модели изоморфны, если их матрицы инцидентности по
добны с точностью до переименования букв.
Модели называются гомоморфными, если одна из них преобра
зуется с точностью до изоморфизма в другую разложением неко
торых подмоделей. В рассмотренном примере модели Фа и Фр
(рис. 3.51) являются гомоморфными.
При разложении подмоделей на нулевую глубину получаем изо
морфные модели. Для получения неизоморфных моделей необ
ходимо разлагать на положительную глубину; для этого нужно,
чтобы мощность разлагаемого слова /х, а следовательно, и степень
сигнатуры подмодели Ф' = {ц}, была больше 2, т. е. чтобы модель
Ф' не являлась графом.
Для графов, как известно, существует свое понятие гомомор-
1 физма. Два графа называются гомеоморфными, если один из них
преобразуется с точностью до изомор
физма в другой путем замены неко
торых ребер цепями (разложением
ребра в цепь) произвольной длины.
Например, графы Ga и Gp (рис. 3.52)
Являются гомеоморфными.
В случае графов гомоморфизм
Имеет линейную структуру. Для мо
делей, не являющихся графами, го
моморфизм имеет более сложную
Структуру — сочетательную.
Гомоморфизм (линейный) графов изменяет только мощность
их носителей. Гомоморфизм (сочетательный) моделей, не являю
щихся графами, изменяет не только носители, но и их сигнатуры.
Рис. 3.52
230
Гл.З. Теория графов и мографов
Модель называется частично упорядочиваемой, если найдется
взаимно однозначное соответствие г) между ее буквами и верши
нами диаграммы Хассе, при котором каждое слово модели взаимно
однозначно соответствует цепи, составленной из вершин, соответ
ствующих буквам этого слова.
Теорема 3.46. Модель Ф частично упорядочиваема тогда
и только тогда, когда она не содержит подмодели, гомоморф
ной квазиполной подмодели положительного порядка:
Ф^Ф?(р, fc), fc>o.
На основании этой теоремы и свойства включаемости квази
полных моделей (3.32) имеем теорему 3.47.
Теорема 3.47. Запрещенными фигурами Qa, Qe преобразо
вания мографа GM в диаграмму Н являются подмографы ти
пов А и Б (рис. 3.53).
Подмограф типа А представляет собой цикл нечетной длины
с циклической перестановкой идентификаторов слов. Подмограф
типа Б является треугольником с висячими вершинами, каждая из
которых имеет общий идентификатор со смежной висячей верши
ной, и все вершины треугольника имеют общий идентификатор;
при этом висячие вершины могут совпадать как попарно, так и
все вместе с соответствующим объединением их идентификаторов.
Наличие одной из таких фигур в мографе делает принципиально
невозможным задание отношения < при преобразовании GM —> Н
без расщепления первичных термов в мографе GM, причем такое
расщепление без знания семантики преобразования GM —> Н про
исходит “вслепую” . При этом кроме ликвидации запрещенных
фигур расщепляются лишние первичные термы, что уменьшает
оптимальность получаемого решения.
Выделение запрещенных фигур типов А и Б сводится к за
даче нахождения циклов нечетной длины в мографе с последую
щей проверкой распределения идентификаторов слов (весов) на