Задача о раскраске графа
В отличие от карт на плоскости, вполне очевидно, что не существует фикси- рованной константы k, с которой любой граф имеет k-раскраску: например, если взять множество из n узлов и соединить каждую пару ребром, то для раскраски полученного графа потребуется n цветов. Тем не менее алгоритмическая версия задачи очень интересна:
Для заданного графа G и границы k имеет ли граф G k-раскраску?
Будем называть эту задачу задачей раскраски графа — или k-раскраски, когда мы хотим подчеркнуть конкретный выбор k.
Задача раскраски графа находит очень широкий диапазон применения. Хотя реальная потребность в ней в картографии пока неочевидна, эта задача естествен- ным образом возникает в ситуациях с распределением ресурсов при наличии конфликтов.
♦ Допустим, имеется набор из n процессов в системе, которая позволяет выпол- нять несколько заданий в параллельном режиме. При этом некоторые пары заданий не могут выполняться одновременно, потому что им нужен доступ к некоторому ресурсу. Для следующих k временных квантов требуется сплани- ровать выполнение процессов, чтобы каждый процесс выполнялся минимум в одном из них. Возможно ли это? Если построить граф G на базе множе- ства процессов, соединяя два процесса ребром при наличии конфликта, то k-раскраска G будет представлять план выполнения, свободный от конфликтов: все узлы, окрашенные в цвет j, будут выполняться на шагеj, а вся конкуренция за ресурсы будет исключена.
♦ Другое известное применение задачи встречается при разработке компилято- ров. Предположим, при компиляции программы мы пытаемся связать каждую переменную с одним из к регистров. Если две переменные используются одно- временно, они не могут быть связаны с одним регистром (в противном случае присваивание одной переменной приведет к потере значения другой). Для множества переменных строится граф G; две переменные соединяются ребром в том случае, если они используются одновременно. ^-раскраска G соответству- ет безопасному способу распределения переменных между регистрами: все узлы с раскраской j могут быть связаны с регистром j, так как никакие два из них не используются одновременно.
♦ Третий пример встречается при распределении частот для беспроводной связи: требуется назначить одну из к частот каждому из n устройств; если два устрой- ства находятся достаточно близко друг к другу, им должны быть присвоены разные длины волн для предотвращения помех. Для решения задачи строится граф G для множества устройств; два узла соединяются в том случае, если они расположены достаточно близко для создания помех. В этом случае k-раскраска графа представляет такое назначение частот, при котором все узлы, работающие на одной частоте, находятся достаточно далеко друг от друга, чтобы избежать помех. (Интересно, что в этом применении задачи раскраски графа узлам на- значаются позиции электромагнитного спектра — иначе говоря, в широком смысле это действительно цвета.)
Еще по теме Задача о раскраске графа:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- 3. Задачи и функции социологии