<<
>>

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

Под раскраской графа понимается аналогичный процесс с ненаправленным гра- фом G, в котором узлы играют роль раскрашиваемых областей, а ребра представ- ляют соседние пары. Требуется назначить цвет каждому узлу G так, чтобы при наличии ребра (u, v) узлам и и v были назначены разные цвета; целью является выполнение этих условий с минимальным набором цветов.
В более формальном ва- рианте k-раскраской G называется такая функция f :V^ {1, 2, ..., k}, что для каждого ребра (u, v) выполняется f (u) = f (v). (Таким образом, цвета обозначаются 1, 2, ..., k, а функция f представляет выбор цвета для каждого узла.) Если для G существует k-раскраска, он называется k-раскрашиваемым.

В отличие от карт на плоскости, вполне очевидно, что не существует фикси- рованной константы k, с которой любой граф имеет k-раскраску: например, если взять множество из n узлов и соединить каждую пару ребром, то для раскраски полученного графа потребуется n цветов. Тем не менее алгоритмическая версия задачи очень интересна:

Для заданного графа G и границы k имеет ли граф G k-раскраску?

Будем называть эту задачу задачей раскраски графа — или k-раскраски, когда мы хотим подчеркнуть конкретный выбор k.

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

♦ Допустим, имеется набор из n процессов в системе, которая позволяет выпол- нять несколько заданий в параллельном режиме. При этом некоторые пары заданий не могут выполняться одновременно, потому что им нужен доступ к некоторому ресурсу. Для следующих k временных квантов требуется сплани- ровать выполнение процессов, чтобы каждый процесс выполнялся минимум в одном из них. Возможно ли это? Если построить граф G на базе множе- ства процессов, соединяя два процесса ребром при наличии конфликта, то k-раскраска G будет представлять план выполнения, свободный от конфликтов: все узлы, окрашенные в цвет j, будут выполняться на шагеj, а вся конкуренция за ресурсы будет исключена.

♦ Другое известное применение задачи встречается при разработке компилято- ров. Предположим, при компиляции программы мы пытаемся связать каждую переменную с одним из к регистров. Если две переменные используются одно- временно, они не могут быть связаны с одним регистром (в противном случае присваивание одной переменной приведет к потере значения другой). Для множества переменных строится граф G; две переменные соединяются ребром в том случае, если они используются одновременно. ^-раскраска G соответству- ет безопасному способу распределения переменных между регистрами: все узлы с раскраской j могут быть связаны с регистром j, так как никакие два из них не используются одновременно.

♦ Третий пример встречается при распределении частот для беспроводной связи: требуется назначить одну из к частот каждому из n устройств; если два устрой- ства находятся достаточно близко друг к другу, им должны быть присвоены разные длины волн для предотвращения помех. Для решения задачи строится граф G для множества устройств; два узла соединяются в том случае, если они расположены достаточно близко для создания помех. В этом случае k-раскраска графа представляет такое назначение частот, при котором все узлы, работающие на одной частоте, находятся достаточно далеко друг от друга, чтобы избежать помех. (Интересно, что в этом применении задачи раскраски графа узлам на- значаются позиции электромагнитного спектра — иначе говоря, в широком смысле это действительно цвета.)

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача о раскраске графа:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии