Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [ 24 ] 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141


Рис. 4.1. Два графа с одинаковыми п, то и распределениями степеней вершин, но с различными хроматическими числами, (а) у (G) = 4. (б) у (G) = 2.

алгоритмов решения задачи о раскраске графа. Здесь мы рассматриваем в ОСНОВНОМ алгоритмы (как точные, так и приближенные ), позволяюш;ие находить (точное или приближенное) значение хроматического числа произвольного графа и соответствую-ш;ую этому значению раскраску вершин.

2. Некоторые теоремы и оценки, относящиеся к хроматическим числам

В разд. 4 гл. 3 было введено понятие кликового числа р (G) графа G (как наибольшего числа вершин в полном порожденном подграфе графа G) и было отмечено, что поскольку между кликами графа G и максимальными независимыми множествами дополнительного графа G существует взаимно однозначное соответствие, то справедливы равенства р (G) = а (G) и р (G) = = a(G).

2.1. Нижние оценки для у {G)

Очевидно, поскольку по крайней мере р (G) цветов требуется для раскраски соответствующей клики графа G (той самой клики, которая определяет кликовое число графа G), что р (G) является



2. ТЕОРЕМЫ О ХРОМАТИЧЕСКИХ ЧИСЛАХ


4 9 3

Рис. 4.2. Граф с р (G). = 2 и у {G) = 5.

нижней оценкой хроматического числа, т. е.

Y (G) р (G). (4.1)

Более того, Зыков [26] доказал, что эта оценка - точная и что разность у {G) - р (G) может быть сколько угодно большой. В действительности Татт [22] показал, что можно построить граф G, который не содержит даже полного подграфа третьего порядка (т. е. р (G) = 2) и который будет иметь произвольно большое заданное значение хроматического числа. На рис. 4.2 изображен граф с р (G) = 2 и Y (С^) = 5.

Поскольку число cs (G) равно мощности наибольшего множества попарно несмежных вершин графа G, то оно совпадает также с мощностью наибольшего множества вершин в G, которые могут быть окрашены в один цвет, и, следовательно,

a{G)

(4.2)

где п - число вершин графа G, а ГжП обозначает наибольшее целое число, не превосходящее числа ) х.

) Число Гх называется щелой частью числа х и часто обозначается через 1х].- Прим. ред.



Если через у (G) обозначить хроматическое число дополнения графа G, то можно записать следующие два неравенства, полученные Нордхаузом и Гаддумом [19]:

Y(G)>L2K J-y(G) (4.3)

и

(4.4)

где LJ означает наименьшее целое число, которое не меньше ) х. Еще одна нижняя оценка для у (G) предложена Геллером [8]:

Майерс и Лин [18] показали, что оценка из (4.1) равномерно мажорирует приведенную выше, и, следовательно, единственное преимущество оценки (4.5) состоит в том, что ее проще вычислять, чем оценку (4.1).

2.2. Верхние оценки для у {G)

Нижние оценки хроматического числа безусловно более интересны, чем верхние, поскольку (если они достаточно близки к истинному значению) они могут быть использованы в процедуре вычисления у (G), включающей дерево поиска. В то же время верхние оценки хроматического числа подобного применения не находят. Тем не менее в литературе приводятся формулы для вычисления верхних оценок хроматического числа; так Бруксом [3] предложена следующая легко вычисляемая оценка:

7(G)<l-f max[d(Xi)4-l]. (4.6)

Другие достаточно точные верхние оценки, также использующие степени вершин графа, можно найти у Уэлша [23] и Вилфа и Секе-реша [21].

Верхние оценки, связывающие значения у (О) ш у (G), приводятся у Нордхауза и Гаддума [19]:

Y (G)< п + 1 - Y (G) (4.7)

и

yiG)<\(Y]ly{G) . (4.8)

Оценки, даваемые формулами (4.3), (4.4), (4.7) и (4.8), являются наилучшими в том смысле, что можно построить графы, на которых эти оценки достигаются. В большинстве случаев, однако, они столь неточны, что не имеют никакой практической значимости.

Это число часто обозначается символом 1а;[.- Прим. ред.



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [ 24 ] 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95