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

Частный случай маркировки графов в теории графов

В теории графов слабая раскраска является частным случаем разметки графа . Слабая $k$ -раскраска графа $G = (V, E)$ назначает цвет $c (v) \in {1, 2, ..., k$ } каждой вершине $v \in V$ , так что каждая неизолированная вершина смежна по крайней мере с одной вершиной с другим цветом. В обозначениях для каждой неизолированной $v \in V$ существует вершина $u \in V$ с ${u, v} \in E$ и $c (u) \neq c (v)$ .

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

Построение слабой двухцветной раскраски.

Характеристики

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

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

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

Приложения

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

Это отличается от (неслабой) раскраски вершин : не существует распределенного алгоритма с постоянным временем для раскраски вершин; наилучшие возможные алгоритмы (для нахождения минимальной, но не обязательно минимальной раскраски) требуют $O (log * | V |)$ раундов связи. ^[1] $[$ ^2]^[3] Здесь $log * x$ — это итерированный логарифм x .

Ссылки

^ ab Naor, Moni ; Stockmeyer, Larry (1995), «Что можно вычислить локально?», SIAM Journal on Computing , 24 (6): 1259–1277, CiteSeerX 10.1.1.29.669 , doi :10.1137/S0097539793254571, MR 1361156.
^ Линиал, Натан (1992), «Локальность в алгоритмах распределенных графов», SIAM Journal on Computing , 21 (1): 193–201, CiteSeerX 10.1.1.471.6378 , doi :10.1137/0221015, MR 1148825 .
^ Коул, Ричард; Вишкин, Узи (1986), «Детерминированное подбрасывание монеты с применением к оптимальному параллельному ранжированию списков», Информация и управление , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7 , MR 0853994.

[naor-stockmeyer-1995-1] Naor, Moni ; Stockmeyer, Larry (1995), «Что можно вычислить локально?», SIAM Journal on Computing , 24 (6): 1259–1277, CiteSeerX 10.1.1.29.669 , doi :10.1137/S0097539793254571, MR 1361156.

[2] Линиал, Натан (1992), «Локальность в алгоритмах распределенных графов», SIAM Journal on Computing , 21 (1): 193–201, CiteSeerX 10.1.1.471.6378 , doi :10.1137/0221015, MR 1148825 .

[3] Коул, Ричард; Вишкин, Узи (1986), «Детерминированное подбрасывание монеты с применением к оптимальному параллельному ранжированию списков», Информация и управление , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7 , MR 0853994.