§ 6. Раскраска графа

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

Раскраской вершин графа называется разбиение носителя V графа G на подмножества, при котором каждое подмножество V_i не содержит ни одной пары смежных вершин.

Каждому подмножеству сопоставляется цвет, в который окрашивают элементы этого подмножества.

Хроматическим числом графа G называется минимальное число п (число красок), для которого граф имеет п – раскраску.

Если = п , то граф называется п – хроматическим .

Если (т – число красок и раскраска удовлетворяет определению), то граф называется т – раскрашиваемым .

1 – хроматический граф – это пустой граф.

Теорема 1. Граф является 2 – хроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Двудольный граф – 2-хроматический граф.

Любое дерево – 2-хроматический граф.