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

Раскраска графика, при которой элементам графика присваиваются наборы цветов.

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

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

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

Определения

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

b -кратная раскраска графа G — это присвоение вершинам графа множеств размера b так, что соседним вершинам присваиваются непересекающиеся множества. Раскраска a : b — это раскраска в b -кратном порядке из имеющихся цветов. Эквивалентно, его можно определить как гомоморфизм графа Кнезера 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). Дробная теория графов, рациональный подход к теории графов . Дуврское издание. п. 42. ИСБН 978-0486485935., Предложение 3.1.1.
2. Ласло Ловаш : «О соотношении оптимальных целых и дробных покрытий», Discrete Math. 13:4(1975), с. 383-390.
3. Карстен Лунд и Михалис Яннакакис : «О сложности аппроксимации задач минимизации», J. ACM 41:5 (1994), p. 960-981.
4. Хаек, Б.; Сасаки, Г. (1988). «Планирование ссылок за полиномиальное время». Транзакции IEEE по теории информации . 34 (5): 910–917. дои : 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.

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

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