Хроматическое число. Хроматический класс Хроматическое число


Download 148.42 Kb.
bet1/3
Sana24.10.2020
Hajmi148.42 Kb.
  1   2   3

Хроматическое число. Хроматический класс

Хроматическое число. Это понятие относится к неориентированным графам.

Граф называют -хроматическим, если его вершины можно раскрасить различными цветами так, что никакие две смежные вершины не окрашены одинаково.



Наименьшее число  для которого граф является -хроматическим, называется хроматическим числом неориентированного графа и обозначается через 

Рис. 135.

Например, на карте (рис. 135) изображены 10 департаментов. Ее можно раскрасить четырьмя цветами: голубым В, желтым  зеленым V и красным так, что никакие два соседних департамента не будут окрашены одинаково. Легко проверить, что с меньшим числом цветов этого сделать невозможно.

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



Отыскание хроматического числа графа. Вновь воспользуемся методом Магу 1)

Напомним формулу (30.11)



которая (см. § 30) позволяет получить все внутренне устойчивые подмножества. Принимая во внимание соотношение а  а, можно записать (33 1) в виде



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



Рис. 136


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

где  множество таких индексов а, что 

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

Обозначим через  максимальное внутренне устойчивое множество, соответствующее  Тогда одночлен



в разложении (33.4) указывает следующий способ окраски графа  цветами: окрашиваем цветом  цветом  цветом 

Если представить (33.4) в виде

то хроматическое число графа равно



Пример. Рассмотрим неориентированный граф  соответствующий графу на рис. 120 В силу (30.15)



или


Так как  то имеем





и

 Обозначим



Тогда


Таким образом, граф можно раскрасить тремя цветами: красным  зеленым  и желтым  в соответствии с  Из (33.8) получаем



Исходя из 



На рис. 137 изображены все возможные способы раскраски графа тремя цветами

Приведем теперь несколько теорем о хроматическом числе графа.

Теорема I (


Download 148.42 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling