Двухшаговая раскраска графов решетки различных типов
https://doi.org/10.18255/1818-1015-2022-3-166-180
Аннотация
В данной статье рассматривается NP-трудная задача о двухшаговой раскраске графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Оптимальной считается двухшаговая раскраска в минимально возможное количество цветов.Задача о двухшаговой раскраске исследуется применительно к графам решетки. Рассмотрены четыре типа решеток: треугольная, квадратная, шестиугольная и восьмиугольная. Показано, что в общем случае для оптимальной двухшаговой раскраски графов шестиугольной и восьмиугольной решетки требуется 4 цвета, приводятся полиномиальные алгоритмы получения такой раскраски. Для графа квадратной решетки, в котором максимальная степень вершины равна 3, может потребоваться 4 или 5 цветов для двухшаговой раскраски. В данной работе предложен алгоритм поиска с возвратом для этого случая. Для графов треугольной решетки представлен линейный относительно количества вершин алгоритм двухшаговой раскраски в 7 цветов, показано, что раскраска будет всегда корректной. Если максимальная степень вершины равна 6, решение будет оптимальным.
Об авторе
Александр Валерьевич Смирнов
Ярославский государственный университет им. П. Г. Демидова
Россия
Россия
Список литературы
1. 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.
2. F. Harary, Graph theory. Addison-Wesley Pub. Co., 1969.
3. 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.
4. 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.
5. A. N. Kolmogorov, “Parkety iz pravil’nykh mnogougol’nikov”, Kvant, no. 3, pp. 24-27, 1970.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
Рецензия
Для цитирования:
Смирнов А.В. Двухшаговая раскраска графов решетки различных типов. Моделирование и анализ информационных систем. 2022;29(3):166-180. https://doi.org/10.18255/1818-1015-2022-3-166-180
For citation:
Smirnov A.V. Two-Step Colouring of Grid Graphs of Different Types. Modeling and Analysis of Information Systems. 2022;29(3):166-180. (In Russ.) https://doi.org/10.18255/1818-1015-2022-3-166-180
Просмотров:
373
Послать статью по эл. почте 