Раскраска упаковки ⇐ Васина Википедия

[wiki_en]

В теории графов «упаковочная раскраска» (также называемая «широковещательной раскраской») — это тип раскраски графа, при котором вершинам присваиваются цвета (представленные положительными целыми числами) так, что расстояние между любыми двумя вершинами одного и того же цвета i больше, чем i. '''упаковочное хроматическое число''' (или '''широковещательное хроматическое число''') \chi_b(G) графа G — это минимальное количество цветов, необходимое для упаковочной раскраски.
== Определение ==
'''Упаковочная раскраска''' графа G = (V,E) — это функция \pi : V \to \{1,2,\ldots,k\ такая, что если \pi(u) = \pi(v), то расстояние d(u,v) > \pi(u). Минимальный k, для которого существует такая раскраска, — это «упаковочное хроматическое число» \chi_b(G).

Эквивалентно, упаковочная раскраска — это раздел \mathcal{P}_\pi = \{V_1, V_2, \ldots, V_k\ набора вершин, где каждый V_i является i-упаковкой (вершины на попарном расстоянии больше, чем i).

== Основные свойства ==
Для любого графа G с n вершинами:
* \omega(G) \leq \chi(G) \leq \chi_b(G), где \omega(G) — кликовый номер, а \chi(G) — хроматическое число
* \chi_b(G) \leq \alpha_0(G) + 1, где \alpha_0(G) — номер покрытия вершины, с равенством тогда и только тогда, когда G имеет диаметр два
* Если \chi_b(G) = \chi(G), то \omega(G) \geq \chi(G) - 2

== Сложность ==
Определить, можно ли решить \chi_b(G) \leq 3 за полиномиальное время, а также определить, является ли \chi_b(G) \leq 4 NP-сложным, даже для плоских графов.

Проблема остается NP-трудной для графов диаметра (теория графов) | диаметра 2, поскольку вычисление числа покрытия вершин для таких графов является NP-трудным.

== Определенные семейства графов ==

Для графов путей P_n:
* \chi_b(P_n) = 2 для 2 \leq n \leq 3
* \chi_b(P_n) = 3 для n \geq 4

Для графов циклов C_n с n \geq 3:
* \chi_b(C_n) = 3, если n равно 3 или кратно 4
* \chi_b(C_n) = 4 иначе

Для дерева (теория графов)|деревьев T порядка n:
* \chi_b(T) \leq (n+7)/4 для всех деревьев, кроме P_4 и двух конкретных деревьев с 8 вершинами
* Звездчатый граф K_{1,n-1} имеет \chi_b(K_{1,n-1}) = 2
* Деревья диаметром 3 имеют \chi_b(T) = 3
* Граница (n+7)/4 является точной и достигается с помощью специальных древовидных конструкций

Для графа гиперкуба Q_k:
* \chi_b(Q_1) = 2
* \chi_b(Q_2) = 3
* \chi_b(Q_3) = 5
* \chi_b(Q_4) = 7
* \chi_b(Q_5) = 15
* \chi_b(Q_k) \sim \frac{1}{2} \cdot O(1/k) \cdot 2^k асимптотически

Для полных графиков K_n:
:\chi_b(K_n) = n

Для двудольного графа G диаметра 3:
:\alpha_0(G) \leq \chi_b(G) \leq \alpha_0(G) + 1

Для полных многодольных графов и колесных графов G:
:\chi_b(G) = \alpha_0(G) + 1

Для графика сетки r \times c G_{r,c}:
* \chi_b(G_{2,c}) = 5 для c \geq 6
* \chi_b(G_{3,c}) = 7 для c \geq 12
* \chi_b(G_{4,c}) = 8 для c \geq 10
* \chi_b(G_{5,c}) = 9 для c \geq 10
* \chi_b(G_{m,n}) \leq 23 для любой конечной сетки

Бесконечная квадратная решетка|квадратная сетка имеет \chi_b \leq 22.

== Характеристики ==

Связный граф G имеет \chi_b(G) = 2 тогда и только тогда, когда G является звездой.

На графике \chi_b(G) = 3 тогда и только тогда, когда его можно сформировать, взяв двудольный мультиграф, разделив каждое ребро ровно один раз, добавив листья к некоторым вершинам и выполнив одну операцию T-добавления к некоторым вершинам.

== Приложения ==
Раскраска упаковки моделирует проблемы с присвоением частот в радиовещании, когда радиостанциям необходимо назначать частоты так, чтобы станции с одинаковой частотой находились на достаточном расстоянии друг от друга, чтобы избежать помех. Требование к расстоянию увеличивается с увеличением мощности транслируемого сигнала.

== Связанные понятия ==
* '''Доминирующая трансляция''': функция b : V \to \{0,1,\ldots\, где b(u) \leq e(u) (эксцентриситет) и каждая вершина с b(v) = 0 имеет соседа u с b(u) > 0 и d(u,v) \leq b(u)
* '''Независимость трансляции''': трансляция, в которой b(u), b(v) > 0 подразумевает d(u,v) > b(u)
* '''(s_1,s_2,\ldots,s_k)-coloring''': обобщение, при котором вершины цветового класса i должны находиться на расстоянии, превышающем s_i друг от друга

== См. также ==
* Раскраска графика
* Раскраска списка
* Дробная окраска
* Ациклическая окраска

Раскраска графа
NP-полные задачи

Подробнее: https://en.wikipedia.org/wiki/Packing_coloring