|
Algorithms
NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа
Н. С. Медведева, А. В. Смирнов Ярославский государственный университет им. П.Г. Демидова,
ул. Советская, 14, г. Ярославль, 150003 Россия
Аннотация:
В данной статье рассматривается задача о двухшаговой раскраске произвольного неориентированного связного графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Также в работе ставится соответствующая задача распознавания.
Данная задача тесно связана с классической задачей о раскраске графа. В статье рассматривается и обосновывается полиномиальное сведение задач друг к другу. В частности, это позволяет доказать NP-полноту задачи о двухшаговой раскраске. Кроме того, определяются некоторые ее свойства.
Отдельно исследуется задача о двухшаговой раскраске в приложении к прямоугольным графам решетки. Максимальная степень вершины таких графов может принимать значение от 0 до 4, и для каждого возможного случая была определена и обоснована функция двухшаговой раскраски в минимальное число цветов. Полученные функции строятся таким образом, что каждая вершина графа может быть раскрашена независимо от остальных, а время раскраски прямоугольного графа решетки полиномиально при последовательном переборе вершин.
Ключевые слова:
двухшаговая раскраска графа, NP-полнота, граф решетки, прямоугольный граф решетки.
Поступила в редакцию: 14.08.2019 Исправленный вариант: 11.09.2019 Принята в печать: 13.09.2019
Образец цитирования:
Н. С. Медведева, А. В. Смирнов, “NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа”, Модел. и анализ информ. систем, 26:3 (2019), 405–419
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais687 https://www.mathnet.ru/rus/mais/v26/i3/p405
|
Статистика просмотров: |
Страница аннотации: | 126 | PDF полного текста: | 49 | Список литературы: | 17 |
|