Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§ 3.9. Характеризация частичного упорядочения мографа 231

них. При выделении циклов нечетной длины в мографе вершины

с одним весом не рассматривают как вершины, которые могут со

ответствовать только висячим вершинам фигур типа Б.

В приведенном выше примере для выделения циклов нечетной

длины достаточно рассмотреть подграф изображенный на

рис. 3.54, а. Анализируя этот мограф, устанавливаем, что запре-

х2(3, б) *4(5)

щенными фигурами типа А являются следующие подмографы:

Qi = {^(З, 6), х5(6, 5), х3(5, 3)},

Q2 = {z2(3, 6), х4(6, 2), x i(2, 1), *6(1, 4), х3(4, 3)},

Qз = {2:5(6, 5), х3(5, 4), х5(4, 1), хх(1, 2), х4(2, 6)}.

Запрещенной фигурой типа Б является подмограф { { 2:2 , х4, Х5},

{ 2:1 , 2:4 }, {х2, х3}, {х5, х4}}.

232

Гл. 3. Теория графов ti мографов

Фигуру типа Б в дальнейшем будем задавать соответствующим

треугольником. В данном случае четвертая запрещенная фигура

имеет следующий вид: Q4 Э { 14(2, 6), 2:5(5, 6), Я2(3, 6)}.

Основное свойство запрещенных фигур типов А и Б заключа

ется в том, что при расщеплении любой вершины фигуры типа А и

любой вершины треугольника фигуры типа Б эти подмографы пе

рестают быть запрещенными фигурами. Таким образом, подобные

расщепления — это способы преобразования запрещенных фигур

типа А и Б в разрешенные. Процедура семантического эквива-

лентирования мографа в частично упорядочиваемый стандартная.

В семантической таблице строкам соответствуют запрещенные фи

гуры типа А или Б, столбцам — расщепляемые вершины мографа.

Семантическая таблица для рассматриваемого примера приведена

в табл. 3.11.

Таблица 3.11

*1(1,2)

*2(3,6)

*3(4,5)

*3(3,4) *3(3,5)

*4(2,6)

*5(5,6)

*5(1,4)

0 1 0

1 1 0

1 0 1

1 1 1

0 1 0 0

1 1

Для уменьшения трудоемкости определения покрытия семан

тической таблицы будем удалять поглощающиеся строки и столбцы,

В данном случае правила поглощения следующие.

Столбец а поглощается столбцом /?, если не найдется

третьего столбца, взвешенного той же буквой, что и столбец а,

и векторное произведение столбцов а и /3 равно столбцу а.

Строка а поглощается строкой /?, если векторное произве

