Дробное окрашивание - Fractional coloring

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

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

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

Определения

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

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

В дробное хроматическое число ${ Displaystyle чи _ {е} (G)}$ определяется как

{ displaystyle chi _ {f} (G) = lim _ {b to infty} { frac { chi _ {b} (G)} {b}} = inf _ {b} { гидроразрыв { chi _ {b} (G)} {b}}}

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

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

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

Свойства

У нас есть

{ Displaystyle чи _ {е} (G) geq { гидроразрыва {п (G)} { альфа (G)}},}

{ Displaystyle омега (G) Leq чи _ {f} (G) Leq чи (G),}

где п(г) это порядок из г, α (г) это число независимости, ω (г) это номер клики, и ${ Displaystyle чи (G)}$ это хроматическое число.

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

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

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

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

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

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

при условии

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

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

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

Приложения

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

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

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

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

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

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

Заметки

^ Ласло Ловас: "О соотношении оптимальных целых и дробных покрытий ", Дискретная математика. 13: 4 (1975), стр. 383-390.
^ Карстен Лунд и Михалис Яннакакис: "О сложности аппроксимации задач минимизации ", J. ACM 41: 5 (1994), стр. 960-981.
^ Hajek, B .; Сасаки, Г. (1988). «Планирование ссылок за полиномиальное время». IEEE Transactions по теории информации. 34 (5): 910–917. Дои:10.1109/18.21215.
^ Шрайвер, Александр (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.

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

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

[1] Ласло Ловас: "О соотношении оптимальных целых и дробных покрытий ", Дискретная математика. 13: 4 (1975), стр. 383-390.

[2] Карстен Лунд и Михалис Яннакакис: "О сложности аппроксимации задач минимизации ", J. ACM 41: 5 (1994), стр. 960-981.

[3] Hajek, B .; Сасаки, Г. (1988). «Планирование ссылок за полиномиальное время». IEEE Transactions по теории информации. 34 (5): 910–917. Дои:10.1109/18.21215.

[schrijver-4] Шрайвер, Александр (2003). Комбинаторная оптимизация: многогранники и эффективность. Берлин; Гейдельберг; Нью-Йорк, Нью-Йорк: Springer-Verlag. стр.474. ISBN 978-3540443896.

[1]

[2]

[3]

[4]