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

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

§ 3.6. Вложение графов 201

На рис. 3.28, а приведены три наикратчайшие цепи, соединяю

щие вершины ООО и 111 в трехмерном кубе. На рис. 3.28, б-г ил

люстрируется рост количества цепей длины 3 в кубах размерности

4, 5, 6 соответственно.

Теорема 3.24. Граф G = (V,U), включающий в себя к

•вершинно не пересекающихся простых цепей длины к между

вершинами а, /3 € V, da{oi, /3) = к, вложим в n-куб Нп, причем

расстояние по Хеммингу между вершинами а и (3 остается

неизменным (т. е. djj(ot, /3) = da(ot, /9) = к), тогда и только

оооо

Рис. 3.29

тогда, когда две любые смежные вершины графа G а, b € V

входят в цикл {а, Ь} € {{а, 6}, {Ь, с}, {с, d}, {d, а}} длины 4

(рис. 3.29) такой, что если

djj(a, а) = maxdff(a, i) = t, г — а, Ь, с, d,

то

b) = dff(a, d) = t - 1, djf(a, с) = t - 2.

Теорема 3.25. В критическом графе Q = (V, U) найдутся

две вершины а, /3, расстояние между которыми равно диа

метру d(a, /3) = d{Q), а число к простых путей на единицу

больше: к = d(Q) + 1.

Сформулируем несколько теорем, позволяющих порождать за

прещенные графы вложения в п-куб.

Теорема 3.26. Если G — критический граф, то граф Т2 (G)

Щакже критический тогда и только тогда, когда степень вер-

щины а больше степени вершины b, т. е. s(a) > s(b) (рис. 3.30),

Ц преобразование не приводит к образованию критического

подграфа (т. е. G не содержит четыре вершинно непересекаю-

Щиеся простые цепи длины 3 между вершинами а, Ь, а подграф

0 графа T2(G) не представляет собой две вершинно непересе-

кающиеся цепи длины 3).

202

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

Теорема 3.27. Замена любого ребра (a, b)£G критическо

го графа G на к вершинно непересекающихся простых цепей

длины 3 тогда и только тогда приводит к образованию кри

тического графа 23(G), когда к удовлетворяет одному из сле

дующих условий'.

1) к = 1, если удаляемое ребро является общим ребром двух

циклов длины 4;

2) к = 2, если s(a) = 3, s(b) = 2 и вершины а, Ь принадлежат

циклу длины 4;

3) к = т + 2 — s(a), если s(a) > s(b) и т = d(G'), где d(G') —

диаметр графа G', полученного из графа G заменой удаленного

ребра цепью длины 3;

4) к = 4, если удаляемое ребро инцидентно вершинам сте

пени 2: s(a) = s(6) = 2.

Рис. 3.30

Теорема 3.28. ГрафТ\(в) (T^(G)) (рис. 3.31) критический

тогда и только тогда, когда является критическим граф G.

Теорема 3.29. Граф 2s(G) критический тогда и только

тогда, когда граф G критический (рис. 3.32).

Теорема 3.30. Если G — критический граф, то граф Tq(G)

критический тогда и только тогда, когда подграф Н содер

жит точку сочленения, и число добавляемых цепей определя

ется из условия

