Радио раскраска
В теории графов , разделе математики, радиораскраска неориентированного графа — это форма раскраски графа присваиваются метки из положительных целых , при которой графам чисел.такие, что метки соседних вершин отличаются хотя бы на два, а метки вершин, находящихся на расстоянии два друг от друга, отличаются хотя бы на одну. Радиоокраска была впервые изучена Григгсом и Йе (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]
Ссылки
[ редактировать ]- ^ Jump up to: а б с д Броерсма, Хаджо (2005), «Общая основа задач раскраски: старые результаты, новые результаты и открытые проблемы» (PDF) , Комбинаторная геометрия и теория графов (PDF) , Конспекты лекций по Comput. наук., вып. 3330, Springer, Berlin, стр. 65–79, doi : 10.1007/978-3-540-30540-8_7 , ISBN. 978-3-540-24401-1 , МР 2172960 . См., в частности, раздел 3 «Радиораскраска».
- ^ Григгс, Джеррольд Р.; Да, Роджер К. (1992), «Разметка графов с условием на расстоянии 2» , SIAM Journal on Discrete Mathematics , 5 (4): 586–595, doi : 10.1137/0405048 , MR 1186826 .
- ^ Бодлендер, Ханс Л .; Клокс, Тон; Тан, Ричард Б.; ван Леувен, Ян (2000), « λ -раскраска графов», STACS 2000: 17-й ежегодный симпозиум по теоретическим аспектам информатики, Лилль, Франция, 17–19 февраля 2000 г., Труды , Конспекты лекций по информатике, том. 1770, Шпрингер, Берлин, стр. 395–406, номер документа : 10.1007/3-540-46541-3_33 , ISBN. 978-3-540-67141-1 , МР 1781749 .
- ^ Чанг, Джерард Дж.; Куо, Дэвид (1996), « Проблема L (2,1) -маркировки на графах», SIAM Journal on Discrete Mathematics , 9 (2): 309–316, CiteSeerX 10.1.1.51.2004 , doi : 10.1137/S0895480193245339 , МР 1386886 .
- ^ Хаве, Фредерик; Клазар, Мартин; Краточвил, Ян ; Крач, Дитер; Лидлофф, Матье (2011), «Точные алгоритмы для L (2,1) -разметки графов» (PDF) , Algorithmica , 59 (2): 169–194, doi : 10.1007/s00453-009-9302-7 , MR 2765572 , S2CID 2634447 .
- ^ Юноша-Шанявский, Константин; Ржонжевский, Павел (2011), «О сложности точного алгоритма L (2,1) -разметки графов» , Information Processing Letters , 111 (14): 697–701, doi : 10.1016/j.ipl.2011.04. 010 , МР 2840535 .
- ^ Харари, Фрэнк ; Плантхолт, Майкл (1999), «Графы, число радиораскраски которых равно количеству узлов» , Раскраска графов и приложения (Монреаль, Квебек, 1997) , CRM Proc. Конспект лекций, том. 23, Провиденс, Род-Айленд: Американское математическое общество, стр. 99–100, MR 1723637 .