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

Игорь Владимирович Олемской; Оксана Сергеевна Фирюлина

doi:10.21638/11701/spbu10.2023.108

Авторы

Игорь Владимирович Олемской Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9
Оксана Сергеевна Фирюлина Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9 https://orcid.org/0000-0002-9457-6670

DOI:

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

Аннотация

Предложен алгоритм решения конфигурационно-оптимизационной задачи о раскраске для квадратных (0,1)-матриц, который базируется на способе выделения их структурных особенностей. Алгоритм относится к классу переборных, тем не менее построение оптимального решения осуществляется среди вариантов, которые обеспечивают наличие определенной конфигурации, за счет чего существенно сокращается размер дерева поиска. Приведена подробная схема его работы, а также продемонстрирована эффективность решения на примере вычислений хроматического числа конкретной (0,1)-матрицы.

Ключевые слова:

раскраска графа, хроматическое число, (0,1)-матрица

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

Литература

Олемской И. В., Хитров Г. М., Виташевская И. С. О некоторых инвариантах квадратных (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)