k = d(G') + 1 - s(a),

где а, b € Н при s(a) > s(b), и граф G' получается из графа G

заменой цепи длины 2 между вершинами а, Ь на цепь длины 4

(рис. 3.33, а).

Пример преобразования, задаваемого данной теоремой, для

подграфа Н приведен на рис. 3.33, б, где s(a) = s(b) = 2, диаметр

есть d(Gr) = 4иЛ = 4-Ь1 — 2 = 3.

Множество запрещенных графов вложения в n-куб является

счетным. На рис. 3.34 приведены критические графы с мощ

ностью носителя от 8 до 17, часто встречающиеся на практике.

§3.6. Вложение графов

203

Среди них имеются как графы, полученные с помощью приведен

ных преобразований Г,-, i = 1, 2, ..6, так и графы, не имеющие

предшественников.

При порождении запрещенных фигур необходимо проверить

полученные графы на изоморфизм. Рассмотрим алгоритм установ-

/ \

Рис. 3.31

Рис. 3.32

ления изоморфизма между графами Ga, Gb, основанный на частот

ном разложении моделей Фа(Ga), Ч?ь(вь), построенных по этим

графам.

204

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

1. С помощью алгоритма, приведенного выше, выделяем пол

ные подграфы в графах Ga, Gb- Выделенные подграфы образуют

слова в соответствующих моделях Фа(£ а),

2. Находим частотные разложения моделей Фа(С?а), Фь(Сь).

Определяем равенство коэффициентов в разложениях. Если ча

стотные разложения равны, то графы Ga и Gb изоморфны.

Из равенства разложений тривиально определяем изоморфизм.

Если частотные разложения не равны, то графы Ga и Gb не изо

морфны.

Проиллюстрируем алгоритм иа примере установления изоморфизма между

графами Ga и Gb (рис. 3.35).

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

ными подграфами являются ребра). Отсюда следует, что модели и Фь соот

ветственно совпадают с графами Ga и Gь:

Фа = <V0, S2>, Ка = {а, /3, . . , (},

Si = {{а, Р}, {а, <*}, {а, £}, {/?, е], Ь, Ь> (},

{», е}, {е. <*}. {*, v), {и, rj}, {rj, £ }};

Фб = {Кь, Si}, Vb = {a,b, ..., т},

Sh = {{а, Ь}, {а, с}, {а, d}, (а, е}, {Ь, /} , (с, д},

W fl}> {е, *}, {/, т } , {д, т }, {fc, т }} -

§ 3.6. Вложение графов 205

я-8

п-11

я-12

л -9

пт 10

ш з

Рис. 3.34

206

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

Частотные разложения моделей Фа и Фь имеют следующий вид:

F(\fa) = За2 о 2/32 о 2т2 о 2р2 о 4е2 о 2J2 о 2и о 2г? о 3£2 о

о afl о аб о а( о /Зс о уц о о це о с& о ы> о i/г) о г)$,

F(tyь) = 4а2 о 2Ь2 о 2с2 о 2d2 о 2е2 о 2/ 2 о Зд2 о 2fc2 о З т2 о аЬ о ас о

о ad о ае о bf о сд о dg о ек о fm о дт о кт.

Частотные разложения равны: F^a) = /'’(Фь). Графы Ga и Gb изоморфны.

Для определения изоморфизма устанавливаем взаимно однозначное соответствие

a Р

Рис: 3.35

между буквами с одинаковыми спектрами частот: е ++ а, ц Ь(е), /3 c(d),

i/ е(Ь), Л +* d(c), 7 ++ f(k), a *+ g, rj ++ k(b), f H m.

При определении изоморфизма ориентированных графов в пред

ложенный алгоритм добавляют третий пункт.

3. Если графы Ga и Gb изоморфны без учета ориентации, рас

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

изоморфизма графов с учетом ориентации.

Другой алгоритм определения изоморфизма графов заключа

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

дый из которых состоит из вершин, имеющих равные степени, на

основе подсчета количества ребер, связывающих рассматриваемую

вершину с вершинами этих классов.

Рассмотрим два графа, G„ и Gb (рис. 3.36, а, б). Носитель графа Ga по значе

нию степеней вершин разбивается на четыре класса: К\ = { 1 , 2, 6}, К% = {4},

Кг = {3}, Ка — {5}. Носитель графа Gb также разбивается на четыре класса:

К{ = {Ь, с, /} , K'i = {е}, Кз = {a}, К'А = {<J}. Количество классов и их

мощности совпадают*, следовательно, графы Ga и Gь могут быть изоморфны,

при этом изоморфизм г? отображает, очевидно, вершины 3, 4, 5 в а, е, d соответ

ственно: а = rj(3), е = г7(4), d = г)(5).

Определим количество связей вершин 1, 2, 6 в графе Ga и вершин Ь, с, /

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

