maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2022-3-166-180mais-1710Research ArticleAlgorithmsДвухшаговая раскраска графов решетки различных типовTwo-Step Colouring of Grid Graphs of Different Typeshttps://orcid.org/0000-0002-0980-2507СмирновАлександр ВалерьевичSmirnovAlexander Valeryevichalexander_sm@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation202225092022293166180Copyright © Смирнов А.В., 20222022Смирнов А.В.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/1710

В данной статье рассматривается NP-трудная задача о двухшаговой раскраске графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Оптимальной считается двухшаговая раскраска в минимально возможное количество цветов.Задача о двухшаговой раскраске исследуется применительно к графам решетки. Рассмотрены четыре типа решеток: треугольная, квадратная, шестиугольная и восьмиугольная. Показано, что в общем случае для оптимальной двухшаговой раскраски графов шестиугольной и восьмиугольной решетки требуется 4 цвета, приводятся полиномиальные алгоритмы получения такой раскраски. Для графа квадратной решетки, в котором максимальная степень вершины равна 3, может потребоваться 4 или 5 цветов для двухшаговой раскраски. В данной работе предложен алгоритм поиска с возвратом для этого случая. Для графов треугольной решетки представлен линейный относительно количества вершин алгоритм двухшаговой раскраски в 7 цветов, показано, что раскраска будет всегда корректной. Если максимальная степень вершины равна 6, решение будет оптимальным.

In this article, we consider the NP-hard problem of the two-step colouring of a 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. The optimum two-step colouring is one that uses the minimum possible number of colours.The two-step colouring problem is studied in application to grid graphs. We consider four types of grids: triangular, square, hexagonal, and octogonal. We show that the optimum two-step colouring of hexagonal and octogonal grid graphs requires 4 colours in the general case. We formulate the polynomial algorithms for such a colouring. A square grid graph with the maximum vertex degree equal to 3 requires 4 or 5 colours for a two-step colouring. In the paper, we suggest the backtracking algorithm for this case. Also, we present the algorithm, which works in linear time relative to the number of vertices, for the two-step colouring in 7 colours of a triangular grid graph and show that this colouring is always correct. If the maximum vertex degree equals 6, the solution is optimum.

двухшаговая раскраска графаграф решеткиграф треугольной решеткиграф квадратной решеткиграф шестиугольной решеткиграф восьмиугольной решеткиtwo-step graph colouringgrid graphtriangular grid graphsquare grid graphhexagonal grid graphoctogonal grid graphReferencesS. V. Korsakov, A. V. Smirnov, and V. A. Sokolov, “Principles of Organizing the Interoperability of Equipollent Nodes in a Wireless Mesh-Network with Time Division Multiple Access”, Automatic Control and Computer Sciences, vol. 50, no. 6, pp. 415-422, 2016. doi: 10.3103/S0146411616060031.S. V. Korsakov, A. V. Smirnov, and V. A. Sokolov, “Principles of Organizing the Interoperability of Equipollent Nodes in a Wireless Mesh-Network with Time Division Multiple Access”, Automatic Control and Computer Sciences, vol. 50, no. 6, pp. 415-422, 2016. doi: 10.3103/S0146411616060031.F. Harary, Graph theory. Addison-Wesley Pub. Co., 1969.F. Harary, Graph theory. Addison-Wesley Pub. Co., 1969.N. S. Medvedeva and A. V. Smirnov, “NP-Completeness and One Polynomial Subclass of the Two-Step Graph Colouring Problem”, Automatic Control and Computer Sciences, vol. 54, no. 7, pp. 685-696, 2020. doi: 10.3103/S0146411620070159.N. S. Medvedeva and A. V. Smirnov, “NP-Completeness and One Polynomial Subclass of the Two-Step Graph Colouring Problem”, Automatic Control and Computer Sciences, vol. 54, no. 7, pp. 685-696, 2020. doi: 10.3103/S0146411620070159.N. S. Medvedeva and A. V. Smirnov, “Dvukhshagovaya raskraska pryamougol’nogo grafa reshetki”, in Zametki po informatike i matematike, vol. 11, Yaroslavl: YSU, 2019, pp. 131-138.N. S. Medvedeva and A. V. Smirnov, “Dvukhshagovaya raskraska pryamougol’nogo grafa reshetki”, in Zametki po informatike i matematike, vol. 11, Yaroslavl: YSU, 2019, pp. 131-138.A. N. Kolmogorov, “Parkety iz pravil’nykh mnogougol’nikov”, Kvant, no. 3, pp. 24-27, 1970.A. N. Kolmogorov, “Parkety iz pravil’nykh mnogougol’nikov”, Kvant, no. 3, pp. 24-27, 1970.C. Umans and W. Lenhart, “Hamiltonian Cycles in Solid Grid Graphs”, in Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 1997, pp. 496-505. doi: 10.1109/SFCS.1997. 646138.C. Umans and W. Lenhart, “Hamiltonian Cycles in Solid Grid Graphs”, in Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 1997, pp. 496-505. doi: 10.1109/SFCS.1997. 646138.A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter, “Hamilton Paths in Grid Graphs”, SIAM Journal on Computing, vol. 11, no. 4, pp. 676-686, 1982. doi: 10.1137/0211056.A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter, “Hamilton Paths in Grid Graphs”, SIAM Journal on Computing, vol. 11, no. 4, pp. 676-686, 1982. doi: 10.1137/0211056.V. S. Gordon, Y. L. Orlovich, and F. Werner, “Hamiltonian properties of triangular grid graphs”, Discrete Mathematics, vol. 308, no. 24, pp. 6166-6188, 2007. doi: 10.1016/j.disc.2007.11.040.V. S. Gordon, Y. L. Orlovich, and F. Werner, “Hamiltonian properties of triangular grid graphs”, Discrete Mathematics, vol. 308, no. 24, pp. 6166-6188, 2007. doi: 10.1016/j.disc.2007.11.040.K. Islam, H. Meijer, Y. Nu´ n˜ ez, D. Rappaport, and H. Xiao, “Hamilton Circuits in Hexagonal Grid Graphs”, in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), 2007, pp. 85-88.K. Islam, H. Meijer, Y. Nu´ n˜ ez, D. Rappaport, and H. Xiao, “Hamilton Circuits in Hexagonal Grid Graphs”, in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), 2007, pp. 85-88.F. Keshavarz-Kohjerdi and A. Bagheri, “An efficient parallel algorithm for the longest path problem in meshes”, The Journal of Supercomputing, vol. 65, no. 2, pp. 723-741, 2013. doi: 10.1007/s11227-012- 0852-0.F. Keshavarz-Kohjerdi and A. Bagheri, “An efficient parallel algorithm for the longest path problem in meshes”, The Journal of Supercomputing, vol. 65, no. 2, pp. 723-741, 2013. doi: 10.1007/s11227-012- 0852-0.

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