Распределенный алгоритм раскраски вершин: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «== Ключевые слова и синонимы == Раскраска вершин; распределенные вычисления == Постановка…»)
 
Строка 3: Строка 3:


== Постановка задачи ==
== Постановка задачи ==
Задача раскраски вершин принимает на вход неориентированный граф G = (V, E) и вычисляет раскраску вершин, т.е функцию c V [k] от некоторого целого положительного значения k, такую, что смежным вершинам присваиваются разные цвета (иначе говоря, c(u) / c(v) для всех (u, v) 2 E). В задаче (A + 1)-раскраски вершин  значение k равно A + 1, где A – максимальная степень входного графа G. В общем случае (A + 1) цветов должно быть достаточно, как показывает пример с кликой. Однако, если граф удовлетворяет определенным свойствам, возможна его раскраска при помощи намного меньшего числа цветов. Нахождение минимально возможного количества цветов представляет собой вычислительно сложную задачу, соответствующие проблемы разрешимости являются NP-полными [ ]. В задаче раскраски Брукса-Визинга цель заключается в нахождении раскрасок, близких к оптимальной.
Задача раскраски вершин принимает на вход неориентированный граф G := (V, E) и вычисляет [[Раскраска графа|раскраску вершин]], т.е функцию <math>c^ V \to [k]</math> от некоторого целого положительного значения k, такую, что смежным вершинам присваиваются разные цвета (иначе говоря, <math>c(u) \ne c(v)</math> для всех <math>(u, v) \in E)</math>. В задаче <math>(\Delta + 1)</math>-раскраски вершин  значение k равно <math>(\Delta + 1)</math>, где <math>\Delta</math> – максимальная степень входного графа G. В общем случае <math>(\Delta + 1)</math> цветов должно быть достаточно, как показывает пример с кликой. Однако, если граф удовлетворяет определенным свойствам, возможна его раскраска при помощи намного меньшего числа цветов. Нахождение минимально возможного количества цветов представляет собой вычислительно сложную задачу, соответствующие проблемы разрешимости являются NP-полными [5]. В задаче раскраски Брукса-Визинга цель заключается в нахождении раскрасок, близких к оптимальной.




В данной статье рассматривается модель вычислений в виде синхронной структуры передачи сообщений, используемой в стандартных распределенных вычислениях [11]. В этом случае цель заключается в описании самых простых алгоритмов, которые могут быть легко реализованы на базы этой распределенной модели и при этом демонстрируют высокие показатели в виде количества необходимых шагов выполнения, а также количества используемых цветов. Количество шагов должно быть полилогарифмическим относительно числа вершин графа n, а количество использованных цветов близким к оптимальному.
В данной статье рассматривается модель вычислений в виде синхронной структуры передачи сообщений, используемой в стандартных распределенных вычислениях [11]. В этом случае цель заключается в описании самых простых алгоритмов, которые могут быть легко реализованы на базы этой распределенной модели и при этом являются эффективными с точки зрения количества необходимых шагов выполнения, а также качественными – с точки зрения количества используемых цветов. Для достижения достаточной эффективности количество шагов должно быть полилогарифмическим относительно числа вершин графа n, а для достижения достаточного качества количество использованных цветов должно быть близким к оптимальному.


== Основные результаты ==
== Основные результаты ==

Версия от 22:55, 2 сентября 2019

Ключевые слова и синонимы

Раскраска вершин; распределенные вычисления

Постановка задачи

Задача раскраски вершин принимает на вход неориентированный граф G := (V, E) и вычисляет раскраску вершин, т.е функцию [math]\displaystyle{ c^ V \to [k] }[/math] от некоторого целого положительного значения k, такую, что смежным вершинам присваиваются разные цвета (иначе говоря, [math]\displaystyle{ c(u) \ne c(v) }[/math] для всех [math]\displaystyle{ (u, v) \in E) }[/math]. В задаче [math]\displaystyle{ (\Delta + 1) }[/math]-раскраски вершин значение k равно [math]\displaystyle{ (\Delta + 1) }[/math], где [math]\displaystyle{ \Delta }[/math] – максимальная степень входного графа G. В общем случае [math]\displaystyle{ (\Delta + 1) }[/math] цветов должно быть достаточно, как показывает пример с кликой. Однако, если граф удовлетворяет определенным свойствам, возможна его раскраска при помощи намного меньшего числа цветов. Нахождение минимально возможного количества цветов представляет собой вычислительно сложную задачу, соответствующие проблемы разрешимости являются NP-полными [5]. В задаче раскраски Брукса-Визинга цель заключается в нахождении раскрасок, близких к оптимальной.


В данной статье рассматривается модель вычислений в виде синхронной структуры передачи сообщений, используемой в стандартных распределенных вычислениях [11]. В этом случае цель заключается в описании самых простых алгоритмов, которые могут быть легко реализованы на базы этой распределенной модели и при этом являются эффективными с точки зрения количества необходимых шагов выполнения, а также качественными – с точки зрения количества используемых цветов. Для достижения достаточной эффективности количество шагов должно быть полилогарифмическим относительно числа вершин графа n, а для достижения достаточного качества количество использованных цветов должно быть близким к оптимальному.

Основные результаты