maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2019-3-405-419mais-1231Research ArticleAlgorithmsNP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графаNP-completeness and One Polynomial Subclass of the Two-Step Graph Colouring Problemhttps://orcid.org/0000-0002-1632-5411МедведеваНаталья СергеевнаMedvedevaNatalya Sergeevna

студент

Student

medvedeva270598@mail.ruhttps://orcid.org/0000-0002-0980-2507СмирновАлександр ВалерьевичSmirnovAlexander Valeryevich

канд. физ.-мат. наук., доцент

PhD, Associate Professor

alexander_sm@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201928092019263405419Copyright © Медведева Н.С., Смирнов А.В., 20192019Медведева Н.С., Смирнов А.В.Medvedeva N.S., Smirnov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1231

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

In this paper, we study the two-step colouring problem for an undirected connected graph. It is required to colour the graph in a given number of colours in a way, when no pair of vertices has the same colour, if these vertices are at a distance of 1 or 2 between each other. Also the corresponding recognition problem is set. The problem is closely related to the classical graph colouring problem. In the article, we study and prove the polynomial reduction of the problems to each other. So it allows us to prove NP-completeness of the problem of two-step colouring. Also we specify some of its properties. Special interest is paid to the problem of two-step colouring in application to rectangular grid graphs. The maximum vertex degree in such a graph is between 0 and 4. For each case, we elaborate and prove the function of two-vertex colouring in the minimum possible number of colours. The functions allow each vertex to be coloured independently from others. If vertices are examined in a sequence, colouring time is polynomial for a rectangular grid graph.

двухшаговая раскраска графаNP-полнотаграф решеткипрямоугольный граф решеткиtwo-step graph colouringNP-completenessgrid graphrectangular grid graphИсследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 17-07-00823 А.The reported study was funded by RFBR according to the research project № 17-07-00823 A.ReferencesKorsakov 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.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.Harary F., Graph theory, Addison-Wesley Pub. Co., 1969.Harary F., Graph theory, Addison-Wesley Pub. Co., 1969.Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman and Company, 1979.Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman and Company, 1979.Рублев В. С., Элементы теории графов. Изоморфизм, планарность, маршруты в графах, Ярославль: ЯрГУ, 2010;Rublev V. S., Elementy teorii grafov. Izomorfizm, planarnost’, marshruty v grafakh, Yaroslavl: YSU, 2010, (in Russian).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.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.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.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.

The authors declare that there are no conflicts of interest present.