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

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

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 представить как интерференцию радиопередатчиков. Каждый из радиотрансляторов должен работать одну единицу времени в сумме. Оптимальная дробная раскраска обеспечивает минимальное по времени расписание (то есть расписание максимальной пропускной способности) без конфликтов.

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..