таблицу (табл. 3.2), каждой строке которой взаимно однозначно соответствует

§3.6. Вложение графов

207

выделенный класс, столбцу — вершина, а на пересечении (i, j) указывается

количество связей j -й вершины с вершинами i-го класса.

Таблица 3.2

Ч>

v'i

K'i

Кг

1 1 1 2

К[

Кг

0 0 0

Кг

0 1

КА

1 1 1 1 1

Аиалиаируя таблицу, замечаем, что класс Ki разбивается иа два класса:

Ki = {2, 6} и Ks = {1}; класс К{ также разбиваетсяна два класса: К[ = {Ь, / }

И Ks = {с}. Если эти графы изоморфны, то с = г?(1). Для установления соот-

Рис. 3.36

ветствуюших вершин графов Ga, Gb строим таблицу (табл. 3.3) для полученного

разбиения вершин.

Таблица 3.3

Ч>

К!1

2 6 6

0 0

... к 1'

к2

0 0 0

Ki'

Кг

1 1 1

Ki'

к4

1 1

кЦ

Ks 1 1

1 1

ка

Одинаковые столбцы указывают на то, что вершина 2 (вершина 6) может

быть сопоставлена как вершине Ь, так и /. Получено два соответствия, г? и гД

так как окрестности вершин 2 и 6 совпадают. Выбрав одно из них и прове

рив его иа изоморфизм, делаем вывод, чтс рассматриваемые графы изоморфны

(рис. 3.36,в).

208

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

§ 3.7. Раскраска вершин и ребер графа.

Характеризация реберности

Раскраской вершин графа G = (V, U) в к цветов (или к-рас-

краской) называется разбиение носителя V графа G, при котором

каждое подмножество

не содержит ни одной пары смежных вершин. Каждому подмно

жеству сопоставляется цвет, в который окрашивают все элементы

этого подмножества. Вершины, окрашенные в один цвет, будем

называть соцветными.

Хроматическим числом h(G) графа G называется минималь

ное число п, для которого граф имеет n-раскраску. Граф, хрома

тическое число которого равно п, называется п-хроматическим;

если же h(G) < п, то граф G называется п-раскрашиваемым.

Очевидно, что 1-хроматическим граф может быть тогда я толь

ко тогда, когда он является пустым графом.

Для 2-хроматических графов справедлива следующая теорема.

Теорема 3.31 (Кёниг). Граф является 2-хроматическим

тогда и только тогда, когда он не содержит циклов нечет

ной длины.

Отметим, что аналогичная теорема задает и условие двудольно-

сти. Поэтому все 2-хроматические (двуцветные) графы являются

двудольными. Любое дерево, поскольку оно является двудольным

графом, двуцветно. Оценим хроматическое число графа через его

параметры.

Теорема 3.32. Если максимальная степень вершин графа

G равна s(G), то хроматическое число этого графа не превы

шает величины s(G) +1:

Для большинства графов эту оценку можно улучшить.

Теорема 3.33 (Брукс). Граф G со степенью s(G) является

s-раскрашиваемым, за исключением двух случаев:

1) при s(G) > 2 граф G содержит компоненту, являющуюся

полным графом плотности, равной s(G) + 1;

2) при s(G) = 2 граф G содержит компоненту, являющуюся

циклом нечетной длины.

Оценки, полученные с помощью этих теорем, дают, однако,

хорошее приближение лишь тогда, когда степени всех вершин

графа имеют близкие значения. В противном случае оценка может

быть значительно завышена. Например, граф Кёнига К\1П (звезд

ный граф) согласно теореме Брукса является п-раскрашиваемым,

в действительности же он двудольный, и поэтому для его раскраски

достаточно двух красок.

h(G) < s(G) + 1.

(3.17)

§3.7. Раскраска вершин и ребер графа 209

Теорема 3.34 (Берж, Оре, Харрари). Для любого графа G =

= М и> .у,

V<fc(G)<|V|-A+l, (3.18)

Ро

где (За — вершинное число независимости графа.

Теорема 3.35 (Гаддум, Нордхауз). Сумма и произведение

хроматических чисел графа G = (F, U) и его дополнения G =

= (V, U) удовлетворяют неравенствам

]2у/т [ < а д + а д < и + 1 ,

_ 1(И + 1)2Г (ЗЛ9)

\V\ <h{G )-h (G )<

где ] [ — целая часть.

Теорема 3.36. Хроматическое число h(G) графа G удовле

творяет следующим соотношениям:

h(G) < H(Ga) • h(Gb), G = Ga U Gb] (3.20)

h(G) = k(Ga) + h(Gb), G = Ga+ Gb, Ga П Gb = 0; (3.21)

h(G) < min (/i(G„), h(Gb)), G = Ga x G b. (3.22)

Аналогично раскраске вершин графа определим раскраску его

ребер.

Раскраской ребер графа G = (V, U) называется разбиение сиг

натуры U графа U — UUi, Uiar\Uig = 0, о; ф /3, при котором каж-

I Р

дое подмножество £/,■ не содержит ни одной пары смежных ребер.

Каждому подмножеству сопоставляется краска, при этом ребра,

принадлежащие одному и тому же подмножеству, называются со-

цветными. Граф G называется реберно к-раскрашиваемым, если

его ребра можно раскрасить к красками так, чтобы никакие смеж

ные ребра не были окрашены одним цветом.

Хроматическим классом (хроматическим индексом) графа

называется число к такое, что граф является реберно Л-раскраши-

ваемым, но его ребра не могут быть раскрашены в к — 1 цветов.

Хроматический класс графа G обозначается H(G). Например,

хроматические классы для двудольных графов Н(К\^) и Н (#2,з)

равны соответственно 4 и 3.

Хроматический класс H(G) графа G совпадает с хроматиче

ским числом графа G' = (X', Г'), определяемого следующим обра

зом: вершины X ' взаимно однозначно соответствуют ребрам графа

G и х'а € Tij, когда соответствующие ребра графа G смежны. Сле

довательно, задача определения хроматического класса сводится к

Задаче определения хроматического числа.

210

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

В связи со сведением раскраски ребер графа к раскраске его

вершин рассмотрим важное свойство графов — свойство реберно-

сти.

Граф G = {V, U) обладает свойством реберности тогда и толь

ко тогда, когда существует взаимно однозначное соответствие, при

котором каждая вершина и,- 6 V графа G сопоставлена ребру

ыj € U графа G = (V, U), при этом матрица смежности вершин

графа G подобна матрице смежности ребер графа G. Дйе матрицы

подобны, если они совпадают с точностью до перестановки строк

(столбцов). В общем случае граф G может быть мультиграфом,

т. е. графом с параллельными ребрами.

Теорема 3.37. Граф G обладает свойством реберности

тогда и только тогда, когда он разложим по аддитивной опе

рации “объединение" G — UF,- на полные подграфы {F^}, в ко-

торые каждая вершина входит не более двух раз.

Пример 3.13 (рис. 3.37). Рассмотрим свойство ребериости графа

G = (V,U), V = {а, Ь, с, d, е},

U = {{а, 6}, {а, с}, {а, £?}, {а, е}, {Ь, с},{Ь, d}, {с, d}, {с, е}, {d, е}}.

Граф G разложим на два полных подграфа, G = Fa U Fp (рис. 3.37, а):

Fa = (Va, Ua), V. = {а, Ь, с, d},

Ua = {{а , Ь}, {а, с), {а, d>, {b, с}, {Ь, d}, {с, d }},

F0 = (Vp, Up), Vp = {a, c, d, e},

Up — ({fl, c), {fl, d}, {я, e}, {c, d), {c, e), {d, c}J,

VaC\Vp = {a, c, d}.

Условия теоремы 3.37 выполнены, граф G обладает свойством реберности,

соответствующий ему реберно производный граф G изображен иа рис. 3.37, б.

Рис. 3.37 Рис. 3.38