Практическое применение раскраски графов

(англ. Spectrum management, англ. frequency allocation)

Термин «распределение частот» объединяет разные типы задач, которые зачастую имеют разные цели и модели[2].

• Планировку моделей распределения (лицензирования, регулирования) радиочастот, максимизирующих использование всего радиоспектра.
• Учёт того, что надо отвести диапазоны и для мобильной, наземной (англ. point-to-point) и спутниковой связи, радио- и телетрансляций.
• Алгоритмы, динамически распределяющие частоты одной конкретной сети между пользователями. Особо интересна тут сотовая связь, в области которой проделан очень большой объём исследований.

Общее между задачами — это то, что они все производят оптимальное распределение ограниченного набора ресурсов радиоспектра между пользователями, количество коих в современных условиях всё время растёт. Два основных направления оптимизации[2]:

• максимизация пропускной способности каналов при сохранении определённого минимального уровня интерференции (помех);
• минимизация интерференции для достижения фиксированной пропускной способности.

В ходе рассмотрения подходящих моделей, возникают задачи не намного сложнее T-раскраски (англ. T-coloring) мультиграфа, списочной T-раскраски (англ. set T-coloring)[2].

Результаты работы над реальной сотовой сетью были применены оператором в своей практической деятельности (проведено оператором E-Plus ( (англ.) en:E-Plus) — 3-м по величине в Германии (на 2010))[3].

Вероятно, любому конкретному виду раскраски найдется применение в составлении расписаний:

• расписания для образовательных учреждений[4];
• расписания в спорте[5];
• планирование встреч, собраний, интервью;
• расписания транспорта, в том числе — авиатранспорта[6];
• расписания для коммунальных служб[7];
• прочие.

Заметную роль в быстродействии программ на компьютере играет время обращения микропроцессора к данным. А именно, процессор может обращаться (перечислим устройства в порядке убывания быстродействия и увеличения объёма) к:

• регистрам процессора,
• кэшу,
• оперативной памяти,
• прочим устройствам.

Далее рассмотрим оптимизации программ, связанные с распределением данных в этих устройствах.

Обобщённо представим задачу так: объекты — некие вычисления, между которыми надо разделить вычислительные ресурсы (процессоры, компьютеры…), могущие работать параллельно друг другу. Какие-то вычисления могут выполняться в параллели друг другу, какие-то — нет. Соответственно, вершинная раскраска графа несовместимости вычислений и представляет собой искомое распределение.

Приведём следующие примеры численных методов, которые таким образом можно распараллелить:

Вычисление матриц производных (якобианов и гессианов) в том случае, когда они разреженные, можно серьёзно ускорить с помощью раскраски графов. Существует проект «Graph Coloring for Computer Derivatives». На его сайте представлены публикации по теме, а также — программный пакет, в который оформили участники проекта свои достижения[www 3]. Для введения в предмет имеются презентации, относящихся к проекту[21].

Для простого случая, когда «уплотнение» производной ограничивается уменьшением количества столбцов, приведём алгоритм.

Вход: функция от вектора — ${\displaystyle F}$ Выход: производная ${\displaystyle F}$ — якобиан или гессиан 1. Исследуем структуру разреженности производной ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ (саму производную вычислять не будем). 2. Составим матрицу ${\displaystyle S\in \lbrace 0;1\rbrace ^{n\times q}}$ уменьшения количества столбцов ${\displaystyle A}$ — англ. seed matrix; составим так, чтобы ${\displaystyle q}$ стало наименьшим. 3. Вычислим значения уплотнённой ${\displaystyle B=AS\in \mathbb {R} ^{m\times q}}$; вычислять будем не по этой формуле, а иным способом. Тут видно, что уменьшенное раньше ${\displaystyle q}$ — количество столбцов ${\displaystyle B}$ 4. И теперь, восстановим значения ${\displaystyle A}$ по ${\displaystyle B}$ (можно некими прямыми методами, можно — решением уравнений).

Место раскраски графа здесь — в вычислении ${\displaystyle S}$. В простых случаях надо вычислять обычную вершинную (англ. distance-1); distance-2 раскраску (которая, в том числе сводится к distance-1 раскраске square graph). В более сложных, требуются небольшие дополнительные ограничения:

• звёздная раскраска (star coloring) — вершинная distance-1, но с дополнительным ограничением: для любого пути из 4 вершин используется не менее 3 цветов;
• ациклическая раскраска (acyclic coloring) — вершинная distance-1 + каждый цикл использует не менее 3 цветов.

В рамках вышеуказанного проекта были проведены вычисления для технических производственных задач:

• процесс хромотографического разделения (из области химии, химической технологии) посредством техники псевдодвижущегося слоя;
• решение задачи оптимального энергетического потока (оптимальное потокоразделение) (электроэнергетика).

Технология цифровых водяных знаков (англ. digital watermarking) позволяет вместе с данными (будь то медиафайлы, исполняемые файлы и прочие) передать некое скрытое сообщение («водяной знак», Watermark). Такое скрытое сообщение может быть применено в защите авторских прав для идентификации владельца данных.

Это важно, например, для установления источника их распространения нелегальным образом. Или же для подтверждения прав на данные, например — программное обеспечение систем на кристалле (system-on-chip). Сообщение можно закодировать в том числе и в графе. Одну из таких техник предложили Qu и Potkonjak (поэтому её иногда называют QP-алгоритмом)[22].

Состоит она вот в чём: допустим, у нас есть граф G, раскраска которого используется в программе — причём, используется так, что допустимо поменять содержимое графа с небольшим увеличением его хроматического числа. Что важно, одним из таких примеров является граф несовместимости распределения регистров процессора, о котором говорилось выше, — а значит, мы сможем закодировать послание в программном продукте с помощью распределения регистров.

Извлечь его можно путём сравнения полученного графа с исходным; существуют и способы удостовериться в том, было ли некое сообщение закодировано в графе без использования исходного[23].

Имеется развитие, уточнение Qu и Potkonjak, попытки улучшения алгоритма[24],[25],[23].

Отметим, что имеется программный пакет SandMark, в котором исполнены алгоритмы такого рода[24],[25]. Он доступен для скачивания[www 4].

• Классическая задача о раскраске карт: вершины — страны; рёбра — общие границы. Такой граф, соответствующий карте, планарен, — а значит, по теореме о 4 красках, всегда χ ≤ 4.
• Расчёт сетей ОКС-7 (некое обобщение телефонных сетей); а именно, раскраска мультиграфа с некоторыми ограничениями нужна при маршрутизации пакетов с учётом равномерной нагрузки[26]. РУДН, в том числе его сотрудник Самуйлов, принимал активное участие в расчёте междугородной сети ОКС-7 России[27].
• Кластерный анализ (разделение объектов на т. н. кластеры; в рамках кластера объекты имеют похожие свойства и/или кластеры имеют отчётливые различия)[28].
• Решение судоку: 9 цифр судоку — 9 цветов. Вершины графа несовместимости — клетки таблицы. Рёбра между ${\displaystyle (x,y)}$ и ${\displaystyle (x',y')}$ проводим тогда и только тогда, когда:
  • ${\displaystyle x=x'}$, или,
  • ${\displaystyle y=y'}$, или,
  • ${\displaystyle \lceil x/3\rceil =\lceil x'/3\rceil }$ и ${\displaystyle \lceil y/3\rceil =\lceil y'/3\rceil }$.
• Конструирование устройств, где провода, соединённые в одном узле, должны для удобства различения иметь разные цвета.

• [www 5] — хороший источник ссылок на информацию по многим аспектам применения
• [www 6], хоть и на 2010 год уже очень давно не обновляемая.