Дробная окраска

Раскраска графа, где элементам графа назначаются наборы цветов

Раскраска 5:2 графа Додекаэдр . Раскраска 4:2 этого графа не существует.

Дробная раскраска — это тема в молодой ветви теории графов , известной как теория дробных графов. Это обобщение обычной раскраски графов . В традиционной раскраске графа каждой вершине в графе назначается некоторый цвет, а смежным вершинам — тем, которые соединены ребрами — должны быть назначены разные цвета. Однако в дробной раскраске каждой вершине графа назначается набор цветов. Требование о смежных вершинах по-прежнему сохраняется, поэтому если две вершины соединены ребром, у них не должно быть общих цветов.

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

Определения

Выше: Раскраска цикла на 5 вершинах в соотношении 3:1 и соответствующая раскраска в соотношении 6:2.
Ниже: Раскраска того же графа в соотношении 5:2.

Раскраска графа G в b - кратное множество — это назначение множеств размера b вершинам графа таким образом, что смежные вершины получают непересекающиеся множества. Раскраска в a : b — это раскраска в b -кратное множество из a доступных цветов. Эквивалентно, ее можно определить как гомоморфизм графа Кнезера KG _{a , b} . Хроматическое число в b -кратное множество — это наименьшее a такое, что существует раскраска в a : b . ${\displaystyle \chi _{b}(G)}$

Дробное хроматическое число определяется как: ${\displaystyle \chi _{f}(G)}$

${\displaystyle \chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}}$

Обратите внимание, что предел существует, поскольку является субаддитивным , что означает: ${\displaystyle \chi _{b}(G)}$ ${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G).}$

Дробное хроматическое число можно эквивалентно определить в вероятностных терминах. Это наименьшее k , для которого существует распределение вероятностей по независимым множествам графа G, такое, что для каждой вершины v , учитывая независимое множество S, взятое из распределения: ${\displaystyle \chi _{f}(G)}$

${\displaystyle \Pr(v\in S)\geq {\frac {1}{k}}.}$

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

У нас есть:

${\displaystyle \chi _{f}(G)\geq {\frac {n(G)}{\alpha (G)}},}$

с равенством для вершинно -транзитивных графов , где n ( G ) — порядок G , α( G ) — число независимости . ^[1]

Более того:

${\displaystyle \omega (G)\leq \chi _{f}(G)\leq \chi (G),}$

где ω( G ) — число клики , а — хроматическое число . ${\displaystyle \chi (G)}$

Более того, дробное хроматическое число приближается к хроматическому числу с точностью до логарифмического множителя ^[2] , фактически:

${\displaystyle {\frac {\chi (G)}{1+\ln \alpha (G)}}\leq \chi _{f}(G)\leq {\frac {\chi _{b}(G)}{b}}\leq \chi (G).}$

Графики Кнезера дают примеры, где: произвольно велико, так как: в то время как ${\displaystyle \chi (G)/\chi _{f}(G)}$ ${\displaystyle \chi (KG_{m,n})=m-2n+2,}$ ${\displaystyle \chi _{f}(KG_{m,n})={\tfrac {m}{n}}.}$

Формулировка линейного программирования (ЛП)

Дробное хроматическое число графа G может быть получено как решение линейной программы . Пусть будет множеством всех независимых множеств G , и пусть будет множеством всех тех независимых множеств, которые включают вершину x . Для каждого независимого множества I определим неотрицательную вещественную переменную x _I. Тогда есть минимальное значение: ${\displaystyle \chi _{f}(G)}$ ${\displaystyle {\mathcal {I}}(G)}$ ${\displaystyle {\mathcal {I}}(G,x)}$ ${\displaystyle \chi _{f}(G)}$

${\displaystyle \sum _{I\in {\mathcal {I}}(G)}x_{I},}$

при условии:

${\displaystyle \sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1}$

для каждой вершины . ${\displaystyle x}$

