НОВОСТИ    БИБЛИОТЕКА    ЭНЦИКЛОПЕДИЯ    БИОГРАФИИ    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

ГРАФА РАСКРАСКА

ГРАФА РАСКРАСКА - приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска - это раскраска вершин (ребер) графа, при к-рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную вершинную раскраску часто наз. просто раскраской графа. Граф наз. k-pаскрашиваемым, если существует правильная вершинная Г. р. к цветами. Наименьшее число цветов, достаточное для правильной вершинной раскраски графа G, наз. хроматическим числом χ(G) графа G. Если χ(G) = k, то граф G наз. k-хроматическим. Граф является 2-хроматическим тогда и только тогда, когда он не содержит простых циклов нечетной длины. Если максимальная степень вершин графа G равна r, то граф G всегда r-раскрашиваем, за исключением двух случаев: 1) r = 2 и G имеет компоненту связности, являющуюся циклом нечетной длины; 2) r > 2 и полный граф с r + 1 вершинами является компонентой связности графа G.

Для объединения двух графов G1 и G2 справедливо неравенство

χ(G1 ∪ G2) ≤ χ(G1)χ(G2),

причем равенство здесь достигается. Более того, если граф G такой, что χ(G) = k = ab, то найдутся подграфы G1 и G2 в G такие, что G = G1 ∪ G2, χ(G1) = a, χ(G2) = b. Если G - граф с n вершинами и G̅ - граф, дополнительный к G, то

причем все границы достигаются. Хроматическим числом χ(S) двумерной поверхности S наз. максимум хроматич. чисел графов, допускающих правильную укладку на S (см. Графа укладка). Для ориентируемой поверхности Sγ рода γ > 0 справедливо равенство

При γ = 0 это равенство принимает вид χ(S0) = 4, что составляет утверждение четырех красок задачи. Пусть f(G, t) - число различных правильных раскрасок графа G с нумерованными вершинами в t или меньше цветов, тогда для любого графа G функция f(G, t) есть многочлен от переменной t, наз. хроматическим многочленом графа G. Напр., хроматич. многочлен любого дерева с n вершинами имеет вид f(G, t) = t(t - 1)n-1. Реберное хроматич. число (хроматический класс) χ'(G) графа G - это наименьшее число цветов, достаточное для правильной раскраски ребер графа G. Если максимальная степень вершин графа G равна k (допускаются кратные ребра), то

k ≤ χ'(G) ≤ [3k/2].

Если при этом кратность каждого ребра не более r, то χ'(G) ≤ k + r. В частности, для графов без петель и кратных ребер k ≤ χ'(G) ≤ k + 1.

Задачи на Г. р. возникают при проектировании коммуникаций, в радиоэлектронике, в планировании эксперимента и других областях.

Лит.: [1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] Оре О., Теория графов, пер. с англ., М., 1968; [3] Шеннон К. Э., «Кибернетический сборник», 1960, в. 2, с. 249-53.

В. Б. Алексеев.


Источники:

  1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.











© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'Математическая библиотека'
Рейтинг@Mail.ru