В теории графов , в области математики, радио окраски из неориентированного графа является одной из форм раскраски графа , в которой один присваивает положительные целые метки на графики , такие , что метки смежных вершин отличаются , по меньшей мере , два, а метки вершин на расстоянии два друг от друга отличаются как минимум на один. Радио-раскраска была впервые изучена Griggs & Yeh (1992) под другим названием - L (2,1) -метка. [1] [2] Фрэнк Харари назвал это радио-раскраской, потому что он моделирует проблему назначения каналов в радиовещании., избегая при этом электромагнитных помех между радиостанциями, которые находятся рядом друг с другом как на графике, так и на назначенных им частотах каналов.
Оболочка из радио окраска его максимальная этикетки, а также радио - раскраски число графа является наименьшим возможным промежуток радио окраски. [1] Например, граф, состоящий из двух вершин с одним ребром, имеет радио-раскраску номер 3: он имеет радио-раскраску с одной вершиной с меткой 1 и другой с меткой 3, но это невозможно для радио-раскраски этого графа. использовать только метки 1 и 2.
Вычислительная сложность [ править ]
Нахождение радио-раскраски с заданным (или минимальным) промежутком является NP-полным , даже если оно ограничено планарными графами , расщепленными графами или дополнениями к двудольным графам . [1] [3] Однако он разрешим за полиномиальное время для деревьев и кографов . [1] [4] Для произвольных графов это может быть решено за одноэкспоненциальное время , что значительно быстрее, чем перебор всех возможных раскрасок. [5] [6]
Другие свойства [ править ]
Хотя число радиокрасок графа с n вершинами может варьироваться от 1 до 2 n - 1 , почти все графы с n вершинами имеют радиокраску ровно n . Это связано с тем, что эти графы почти всегда имеют диаметр не менее двух (заставляя все вершины иметь разные цвета и заставляя число радиокрасок быть не менее n ), но они также почти всегда имеют гамильтонов путь в дополнительном графе . Последовательным вершинам в этом пути могут быть присвоены последовательные цвета, что позволяет радио-раскраске избежать пропуска каких-либо чисел. [7]
Ссылки [ править ]
- ^ a b c d Broersma, Hajo (2005), "Общая структура для задач раскраски: старые результаты, новые результаты и открытые проблемы" (PDF) , Комбинаторная геометрия и теория графов , Конспекты лекций в Comput. Sci . , 3330 ., Springer, Berlin, стр 65-79, DOI : 10.1007 / 978-3-540-30540-8_7 , MR 2172960. См., В частности, Раздел 3, «Раскраска радио».
- ^ Griggs, Jerrold R .; Е, Роджер К. (1992), "Маркировка графы с условием на расстоянии 2" , SIAM журнал по дискретной математике , 5 (4): 586-595, DOI : 10,1137 / 0405048 , МР 1186826 .
- ^ Bodlaender, Ганс Л. ; Клокс, Тон; Тан, Ричард Б .; ван Леувен, Ян (2000), « λ- раскраска графиков», STACS 2000: 17-й ежегодный симпозиум по теоретическим аспектам информатики, Лилль, Франция, 17–19 февраля 2000 г., Труды , Лекционные заметки по компьютерным наукам, 1770 , . Springer, Berlin, С. 395-406, DOI : 10.1007 / 3-540-46541-3_33 , MR 1781749 .
- ^ Чанг, Джерард Дж .; Kuo, Дэвид (1996), "О L (2,1) -labeling задачи на графах", SIAM журнал по дискретной математике , 9 (2): 309-316, CiteSeerX 10.1.1.51.2004 , DOI : 10,1137 / S0895480193245339 , Руководство по ремонту 1386886 .
- ^ Хаве, Фредерик; Клазар, Мартин; Кратохвил, Ян ; Крач, Дитер; Liedloff, Mathieu (2011), «Точные алгоритмы для L (2,1) -маркировки графов» (PDF) , Algorithmica , 59 (2): 169–194, DOI : 10.1007 / s00453-009-9302-7 , MR 2765572 , S2CID 2634447 .
- ^ Junosza-Szaniawski, Konstanty; Rzążewski, Paweł (2011), "О сложности точного алгоритма L (2,1) -labeling графов" , Information Processing Letters , 111 (14): 697-701, DOI : 10.1016 / j.ipl.2011.04. 010 , Руководство MR 2840535 .
- ^ Харари, Фрэнк ; Plantholt, Michael (1999), «Графы, число радиокрасок которых равно количеству узлов» , Раскраска графов и приложения (Монреаль, Квебек, 1997) , CRM Proc. Конспект лекций, 23 , Провиденс, Род-Айленд: Американское математическое общество, стр. 99–100, MR 1723637 .
