Jump to content

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

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

В теории графов слабая раскраска является частным случаем разметки графов . Слабая 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-раскраску. Рисунок справа иллюстрирует простой алгоритм построения слабой 2-раскраски произвольного графа. Часть (a) показывает исходный график. Часть (b) показывает дерево поиска в ширину того же графа. Часть (в) показывает, как раскрасить дерево: начиная с корня, слои дерева окрашиваются поочередно цветами 1 (темный) и 2 (светлый).

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

Приложения

[ редактировать ]

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

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

  1. ^ Jump up to: а б Наор, Мони ; Стокмейер, Ларри (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), «Детерминистическое подбрасывание монеты с применением оптимального ранжирования в параллельных списках», Information and Control , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7 , MR   0853994 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: b7727dfee9014b32c7c879d9d5a08d79__1688308740
URL1:https://arc.ask3.ru/arc/aa/b7/79/b7727dfee9014b32c7c879d9d5a08d79.html
Заголовок, (Title) документа по адресу, URL1:
Weak coloring - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)