Preview

Моделирование и анализ информационных систем

Расширенный поиск

NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа

https://doi.org/10.18255/1818-1015-2019-3-405-419

Полный текст:

Аннотация

В данной статье рассматривается задача о двухшаговой раскраске произвольного неориентированного связного графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Также в работе ставится соответствующая задача распознавания. Данная задача тесно связана с классической задачей о раскраске графа. В статье рассматривается и обосновывается полиномиальное сведение задач друг к другу. В частности, это позволяет доказать NP-полноту задачи о двухшаговой раскраске. Кроме того, определяются некоторые ее свойства. Отдельно исследуется задача о двухшаговой раскраске в приложении к прямоугольным графам решетки. Максимальная степень вершины таких графов может принимать значение от 0 до 4, и для каждого возможного случая была определена и обоснована функция двухшаговой раскраски в минимальное число цветов. Полученные функции строятся таким образом, что каждая вершина графа может быть раскрашена независимо от остальных, а время раскраски прямоугольного графа решетки полиномиально при последовательном переборе вершин.

Об авторах

Наталья Сергеевна Медведева
Ярославский государственный университет им. П.Г. Демидова
Россия
студент


Александр Валерьевич Смирнов
Ярославский государственный университет им. П.Г. Демидова
Россия
канд. физ.-мат. наук., доцент


Список литературы

1. Korsakov S. V., Smirnov A. V., Sokolov V. A., “Principles of Organizing the Interoperability of Equipollent Nodes in a Wireless Mesh-Network with Time Division Multiple Access”, Automatic Control and Computer Sciences, 50:6 (2016), 415–422.

2. Harary F., Graph theory, Addison-Wesley Pub. Co., 1969.

3. Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman and Company, 1979.

4. Рублев В. С., Элементы теории графов. Изоморфизм, планарность, маршруты в графах, Ярославль: ЯрГУ, 2010;

5. Umans C., Lenhart W., “Hamiltonian Cycles in Solid Grid Graphs”, Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1997, 496– 505.

6. Keshavarz-Kohjerdi F., Bagheri A., “An efficient parallel algorithm for the longest path problem in meshes”, The Journal of Supercomputing, 65:2 (2013), 723–741.


Для цитирования:


Медведева Н.С., Смирнов А.В. NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа. Моделирование и анализ информационных систем. 2019;26(3):405-419. https://doi.org/10.18255/1818-1015-2019-3-405-419

For citation:


Medvedeva N.S., Smirnov A.V. NP-completeness and One Polynomial Subclass of the Two-Step Graph Colouring Problem. Modeling and Analysis of Information Systems. 2019;26(3):405-419. (In Russ.) https://doi.org/10.18255/1818-1015-2019-3-405-419

Просмотров: 127


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)