Раскраска радио - Radio coloring

Оптимальная (спан-5) радиокраска 6-тактного

В теория графов, раздел математики, радио раскраска из неориентированный граф это форма раскраска графика в котором присваивается положительный целое число метки к графам, например, что метки соседних вершин отличаются как минимум на два, а метки вершин на расстоянии два друг от друга отличаются как минимум на единицу. Радио-раскраску впервые изучил Григгс и Йе (1992), под другим именем, L(2,1)-маркировка.[1][2] Это было названо радио раскраской. Фрэнк Харари потому что он моделирует проблему назначение каналов в радиовещание, избегая электромагнитная интерференция между радиостанциями, которые находятся рядом друг с другом как на графике, так и на назначенных им частотах каналов.

В охватывать окраски радио - это максимальная метка, а радио раскраски номер графа - это наименьший возможный промежуток радиокраски.[1] Например, граф, состоящий из двух вершин с одним ребром, имеет радио-раскраску номер 3: он имеет радио-раскраску с одной вершиной, помеченной 1, а другой - 3, но для радиокраски этого графа нельзя использовать только метки 1 и 2.

Вычислительная сложность

Найти радио-раскраску с заданным (или минимальным) диапазоном НП-полный, даже если они ограничены планарные графы, разделить графики, или дополняет из двудольные графы.[1][3] Однако это разрешимо в полиномиальное время за деревья и кографы.[1][4] Для произвольных графов ее можно решить за одноэкспоненциальное время, значительно быстрее, чем перебор всех возможных раскрасок.[5][6]

Другие свойства

Хотя радио раскраски номер п-вершинный график может принимать значения от 1 до 2п − 1, почти все п-вершинные графы имеют ровно номер радиокраски п. Это потому, что на этих графиках почти всегда диаметр не менее двух (принуждение всех вершин к разным цветам и установление числа радиокраски не менее п), но у них также почти всегда есть Гамильтонов путь в дополнительный граф. Последовательным вершинам в этом пути могут быть назначены последовательные цвета, что позволяет радио-раскраске избегать пропусков каких-либо чисел.[7]

Рекомендации

  1. ^ а б c d Broersma, Hajo (2005), «Общая структура для задач раскраски: старые результаты, новые результаты и открытые проблемы» (PDF), Комбинаторная геометрия и теория графов, Конспект лекций по вычисл. Наук, 3330, Springer, Berlin, стр. 65–79, Дои:10.1007/978-3-540-30540-8_7, МИСТЕР  2172960. См., В частности, Раздел 3, «Раскраска радио».
  2. ^ Griggs, Jerrold R .; Да, Роджер К. (1992), «Маркировка графиков условием на расстоянии 2», Журнал SIAM по дискретной математике, 5 (4): 586–595, Дои:10.1137/0405048, МИСТЕР  1186826.
  3. ^ Бодландер, Ханс Л.; Клокс, Тон; Тан, Ричард Б .; ван Леувен, Ян (2000), "λ-раскрашивание графиков », STACS 2000: 17-й ежегодный симпозиум по теоретическим аспектам компьютерных наук, Лилль, Франция, 17–19 февраля 2000 г., Труды, Конспект лекций по информатике, 1770, Springer, Berlin, стр. 395–406, Дои:10.1007/3-540-46541-3_33, МИСТЕР  1781749.
  4. ^ Чанг, Джерард Дж .; Куо, Дэвид (1996), "The L(2,1)-задача маркировки на графах », Журнал SIAM по дискретной математике, 9 (2): 309–316, CiteSeerX  10.1.1.51.2004, Дои:10.1137 / S0895480193245339, МИСТЕР  1386886.
  5. ^ Хаве, Фредерик; Клазар, Мартин; Кратохвил, Ян; Крач, Дитер; Лидлофф, Матье (2011), "Точные алгоритмы для L(2,1)-маркировка графиков » (PDF), Алгоритмика, 59 (2): 169–194, Дои:10.1007 / s00453-009-9302-7, МИСТЕР  2765572, S2CID  2634447.
  6. ^ Юноша-Сзанявский, Константин; Ржевский, Павел (2011), «О сложности точного алгоритма для L(2,1)-маркировка графиков », Письма об обработке информации, 111 (14): 697–701, Дои:10.1016 / j.ipl.2011.04.010, МИСТЕР  2840535.
  7. ^ Харари, Фрэнк; Плантхольт, Майкл (1999), «Графы, у которых число радиокраски равно количеству узлов», Раскраска графиков и приложения (Montréal, QC, 1997), CRM Proc. Конспект лекций, 23, Провиденс, Род-Айленд: Американское математическое общество, стр. 99–100, МИСТЕР  1723637.