20)Раскраска вершин

Раскрасить вершины графа значит сопоставить каждой вершине графа идентификатор краски таким образом, чтобы кол-во этих красок было минимальным и 2 любые вершины, покрашенные одной краской, не были бы смежные. Если по-простому, то раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа (также можно использовать латинские буквы). Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве . Раскраску можно также рассматривать как разбиение множества вершин , где - множество вершин цвета . Множества называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .

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

Однако хроматическое число может быть и строго больше кликового числа. (Клика — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом. Кликовое число — число (G) вершин в наибольшей клике. Другие названия — густота, плотность. Максимальная клика — клика с максимально возможным числом вершин среди клик графа.)

Стандартный алгоритм раскраски

1.Порождение пустых подграфов, максимальных по включению вершин

2.Формируем бинарную таблицу (столбцы – названия вершин, строки – красок; в клетке (i,j) записываем 1, если J-ая вершина содержится в i-ом пустом подграфе, в противном случае клетку оставляем пустой).

3.Находим покрытия таблицы столбцов строками (такое множество строк, при котором для каждого столбца найдется хотя бы 1 строка из этого множества, на пересечении с которой этот столбец имеет 1, причем при вычеркивании хотя бы 1 элемента из этого множества строк указанное свойство не выполняется).

21)Раскраска ребер

Наряду с задачей о раскраске вершин имеется задача о раскраске ребер графа, когда цвета назначаются ребрам. Раскраска ребер (или реберная раскраска) называется правильной, если любые два ребра, имеющие общую вершину, окрашены в разные цвета. Минимальное число цветов, необходимое для правильной раскраски ребер графа , называется хроматическим индексом графа и обозначается через .

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

Теорема: Для любого графа справедливы неравенства

Все графы делятся на два класса: у одних хроматический индекс равен максимальной степени вершины, у других он на единицу больше. Оказывается, определение принадлежности графа к тому или иному классу является NP-трудной задачей.

Алгоритм вычисления минимальной раскраски аналогичен раскраске вершин.