Слабая раскраска

Слабая раскраска — это специальный вид разметки графа. Слабая $\text{[math]}$ k-раскраска графа $\text{[math]}$ G = (V, E) назначает цвета $\text{[math]}$ c(v) ∈ {1, 2, ..., k} всем вершинам $\text{[math]}$ v ∈ V, так что каждая неизолированная вершина смежна по меньшей мере одной вершине другого цвета. В формальных обозначениях, для любой неизолированной вершины $\text{[math]}$ v ∈ V существует вершина $\text{[math]}$ u ∈ U с $\text{[math]}$ {u, v} ∈ E и $\text{[math]}$ c(u) ≠ c(v).

Слабая 2-раскраска.

Рисунок справа показывает слабую 2-цветную раскраску графа. Каждая тёмная вершина (цвет 1) смежна по меньшей мере с одной светлой вершиной (цвет 2) и наоборот.

Построение слабой 2-раскраски.

СвойстваПравить

Раскраска вершин графа является слабой раскраской, но обратное не обязательно верно.

Любой граф имеет слабую 2-раскраску. Рисунок справа показывает простой алгоритм построения слабой 2-раскраски произвольного графа. Фрагмент (a) показывает исходный граф. Фрагмент (b) показывает дерево поиска в ширину того же графа. Фрагмент (c) показывает, как раскрасить дерево — начиная с корня, уровни дерева раскрашиваются попеременно цветом 1 (тёмный) и 2 (светлый).

Если нет изолированных вершин в графе $\text{[math]}$ G, то слабая 2-раскраска определяет доматическое разбиение — множество вершин с $\text{[math]}$ c(v) = 1 является доминирующим множеством, а множество вершин с $\text{[math]}$ c(v) = 2 является другим доминирующим множеством.

ПриложенияПравить

Исторически, слабая раскраска выступила в качестве первого нетривиального примера задачи на графе, которая может быть решена локальным алгоритмом (распределённым алгоритмом^[en], работающим за постоянное число раундов синхронной передачи). Точнее, если степень каждой вершины нечётна и ограничена константой, то существует распределённый алгоритм слабой 2-раскраски с постоянным временем работы ^[1].

Данный случай отличается от (не слабой) раскраски вершин — не существует распределённого алгоритма раскраски вершин с постоянным временем работы. Лучшие возможные алгоритмы (для поиска минимальной, но не обязательно наименьшей по количеству цветов раскраски) требуют O(log* |V|) раундов передачи ^[1]^[2]^[3]. Здесь log* x — итерированный логарифм от $\text{[math]}$ x.

ПримечанияПравить

↑ ¹ ² Naor, Stockmeyer, 1995, с. 1259–1277.
↑ Linial, 1992, с. 193–201.
↑ Cole, Vishkin, 1986, с. 32–53.

ЛитератураПравить

Moni Naor, Larry Stockmeyer. What can be computed locally? // SIAM Journal on Computing. — 1995. — Т. 24, вып. 6. — С. 1259–1277. — doi:10.1137/S0097539793254571.
Nati Linial. Locality in distributed graph algorithms // SIAM Journal on Computing. — 1992. — Т. 21, вып. 1. — С. 193–201. — doi:10.1137/0221015.
Richard Cole, Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking // Information and Control. — 1986. — Т. 70, вып. 1. — С. 32–53. — doi:10.1016/S0019-9958(86)80023-7.

[_81c8b8b568228e6c-1] ¹ ² Naor, Stockmeyer, 1995, с. 1259–1277.

[_220947e6d84f4d86-2] Linial, 1992, с. 193–201.

[_8b8dadabd3ea8554-3] Cole, Vishkin, 1986, с. 32–53.

[1]

[2]

[3]