Двойственная этой линейной программе вычисляет «дробное число клики», релаксацию к рациональным числам целочисленной концепции числа клики . То есть, взвешивание вершин G таким образом, что общий вес, назначенный любому независимому множеству , не превышает 1. Теорема сильной двойственности линейного программирования гарантирует, что оптимальные решения обеих линейных программ имеют одинаковое значение. Однако следует отметить, что каждая линейная программа может иметь размер, экспоненциальный по числу вершин G , и что вычисление дробного хроматического числа графа является NP-трудной задачей . ^[3] Это контрастирует с задачей дробной раскраски ребер графа, которая может быть решена за полиномиальное время. Это является прямым следствием теоремы Эдмондса о соответствующем многограннике. ^{[4] [5]}

Приложения

Приложения дробной раскраски графа включают планирование активности . В этом случае граф G является конфликтным графом : ребро в G между узлами u и v обозначает, что u и v не могут быть активны одновременно. Иначе говоря, набор узлов, которые активны одновременно , должен быть независимым набором в графе G.

Оптимальная дробная раскраска графа в G тогда обеспечивает кратчайшее возможное расписание, так что каждый узел активен в течение (по крайней мере) 1 единицы времени в общей сложности, и в любой момент времени набор активных узлов является независимым набором. Если у нас есть решение x для указанной выше линейной программы, мы просто проходим все независимые наборы I в произвольном порядке. Для каждого I мы позволяем узлам в I быть активными в течение единиц времени; между тем, каждый узел, не входящий в I, является неактивным. ${\displaystyle x_{I}}$

В более конкретных терминах, каждый узел G может представлять радиопередачу в беспроводной сети связи; ребра G представляют помехи между радиопередачами. Каждая радиопередача должна быть активна в течение 1 единицы времени в общей сложности; оптимальная дробная раскраска графа обеспечивает расписание минимальной длины (или, что эквивалентно, расписание максимальной пропускной способности), которое не содержит конфликтов.

Сравнение с традиционной раскраской графа

Если бы дополнительно потребовалось, чтобы каждый узел был активен непрерывно в течение 1 единицы времени (без его периодического включения и выключения), то традиционная раскраска вершин графа обеспечила бы оптимальное расписание: сначала узлы цвета 1 активны в течение 1 единицы времени, затем узлы цвета 2 активны в течение 1 единицы времени и т. д. Опять же, в любой момент времени набор активных узлов является независимым набором.

В общем случае дробная раскраска графа обеспечивает более короткий график, чем недробная раскраска графа; существует разрыв целостности . Возможно, удастся найти более короткий график, ценой включения и выключения устройств (например, радиопередатчиков) более одного раза.

Примечания

1. Шайнерман, Эдвард Р.; Ульман, Дэниел Х. (2013). Дробная теория графов, рациональный подход к теории графов . Dover Publication. стр. 42. ISBN 978-0486485935., Предложение 3.1.1.
2. Ласло Ловаш : «О соотношении оптимальных целых и дробных покрытий», Discrete Math. 13:4(1975), с. 383-390.
3. Карстен Лунд и Михалис Яннакакис : «О сложности аппроксимации задач минимизации», J. ACM 41:5(1994), стр. 960-981.
4. Hajek, B.; Sasaki, G. (1988). «Планирование связей за полиномиальное время». Труды IEEE по теории информации . 34 (5): 910–917. doi :10.1109/18.21215.
5. Шрийвер, Александр (2003). Комбинаторная оптимизация: многогранники и эффективность . Берлин; Гейдельберг; Нью-Йорк, штат Нью-Йорк: Springer-Verlag. стр. 474. ISBN. 978-3540443896.

Ссылки

• Шайнерман, Эдвард Р .; Ульман, Дэниел Х. (1997), Дробная теория графов , Нью-Йорк: Wiley-Interscience, ISBN 978-0-471-17864-4.
• Годсил, Крис ; Ройл, Гордон (2001), Алгебраическая теория графов , Нью-Йорк: Springer-Verlag, ISBN 978-0-387-95241-3.

Смотрите также

• Дробное соответствие