дение этих строк равно строке (3.

В рассматриваемом случае первый и восьмой столбцы погло

щаются шестым. Вычеркивая поглощающиеся столбцы, имеем

шесть покрытий семантической таблицы:

{х2(3, 6), х4(2, 6)}, {х2(3, 6), х5(5, 6)}, {х2(3, 6), z3(4, 5)},

{ i 4(2, 6), х5(5, 6)}, {х3(3, 4), х5(5, 6)}, {х3(3, 5), ж4(2, б)}.

Каждое из этих покрытий порождает два расщепления. Следова

тельно, мощность расширения носителя модели Ф„ равна 2, и

абсолютно минимальная реализация рассматриваемой тупиковой

ДНФ содержит 11 ключей:

L = \Ма\ + \АМа\ = И.

Для определенности рассмотрим последнее покрытие, и будем

отличать букву х3 в третьем слове от х3 в пятом слове, добавляя

штрих в верхнем индексе: х'3. В дальнейшем это переименова

ние будем называть штриховкой буквы в соответствующем слове.

§3.9. Характеризация частичного упорядочения мографа 233

Аналогично произведем штриховку буквы х4 во втором слове. В

результате получаем модель Ф„:

Фа = (М а, S2, 5з>,

Ма = { х г, хи х 2, х3, х'3, х 3, х 4, х'4, х4, х 5, х5},

5 2 = { { х ь х^}, { х 2, х (,}},

5з = {{х х , Хз, * 5}, { * 1, * 3, * 5} , {х 3, х4, х 5}, { х 2, х 4, х 5} } .

Она эквивалентна заданной и интерпретируется в терминах ча

стично упорядоченного множества (рис. 3.54,6):

Хх <-> и(хх), х 2 и (х2), х 3 f* и (х3), Хх и(хх),

Х3 <-> и(х^), х3 <-> и(х3), х4 о и(х4), х^ <-> и(х^),

х4 <-> и(х4), х5 <-> и(х5), х5 <-> и(х5);

при этом

* 1, * 3*5 и(хх) < и (х 3) < и(х5),

ХхХ^ и(хх) < и(х^ ), X2Xg и(х2) < и(хд),

ХхХ3Х5 <-> и (х3) < и(хх) < и(х5),

х 3х4х 5 и(х3) < и (х4) < и(х5),

х 2х 4х 5 и(х2) < и(х4) < и (х 5).

Если в покрытие первой таблицы вошли хотя бы две буквы,

лексикографически одинаковые, то слова, в которых происходит

Их штриховка, определяются покрытием столбцов (букв) строками

(идентификаторами слов), в которые буквы входят.

Таким образом, знание семантики преобразования GM —> Н

позволило заменить перебор 5184 фактически строящихся диа

грамм Н{ анализом шести покрытий семантической таблицы. В

общем случае трудоемкость при знании семантики уменьшается в

комбинаторное число раз по сравнению с количеством всех экви

валентных решений.

Рассмотрим примеры, иллюстрирующие теорему 3.47.

Пример 3.17. Мограф

GM = (V, S2, S3), V = {a,b,c,d,e},

S2 = {{a^e}, {b ^ }. S3 =

12 3

содержит запрещенные фигуры Qi = {b(2, 4), c(4, 3), d(3, 2)}, Q2 = {a(4, 1),

b(4, 2), c(4,> 3)} (рис. 3.55,а), которые порождают семантическую таблицу

(*вбл. 3.12).

Таблица 3.12

Запрещенные

фигуры

a( 1,4)

Ь(2,4) с(3,4)

«*(2,3)

0 1

1 1

1 1 1

234

Гл. 3. Теория графов и мографов

Табл. 3.12имеет три покрытия: iri = {b(2, 4)}, jr2 = {c(3, 4)}, jr3= (а( 1, 4),

<*(2, 3)}; с помощью них исходный мограф можно привести к интерпретируе

мому виду тремя способами, показанными иа рис. 3.55,6.

Рис. 3.55

Пример 3.18. Мограф

GM = (V; S2, S^, V = {а, Ь, с, d],

S2 = {{a jjp , { М ) , { c j* } } , S3 = {{оЛ с}},

12 3 4

содержит три запрещенные фигуры типа А и одну типа Б:

Qi = {<i(l, 4), Ь(2, 4), <*(1, 2)}, Q2 = {Ь(2, 4), с(3, 4), d(2, 3)},

Q3 = {а(1, 4), с(3, 4), d( 1, 3)}, Q4 = {а(1, 4), Ь(2, 4), с(3, 4)};

они порождают семантическую таблицу (табл. 3.13).

Таблица 3.13

Запрещенные

фигуры

а(1,4)

Ь(2,4)

с(3,4)

«*(1,3) Ф ,2 )

<*(2,3)

<?2

1 1 0

1 0 0

1 1 0

Табл. 3.13 имеет шесть покрытий: яч = {а(1, 4), Ь(2, 4)}, jr2 = {а(1, 4),

с(3, 4)}, *3 = {Ь(2, 4), с(3, 4)}, л-4 = {а(1, 4), d(2, 3)}, ж, = {Ь(2, 4), <*(1, 3)},

jre = {с(3, 4), tf(l, 2)}; каждое из них порождает диаграмму Хассе сложности

6. Для определенности выберем первое покрытие, произведя штриховку буквы

§ 3.9. Характеризация частичного упорядочения мографа 235

а в первом слове, буквы Ь — во втором. В результате получаем мограф

GM = {V, 52,5з>, V = {а, а', Ь, Ь', с, d),

52 = {{o ', d}, {У, d}, {с, <*}}, 53 = {{а, Ь, с}},

эквивалентируюший заданный и интерпретируемый в категориях частично упо

рядоченного множества (V, <):

{a', d} и(а') < u(rf), {6', d} и(б') < u(tf),

{с, с/} +* v(c) < 0(d), {а, Ь, с} ++ и(с) < v(a) < v(b).

Рассмотрим устойчивость запрещенных фигур в зависимости

от граничных условий, т. е. от условий пересечения запрещенной

фигуры с остальной частью мографа.

Условие неустойчивости запрещенной фигуры

типа А. Композиция запрещенной фигуры типа А и слова, но

сители которых совпадают, не нарушает условий интерпре

тируемости мографа в категориях частично упорядоченного

множества.

Рассмотрим мограф

GM = (V, S3), V = {хь х2, х2, х3, х4, х5},

S3 = { { д?1, Х2, Х4) , {х2, х3, Х4}, {хи Хз, х5) , {х2, х3, х5}} ,

12 3 4

содержащий запрещенную фигуру типа А

Qa = {*1(1, 3), х3(3, 2), х4(2, 1)}.

При преобразовании этого мографа в структурный граф необ

ходимо расщепить одну из букв xlt х3, х4. Для определенности

расщепляем х4 во втором слове; в результате получаем мограф

6 м = (V, S3), V = {хь х2, х2, х3, х4, х'4, х5},

S3 = {{51, Х2, *4}, {*2, *3, Х4}, {511 *3, Хь), {*2, *3, *5 }},

S.4.I..I ^1 I ✓ Ч 1^,1! ■!!■!■/ > V

...

^ I S/ ■ I" *

1 2 3 4

интерпретируемый в категориях частично упорядоченного множе

ства (рис. 3.56, а).

Введем понятие пары внешне неустойчивых вершин. Парой

внешне неустойчивых вершин относительно подмографа (GM)'

мографа GM называется пара вершин ujt, и/, взвешенных пер

вичными термами х,-, х,-, и* (г,-), г;(х,), таких, что объединение

вершин, смежных с и*(х,-) согласно идентификатору а, и вершин,

смежных с uj(xj) согласно идентификатору /?, включает носитель

подмографа (GM)'.

В рассматриваемом примере имеется пара внешне неустойчи

вых вершин и(хг), v(x2) относительно носителя выделенной за

прещенной фигуры Q. Роль а играет идентификатор 1, роль (3 —

либо 2, либо 4.

236

Гл. 3. Теория графов и мографов

Согласно соотношению Порецкого

Ах V Вх = Ах V Вх V АВ

в мограф, не нарушая эквивалентности задания им булевой функ

ции, можно добавить слово АВ.

В случае наличия в мографе пары внешне неустойчивых вер

шин слово АВ имеет вид

(<*\х^)и {f3\xi).

В данном случае это xix3x4, так как мограф является дистрибу

тивной решеткой.

Добавление слова {xi, хз, х4} вызывет неустойчивость запре

щенной фигуры {xi(l, 3), хз(2, 3), х4(1, 2)}; в результате мограф

GM = (V, 53), V = {хь х2, х2, х3, х4, х5},

Sa = {{zi, х2, х4}, {*2, х3, х4}, {хх, х3, х5},

1 2 3

{х 2, 21з, X s}, {xi, Х3 , X4 j-},

msS ' т" / ^

4 5

является интерпретируемым в категориях частично упорядочен

ного множества (рис. 3.56,6).

При добавлении слов в случае пары внешне неустойчивых вер

шин относительно запрещенной фигуры следует рассмотреть и

добавление связей, которые могут привести к появлению допол-

*2(1)

*1(1.3),

Лз(2, 3,4) \ \ / х 2(2, 4)

% ( 3, 4) хА

Xjd.3.

х3(2,3,4,5)

х5(3, 4)

Рис. 3.56

нительных запрещенных фигур. Добавление связей (ребер) в мо

графе имеет место в случае, когда добавляемое слово строго вклю

чает носитель запрещенной фигуры.

Условия неустойчивости запрещенной фигуры

типа Б. 1. Запрещенная фигура типа Б неустойчива, если иден

тификатор слова, взвешивающий висячую вершину, по кото

рому она смежна с вершиной треугольника фигуры, взвеши

вает еще одну вершину треугольника.

§ 3.9. Характеризация частичного упорядочения мографа 237

Рассмотрим мограф

GM = (V, S2, S3}, V = {хи х6, х2, х3, х4, х5),

S2 = {{^ьД б}, {^ Д 4 ,}}, S3 = {{xi, Хз, ХЪ) , {х2, Хз, Д5}},

12 3 4

удовлетворяющий этому условию. Он не содержит устойчивых

запрещенных фигур: взаимно однозначное соответствие между

первичными термами (буквами мографа) и вершинами структур

ного графа, при котором каждое слово взаимно однозначно соот

ветствует пути, имеет вид

{жг, х6} <-> и(хх) < v(x6), {2:3, х4} <-> и(х4) < и(х3),

ixu Хз, х5| v(xi) < v(x5) < v(x3),

[х2, Хз, х5} <-> v(x2) < v(x5) < v(x3).

2. Запрещенная фигура типа Б неустойчива, если условие 1

выполняется для двух висячих вершин, и устойчива, если оно

выполняется для всех трех вершин.

Рассмотрим мограф

G“ = (V,S3), V = {а, Ь, с, d, е, /},

S3 = {{а ^ с^ }, {bj_c^f}, { а ^ с } } ,

12 3 4

содержащий неустойчивую запрещенную фигуру типа А

Qa = {а(1, 2), 6(2, 3), с(1, 3)}

и устойчивую запрещенную фигуру типа Б, основанием которой

является треугольник с вершинами а, Ь, с и висячими вершинами

d, е, /. Эта фигура будет неустойчивой при добавлении одного из

слов {6, е, /}, {с, d, /} , {a, d, е}.

Частным случаем частичного упорядочения мографа является

транзитивная ориентация графа. Здесь мограф рассматривают без

моделизации, т. е. словами полученной модели являются макси

мально полные подграфы графа, над которым проводится транзи

тивная ориентация.

Для этого случая имеем три запрещенные фигуры. Первыми

двумя фигурами являются фигуры типа Qa и Qb , рассматривае

мые без моделизации, третьей фигурой — граф G%? без модели

зации, являющийся композицией неустойчивой запрещенной фи

гуры типа А и устойчивой фигуры типа Б.

Рассмотрим применение теоремы при транзитивной ориентации графов на

примере представителя одного из транзитивно ие ориентируемых семейств гра

фов — графа, дополняющего цикл, длина которого превышает 5, до пол

ного. Граф G — (V, U) называется транзитивно ориентированным, если из

(i>i, Vj) £ U и (vj, Vk) 6 U следует (и;, Vk) € U. Рассмотрим цикл, длина

которого равна 6. Этот цикл до полного дополняет граф G, изображенный на

рис. 3.57, а.

238

Гл. 3. Теория графов и мографов

Применяя алгоритм выделения полных подграфов к рассматриваемому графу

(рис. 3.57, d), получаем множество полных подграфов {{Ь, d, /} , {а, с, е}, {а, d},

{b, е}, {с, / } } , которое образует сигнатуру мографа (рис. 3.57, в):

GM = (V, S2, 5з>, V = {а, Ъ, с, d, е, /} ,

1 2 3 4 5

Мограф GM = {V, S2, S3) содержит две устойчивые запрещенные фигуры

типа Б: Обi = {Ь, d, /} , {Ь, е}, {а, с/}, {с, /} }, QB2 = {{а, с, е},{а, с/}, {с, /} ,

{Ь, е}}. Расщепляя одну из вершни треугольника каждой запрещенной фи

гуры, получаем транзитивно ориентированный граф. Возможны девять спосо

бов расщепления. В каждом из них следует расщеплять две вершины, так как

эти треугольники ие пересекаются. Для определенности выберем вершины с

Рис. 3.57

и / (рис. 3.57,г). В результате получаем траизитивио ориентированный граф

(рис. 3.57, <?), который после удаления транзитивно замыкающих дуг преобразу

ется в структурный граф (рис. 3.57, е).

§3.10. Логарифмические оценки хроматического числа

_____

239

§ 3.10. Логарифмические оценки хроматического числа.

Решение проблемы четырех красок

Как уже отмечалось, частным случаем квазиполной модели яв

ляется квазиполный граф, который не следует путать с критиче

ским графом, введенным Г.А. Дираком [39].

Критический граф изменяет хроматическое число при удале

нии хотя бы одной вершины. На рис. 3.58 приведен критиче

ский граф, но не квазиполный. Дей

ствительно, сужение сигнатуры графа

удалением одного или всех ребер мно

жества {{а, /}, {6, /}, {с, /}, {d, /},

{е,/}} не меняет хроматическое чис

ло, оно остается постоянным, равным 4;

при удалении же любой вершины хро

матическое число уменьшается на 1.

Теорема 3.48 (основное свойство

квазиполных графов). Для любой вер

шины V{ квазиполного графа Q най

дется такая раскраска его вершин, Рис- 3 58

при которой не существует вершины va (а ф г), соцветкойси,-.

Доказательство проводим от противного. Пусть такая раскраска

не существует, т. е. при каждой раскраске вершин графа Q най

дется вершина va (а ф г), соцветная с и,-. Но тогда после уда

ления вершины Vi и ребер, инцидентных вершине и,-, получаем,

что число красок не изменяется; это противоречит определению

квазиполного графа.

Следствие. При удалении любого ребра из квазиполного

графа его квазиплотность уменьшается на 1.

Теорема 3.48 лежит в основе доказательства структуры ква

зиполного графа Q(q) квазиплотности q; квазиполный граф Q(q)

состоит из основания — квазиполного графа Q(q — 1), замещаю

щего и замыкающего слоев. Вершины замещающего слоя согласно

основному свойству квазиполных графов взаимно однозначно со

ответствуют вершинам основания; при этом соответствующие вер

шины смежны с одними и теми же вершинами, принадлежащими

основанию Q(q — 1). Вершины замещающего слоя являются как

бы “двойниками” вершин основания. Замыкающий слой пред

ставляет собой вершины, конусирующие вершины замещающего

слоя, и число их колеблется от до 1, конусирующих весь

замещающий слой.

Рассмотрим образование квазиполного графа Q(2, к), обладаю

щего экстремальными свойствами, т. е. мощности его носителя

и сигнатуры являются минимальными по сравнению с другими

квазиполными графами плотности 2 и порядка к. Согласно теоре

240

Гл. 3. Теория графов и мографов

ме 3.48, чем меньше мощность носителя или сигнатуры основания

Q(2, fc — 1), тем меньше соответствующие мощности квазиполного

графа Q(2, fc). Основанием графа Q(2, 1) является граф Q(2, 0)

(рис. 3.44, а), представляющий собой ребро {а, Ь}; замещающий

слой — две вершины а1 и V, которые соответственно смежны с

Ь и а. Замыкающий слой представляет собой вершину, конуси-

рующую вершины а' и V. В результате получен цикл длины 5

(рис. 3.44, б).

Аналогично, продолжая процесс построения графов и взяв в

качестве основания Q(2, 1) (рис. 3.44,6), получаем граф Q(2, 2)

(рис. 3.44, в); взяв граф Q(2, 2) в качестве основания, получаем

квазиполный граф Q(2, 3) (рис. 3.44, г). Продолжая этот процесс,

можно построить квазиполный граф Q (2, к) с минимальными мощ

ностями носителя и сигнатуры для любого fc.

Определим зависимость минимальной мощности носителя гра

фа Q(2, fc) от его порядка fc. Имеем

Следовательно,

| W Q (2 , *))| = 2 • (2 • (.. .2 • (2 • 2 + 1) + 1...) + 1) + 1 =

*+1

= 2*+1 + 2к~1 + 2*~2 -(- 2*-3 + ... + 21 + 2° = У ^2* - 2к =

2*+1 -2-2°

1=0

2* = 4 • 2* 2* — 1 = 3 • 2*

2-1

Таким образом, окончательно имеем

M Q (2 ,fc ))[ = 3-2*-l. (3.36)

Найдем зависимость минимальной мощности сигнатуры графа

Q(2, fc) от его порядка. Согласно структуре квазиполных графов

и их основному свойству сумма мощностей сигнатуры основания

Q(2, fc — 1) и сигнатуры замещающего слоя равна утроенной мощ

ности сигнатуры основания Q(2, fc — 1) при построении графа

Q(2, fc) с минимальной мощностью сигнатуры, а мощность сигна

туры замыкающего слоя согласно (3.36) равна мощности носителя

основания 3 • 2к~1 — 1.