Раскраска графов

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

Способ явного выражения хроматического числа через другие инварианты неизвестен.

Практические задачи, сводящиеся к задаче раскраски.

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

Задача распределения оборудования. Даны: множество работ и множество механизмов. Для выполнения каждой из работ необходимо определённое время (пусть равное для всех), и некоторые инструменты. При этом ни один инструмент не может использоваться одновременно в разных работах. Необходимо распределить механизмы так, чтобы время работы было минимальным. В данном случае следует сделать смежными те вершины, соответствующие работам, для выполнения которых требуется один инструмент.

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

Теорема о пяти красках.

Гипотеза четырёх красок. – Одна из самых знаменитых задач теории графов, по известности сравнима с Великой теоремой Ферма. Всякий планарный граф раскрашивается с помощью четырёх красок. Исторически задача связана с раскраской географических карт – сопоставим каждой стране вершину графа. Вершины смежные (проведём ребро), если они имеют общую границу. – Предполагается, что граница не может быть нулевой – не может быть больше трёх стран.

Существуют алгоритмы раскраски графов – можно правильно раскрасить весь граф, кроме последней вершины. В этом случае часть вершин приходится перекрашивать заново. При этом возникают различные конфигурации – числом около 2000. Убедиться в возможности правильной раскраски этих конфигураций человеку практически невозможно – да и нужно ли? В настоящее время гипотеза «доказана» с помощью суперкомпьютера (1000 часов), но как проверить доказательство?

Теорема Грёча. Любой не содержащий треугольников планарный граф 3-раскрашиваем.

Уитни: задача сводится раскрашиванию гамильтоновых планарных графов (!)