Задача раскраски вершин графа

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

Но задача раскраски в том «чистом» виде, в каком она рассматривается в теории, редко применяется в жизни. Ниже приведены некоторые примеры раскраски, часто встречающиеся на практике. Естественно, что данный список этими примерами не ограничивается.

Составление графиков осмотра (проверки)

В задачах теории расписаний осмотры представляются, в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Требуется составить такой график осмотра, который связан с наименьшими временными затратами (с учетом приведенных выше ограничений на «совместимость» осмотров). Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат.

Задача составления расписания

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

граф алгоритм раскраска вершина.