Слабая раскраска — это специальный вид разметки графа. Слабая k-раскраска графа G = (V, E) назначает цвета c(v) ∈ {1, 2, ..., k} всем вершинам v ∈ V, так что каждая неизолированная вершина смежна по меньшей мере одной вершине другого цвета. В формальных обозначениях, для любой неизолированной вершины v ∈ V существует вершина u ∈ U с {u, v} ∈ E и c(u) ≠ c(v).
Рисунок справа показывает слабую 2-цветную раскраску графа. Каждая тёмная вершина (цвет 1) смежна по меньшей мере с одной светлой вершиной (цвет 2) и наоборот.
Раскраска вершин графа является слабой раскраской, но обратное не обязательно верно.
Любой граф имеет слабую 2-раскраску. Рисунок справа показывает простой алгоритм построения слабой 2-раскраски произвольного графа. Фрагмент (a) показывает исходный граф. Фрагмент (b) показывает дерево поиска в ширину того же графа. Фрагмент (c) показывает, как раскрасить дерево — начиная с корня, уровни дерева раскрашиваются попеременно цветом 1 (тёмный) и 2 (светлый).
Если нет изолированных вершин в графе G, то слабая 2-раскраска определяет доматическое разбиение — множество вершин с c(v) = 1 является доминирующим множеством, а множество вершин с c(v) = 2 является другим доминирующим множеством.
Исторически, слабая раскраска выступила в качестве первого нетривиального примера задачи на графе, которая может быть решена локальным алгоритмом (распределённым алгоритмом[en], работающим за постоянное число раундов синхронной передачи). Точнее, если степень каждой вершины нечётна и ограничена константой, то существует распределённый алгоритм слабой 2-раскраски с постоянным временем работы [1].
Данный случай отличается от (не слабой) раскраски вершин — не существует распределённого алгоритма раскраски вершин с постоянным временем работы. Лучшие возможные алгоритмы (для поиска минимальной, но не обязательно наименьшей по количеству цветов раскраски) требуют O(log* |V|) раундов передачи [1][2][3]. Здесь log* x — итерированный логарифм от x.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .