Алгоритм оптимальной раскраски квадратных (0,1)-матриц

Igor V. Olemskoy; Oxana S. Firyulina

doi:10.21638/11701/spbu10.2023.108

Authors

Igor V. Olemskoy St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation https://orcid.org/0000-0001-8897-9898
Oxana S. Firyulina St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation https://orcid.org/0000-0002-9457-6670

DOI:

https://doi.org/10.21638/11701/spbu10.2023.108

Abstract

The paper proposes an algorithm for solving the configuration-optimization coloring problem for square (0,1)-matrices, which is based on the method of selection their structural features. The algorithm belongs to the method's of backtracking, however, the construction of the optimal solution is carried out among the options that provide a certain configuration, due to which the size of the search tree is significantly reduced. A detailed scheme of its operation is given, and the effectiveness of the solution is demonstrated by the example of calculating the chromatic number of a specific (0,1)-matrix.

Keywords:

graph coloring, chromatic number, (0,1)-matrix

Downloads

Download data is not yet available.

References

Литература

Олемской И. В., Хитров Г. М., Виташевская И. С. О некоторых инвариантах квадратных (0,1)-матриц // Вестник Санкт-Петербургского университета. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2007. Вып. 1. С. 38-45.

Фирюлина О. С. Вычисление неплотности квадратных (0,1)-матриц // Сб. трудов XLIII Междунар. науч. конференции аспирантов и студентов "Процессы управления и устойчивость". СПб.: Изд-во С.-Петерб. ун-та, 2012. С. 55-60.

Курош А. Г. Курс высшей алгебры: учебник для вузов. СПб.: Лань, 2021. 432 с.

Олемской И. В. Алгоритм выделения структурных особенностей // Николай Ефимович Кирин: cб. ст.; под ред. В. В. Жука, В. Ф. Кузютина. СПб.: АССПИН, 2003. С. 234-251.

Олемской И. В. Методы интегрирования систем структурно разделенных дифференциальных уравнений. СПб.: Изд-во С.-Петерб. ун-та, 2009. 180 с.

Олемской И. В., Фирюлина О. С. Алгоритм поиска наибольшего независимого множества // Вестник Санкт-Петербургского университета. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2014. Вып. 1. С. 79-89.

Новиков Ф. А. Дискретная математика для программистов: учебник для вузов. СПб.: Питер, 2009. 384 с.

Фирюлина О. С. Нахождение всех максимальных независимых множеств неориентированного графа // Вестник Санкт-Петербургского университета. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2013. Вып. 1. С. 63-69.

References

Olemskoy I. V., Hitrov G. M., Vitashevskaya I. S. O nekotorykh invariantakh kvadratnykh (0,1)-matrits [On some invariants of square (0,1)-matrices]. Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Sciences. Control Processes, 2007, iss. 1, pp. 38-45. (In Russian)

Firyulina O. S. Vychislenie neplotnosti kvadratnykh (0,1)-matric [Calculation of the nondensity of square (0,1)-matrices]. Proceedings of the XLIII International Scientific Conference of postgraduates and students "Control processes and stability". St. Petersburg, St. Petersburg University Press, 2012, pp. 55-60. (In Russian)

Kurosh A. G. Kurs vysshey algebry. Uchebnik dlya vuzov [ Higher algebra course. A textbook for universities]. St. Petersburg, Lan' Publ., 2021, 432 p. (In Russian)

Olemskoy I. V. Algoritm vydeleniya structurnykh osobennostey [Algorithm for the identification of structural features]. Nikolay Efimovich Kirin. Сollection of articles. St. Petersburg, ASSPIN Publ., 2003, pp. 234-251. (In Russian)

Olemskoy I. V. Metody integrirovaniya sistem structurno razdelennykh differentsial'nykh uravneniy [ Methods of integration of systems of structurally separated differential equations ]. St. Petersburg, St. Petersburg University Press, 2009, 180 p. (In Russian)

Olemskoy I. V., Firyulina O. S. Algoritm poiska naibol'shego nezavisimogo mnozhestva [Algorithm for finding the maximum independent set]. Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Sciences. Control Processes, 2014, iss. 1, pp. 79-89. (In Russian)

Novikov F. A. Diskretnaya matematika dlya programmistov. Uchebnik dlya vuzov [Discrete mathematics for programmers. A textbook for universities]. St. Petersburg, Piter Publ., 2009, 384 p. (In Russian)

Firyulina O. S. Nakhozhdenie vsekh maksimal'nykh nezavisimykh mnozhestv neorientirovannogo grafa [Finding all maximal independent sets of an undirected graph]. Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Sciences. Control Processes, 2013, iss. 1, pp. 63-69. (In Russian)