Слабая окраска
В теории графов слабая раскраска является частным случаем разметки графов . Слабая k -раскраска графа G = ( V , E ) присваивает цвет c ( v ) ∈ {1, 2, ..., k } каждой вершине v ∈ V такой, что каждая неизолированная вершина является смежной. хотя бы к одной вершине разного цвета. В обозначениях для каждого неизолированного v ∈ V существует вершина u ∈ V такая, что { u , v } ∈ E и c ( u ) ≠ c ( v ) .
На рисунке справа показана слабая 2-раскраска графа. Каждая темная вершина (цвет 1) соседствует хотя бы с одной светлой вершиной (цвет 2) и наоборот.
Характеристики
[ редактировать ]графа Раскраска вершин является слабой раскраской, но не обязательно наоборот.
Любой граф имеет слабую 2-раскраску. Рисунок справа иллюстрирует простой алгоритм построения слабой 2-раскраски произвольного графа. Часть (a) показывает исходный график. Часть (b) показывает дерево поиска в ширину того же графа. Часть (в) показывает, как раскрасить дерево: начиная с корня, слои дерева окрашиваются поочередно цветами 1 (темный) и 2 (светлый).
нет изолированной вершины Если в графе G , то слабая 2-раскраска определяет домашнее разбиение : множество узлов с c ( v ) = 1 является доминирующим множеством , а множество узлов с c ( v ) = 2 — еще один доминирующий набор.
Приложения
[ редактировать ]Исторически слабая раскраска служила первым нетривиальным примером проблемы графа, которую можно решить с помощью локального алгоритма ( распределенного алгоритма , который выполняется за постоянное количество синхронных раундов связи). Точнее, если степень каждого узла нечетна и ограничена константой, то существует распределенный алгоритм слабой 2-раскраски с постоянным временем. [1]
Это отличается от (неслабой) раскраски вершин : не существует распределенного алгоритма с постоянным временем для раскраски вершин; наилучшие возможные алгоритмы (для поиска минимальной, но не обязательно минимальной раскраски) требуют O ( log * | V |) раундов связи. [1] [2] [3] Здесь log * x — повторный x . логарифм
Ссылки
[ редактировать ]- ^ Jump up to: а б Наор, Мони ; Стокмейер, Ларри (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), «Детерминистическое подбрасывание монеты с применением оптимального ранжирования в параллельных списках», Information and Control , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7 , MR 0853994 .