Алгоритмы раскраски обычно используются в таких приложениях, как планирование, анализ данных, работа в сетях и т.п. Например, рассмотрим задачу назначения времени для собраний длительностью один час, когда на разные собрания приглашаются разные люди и используется разное оборудование. Мы представляем каждое собрание в виде вершины и добавляем ребро между двумя вершинами, если в них задействованы одни и те же человек или оборудование. Нахождение минимальной раскраски говорит нам о необходимости назначить разное время для встреч
Гид по Computer Science
·
Вильям Спрингер
