Радиоокраска
Радиоокраска неориентированного графа — это разновидность раскраски графа в теории графов и разделе математики, при которой вершинам графа присваиваются положительные целые значения так, что значения, присвоенные смежным вершинам, различаются как минимум на две, а значения вершин, находящихся на расстоянии двух, различаются как минимум на единицу. Радиоокраска была впервые исследована в работе Григгс & Йе (1992), где использовался иной термин — L(2,1)-маркировка[1][2]. Термин «радиоокраска» был предложен Фрэнком Харэри, поскольку эта задача моделирует назначение каналов в радиовещании с целью предотвращения электромагнитных помех между станциями, находящимися рядом как в графе, так и по спектру частот. Ширина радиоокраски — это максимальное значение, присвоенное вершине, а номер радиоокраски графа — это минимально возможная ширина радиоокраски графа[1]. Например, для графа из двух вершин, соединённых ребром, номер радиоокраски равен 3: имеется радиоокраска с метками 1 и 3, однако использовать только 1 и 2 невозможно.
Вычислительная сложность
Поиск радиоокраски с заданной шириной является NP-полной задачей, даже если рассматривать только плоские графы, сплит-графы или дополнения бипартитных графов[1][3]. Однако для деревьев и кографов задача решается за полиномиальное время[1][4]. Для произвольных графов задача решается за экспоненциальное время, значительно быстрее, чем полный перебор всех возможных раскрасок[5][6].
Другие свойства
Хотя номер радиоокраски n-вершинного графа может изменяться от 1 до 2n - 1, почти все графы на n вершинах имеют номер радиоокраски ровно n. Это связано с тем, что такие графы почти всегда имеют диаметр не менее двух (что требует разных «цветов» для всех вершин, и, соответственно, номер радиоокраски не меньше n), а также почти всегда содержат гамильтонов путь в дополнении графа. Соседним вершинам этого пути можно присвоить последовательные метки, что позволяет выполнить радиоокраску без пропуска номеров[7].