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

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

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

b-кратная раскраска графа G — это назначение наборов из b цветов вершинам графа таким образом, что смежные вершины не содержат общих цветов.

a:b-раскраска — это b-кратная раскраска, содержащая в общей сложности a цветов.

b-кратное хроматическое число χ_b(G) — это наименьшее a, при котором существует a:b-раскраска.

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

${\displaystyle \chi _{f}(G)=\lim _{b\to \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

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

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

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

и

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

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

Дробное хроматическое число χ_f(G) графа G можно найти решением задачи линейного программирования. Пусть ${\displaystyle {\mathcal {I}}}$(G) — набор всех независимых множеств графа G, и пусть ${\displaystyle {\mathcal {I}}}$(G,x) — все те независимые множества, которые включают вершину x. Для каждого независимого множества ${\displaystyle I}$ определим неотрицательную вещественную переменную x_I. Теперь χ_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-трудной задачей.^[1] Это контрастирует с задачей дробной рёберной раскраски графа, которую можно найти за полиномиальное время, что является прямым следствием теоремы Эдмондса.^[2][3]

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

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

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

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

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

1. ↑ Carsten Lund^[англ.] and Mihalis Yannakakis: "On the hardness of approximating minimization problems", J. ACM 41:5(1994), p. 960-981.
2. ↑ Bruce Hajek and Galen Sasaki: "Link scheduling in polynomial time", IEEE Transactions on Information Theory 34:5(1988), p. 910-917.
3. ↑ Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. — Berlin; Heidelberg; New York, N.Y.: Springer-Verlag, 2003. — С. 474. — ISBN 3540443894.

• Edward R. Scheinerman, Daniel H. Ullman. Fractional graph theory. — New York: Wiley-Interscience, 1997. — ISBN 0-471-17864-0..
• Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — ISBN 0-387-95241-1..