Слабая раскраска — это специальный вид разметки графа. Слабая -раскраска графа назначает цвета всем вершинам , так что каждая неизолированная вершина смежна по меньшей мере одной вершине другого цвета. В формальных обозначениях, для любой неизолированной вершины существует вершина с и .
Рисунок справа показывает слабую 2-цветную раскраску графа. Каждая тёмная вершина (цвет 1) смежна по меньшей мере с одной светлой вершиной (цвет 2) и наоборот.
Свойства Раскраска вершин графа является слабой раскраской, но обратное не обязательно верно.
Любой граф имеет слабую 2-раскраску. Рисунок справа показывает простой алгоритм построения слабой 2-раскраски произвольного графа. Фрагмент (a) показывает исходный граф. Фрагмент (b) показывает дерево поиска в ширину того же графа. Фрагмент (c) показывает, как раскрасить дерево — начиная с корня, уровни дерева раскрашиваются попеременно цветом 1 (тёмный) и 2 (светлый).
Если нет изолированных вершин в графе , то слабая 2-раскраска определяет доматическое разбиение — множество вершин с является доминирующим множеством, а множество вершин с является другим доминирующим множеством.
Приложения Исторически, слабая раскраска выступила в качестве первого нетривиального примера задачи на графе, которая может быть решена локальным алгоритмом (, работающим за постоянное число раундов синхронной передачи). Точнее, если степень каждой вершины нечётна и ограничена константой, то существует распределённый алгоритм слабой 2-раскраски с постоянным временем работы .
Данный случай отличается от (не слабой) раскраски вершин — не существует распределённого алгоритма раскраски вершин с постоянным временем работы. Лучшие возможные алгоритмы (для поиска минимальной, но не обязательно наименьшей по количеству цветов раскраски) требуют O(log* |V|) раундов передачи . Здесь log* x — итерированный логарифм от .
Примечания
Литература
Категория:Раскраска графа Категория:Распределённые алгоритмы Категория:Задачи распределённых вычислений