Задача о раскраске графа

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

Рисунок 5.3 Раскраска графа

Найдем хроматическое число графа (рисунок 5.3.). Вершины 1, 3, 5, 7 - раскрасим в красный цвет, вершины 2, 6, 8 - в желтый и вершину 4 в зеленый. Хроматическое число будет равно 3.

Примеры задач данного типа: распределение ресурсов и составление расписаний.

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

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

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