Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Понятие раскраски графов

Раскарска графа - приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска - это раскраска вершин (ребер) графа, при которой любые смежные вершины (ребра) окрашены в разные цвета. Правильную вершинную раскраску часто называют просто раскраской графа. Граф называется k-pаскрашиваемым, если существует правильная вершинная раскраска k цветами.

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

Задачи определения хроматического числа и построения минимальной раскраски произвольного графа являются очень сложными. С одной стороны, не известны алгоритмы их решения, сложность которых есть некоторая фиксированная степень от длины записи условий задачи (так называемые полиномиальные алгоритмы). С другой стороны, нигде явно не выражены те потери, которые мы несем от отсутствия таких алгоритмов.

Разумеется, есть лишь конечное число ситуаций, которые надо рассмотреть, чтобы найти хроматическое число n-вершинного графа. Действительно, всего имеется kⁿ различных способов раскраски графа G в k цветов. Перебрав их, мы либо найдем правильную раскраску G в k цветов, либо убедимся, что таковой не существует. Ясно, что это самый примитивный способ решения задачи. Имеется целый ряд значительно более совершенных методов, использующих как оценки, так и другие соображения, призванные сократить перебор.

Раскраску графа можно определить, представить, двумя различными способами. Первый, наиболее понятный: раскраскрасить граф правильно - значит взвесить его, сопоставить его вершинам значения так, что две смежные вершины не могут быть одного значения (цвета).

Обобщенная теорема Эйлера о многогранниках: «Количество граней плоского графа равно его хроматическому числу + 1». В первоначальной формулировке теорема Эйлера о многогранниках звучала так: «Для любого выпуклового многогранника количество вершин минус количество рёбер плюс количество граней равно 2».

Второе определение раскраски графа - раскраской вершин графа G называется разбиение множества вершин Х на l непересекающихся подмножеств Х₁, Х₂,..., Х_l; ХÈХ_I; X_iÇX_j=Æ; i,jÎI={1,2,..,l}, (1) таких, что внутри каждого подмножества X_i не должно содержаться смежных вершин (X_i-внутренне устойчивые подмножества).

Если каждому подмножеству х_i поставить в соответствие определенный цвет, то вершины внутри этого подмножества можно окрасить в один цвет, вершины другого подмножества Х_j - в другой цвет и т.д. до раскраски всех подмножеств.

В этом случае граф называется 1-раскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом c(G).

Очевидно, что полный граф K_n можно раскрасить только n цветами, следовательно, c(К_n) =n. Для связного графа G= (Х,U) с числом ребер m, где (n-1)<m<n(n-1)/2 верхняя оценка хроматического числа c(G) определяется как

c(G)

Нижней оценкой c(G) является число вершин в наибольшем полном подграфе графа G,т.е. его плотность. Известно утверждение, что для любого графа c(G)<1+max r(x_i),где х_i Î Х, iÎI={1,2,...,n},r(x_i)- локальная степень вершины х_i.Приводятся также следующие оценки:

c(G)³n²/(n²-m²); c(G)£n+1-c(G_д),

где G_д= К\G (дополнение графа G до полного К).

Задача раскраски вершин (поиска хроматического числа) графа может быть решена точными или приближенными алгоритмами.

К точным алгоритмам относятся: алгоритм, использующий метод Магу – Вейсмана; алгоритмы, основанные на рассмотрении максимальных r - подграфов и алгоритмы на основе методов целочисленного линейного программирования.

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