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

17.06.2022

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

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

Определения

b-кратная раскраска графа G — это назначение наборов из b цветов вершинам графа таким образом, что смежные вершины не содержат общих цветов. a:b-раскраска — это b-кратная раскраска, содержащая в общей сложности a цветов. b-кратное хроматическое число χb(G) — это наименьшее a, при котором существует a:b-раскраска.

Дробным хроматическим числом χf(‘‘G’’) называется

χ f ( G ) = lim b → ∞ χ b ( G ) b = inf b χ b ( G ) b {displaystyle chi _{f}(G)=lim _{b o infty }{frac {chi _{b}(G)}{b}}=inf _{b}{frac {chi _{b}(G)}{b}}}

Заметим, что предел существует, поскольку χb(G) субаддитивна, что означает χa+b(G) ≤ χa(G) + χb(G).

Дробное хроматическое число можно также определить в терминах теории вероятности. χf(G) — это наименьшее k, для которого существует распределение вероятности на независимых множествах графа G такое, что для любой вершины v и независимого множества S

Pr ( v ∈ S ) ≥ 1 k {displaystyle Pr(vin S)geq {frac {1}{k}}} .


Несколько свойств χ f ( G ) {displaystyle chi _{f}(G)} :

χ f ( G ) ≥ n ( G ) / α ( G ) {displaystyle chi _{f}(G)geq n(G)/alpha (G)}

и

ω ( G ) ≤ χ f ( G ) ≤ χ ( G ) {displaystyle omega (G)leq chi _{f}(G)leq chi (G)} .

Здесь n(G) — порядок графа G, α(G) — число независимости, ω(G) — кликовое число, а χ(G) — хроматическое число.

Дробное хроматическое число в терминах линейного программирования

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

∑ I ∈ I ( G ) x I {displaystyle sum _{Iin {mathcal {I}}(G)}x_{I}} , при ограничениях ∑ I ∈ I ( G , x ) x I ≥ 1 {displaystyle sum _{Iin {mathcal {I}}(G,x)}x_{I}geq 1} для каждой вершины x {displaystyle x} .

Двойственная задача этой задачи линейного программирования вычисляет "дробное кликовое число", ослабление до дробных чисел целочисленной концепции кликового числа. Таким образом, можно ввести вес для вершин графа G, при котором суммарный вес любого независимого множества не превосходит 1. Согласно теореме о строгой двойственности задач линейного программирования оптимальные решения обеих задач совпадают. Заметим, однако, что обе задачи имеют размер, экспоненциально зависящий от числа вершин графа G, так что вычисление дробного хроматического числа графа является NP-трудной задачей. Это контрастирует с задачей дробной рёберной раскраски графа, которую можно найти за полиномиальное время, что является прямым следствием теоремы Эдмондса.

Приложения

Дробная раскраска графа используется в календарном планировании. В этом случае граф G является графом конфликтов — ребро в G между вершинами u и v означает невозможность выполнения u и v одновременно. Тогда работы, выполняемые одновременно, должны быть независимым множеством в графе G.

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

Более конкретный пример. Пусть каждая вершина графа Gрадиотранслятор в беспроводной сети. Тогда можно рёбра G представить как интерференцию радиопередатчиков. Каждый из радиотрансляторов должен работать одну единицу времени в сумме. Оптимальная дробная раскраска обеспечивает минимальное по времени расписание (то есть расписание максимальной пропускной способности) без конфликтов.

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

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

Как правило, дробная раскраска графа даёт более короткое расписание, чем обычное. Но это более короткое расписание получается за счёт включения/выключения устройств (таких как радиотансляторы) больше одного раза.



Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru © 2022
При цитировании информации ссылка на сайт обязательна.
Копирование материалов сайта ЗАПРЕЩЕНО!