Для цитирования:
Разумовский П. В., Абросимов М. Б. Построение цветных графов без проверки на изоморфизм // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2021. Т. 21, вып. 2. С. 267-277. DOI: 10.18500/1816-9791-2021-21-2-267-277, EDN: TRQZAM
Построение цветных графов без проверки на изоморфизм
В работе рассматриваются графы, вершины или ребра которых раскрашены в заданное количество цветов — вершинные и реберные раскраски. Изучение раскрасок графов началось с середины XIX в., однако основное внимание уделяется правильным раскраскам, в которых накладывается ограничение, что цвета смежных вершин или ребер должны быть различными. В данной работе рассматриваются раскраски графов без каких-либо ограничений. Исследуется задача генерации всех неизоморфных вершинных и реберных k-раскрасок заданного графа без непосредственной проверки на изоморфизм. Задача о нахождении неизоморфных реберных k-раскрасок сводится к задаче построения всех вершинных k-раскрасок графа. В основе методов генерации графов без непосредственной проверки на изоморфизм лежит метод канонических представителей. Идея метода состоит в том, что предлагается способ кодирования графов и выбирается некоторое правило, по которому из всех изоморфных графов один граф объявляется каноническим. Строятся все коды и из них оставляются только канонические. Часто в качестве канонического выбирается представитель с наибольшим или наименьшим кодом. На практике порождение всех кодов требует больших вычислительных ресурсов, поэтому используются различные методы оптимизации перебора. В работе предлагаются два алгоритма решения задачи генерации вершинных k-раскрасок без проверки на изоморфизм методом МакКея и методом Рида – Фараджева. Производится сравнение разработанных алгоритмов генерации раскрасок на двух классах графов — цепях и циклах. Вычислительные эксперименты показывают, что для цепей и циклов алгоритм, построенный на основе метода Рида – Фараджева, работает быстрее.
- McKay B. D., Piperno A. Practical graph isomorphism, II // Journal of Symbolic Computation. 2013. Vol. 60. P. 94–112. https://doi.org/10.1016/j.jsc.2013.09.003
- McKay B. D., Piperno A. Nauty and Traces: Graph canonical labeling and automorphism group computation. URL: https://pallini.di.uniroma1.it/ (дата обращения: 01.05.2020).
- Meringer M. Fast generation of regular graphs and construction of cages // Journal of Graph Theory. 1999. Vol. 30. P. 137–146. https://doi.org/10.1002/(SICI)1097- 0118(199902)30:2<_x0031_37:_x003a_AID-JGT7>3.0.CO;2-G
- Brinkmann G., Goedgebeur J., McKay B. D. Generation of cubic graphs // Discrete Mathematics and Theoretical Computer Science, DMTCS. 2011. Vol. 13, no. 2. P. 69–79.
- Brinkmann G. Isomorphism rejection in structure generation programs // Discrete Mathematical Chemistry / eds. P. Hansen, P. W. Fowler and M. Zheng. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2000. Vol. 51. P. 25–38.
- Hayes J. P. A graph model for fault-tolerant computing system // IEEE Transactions on Computers. 1976. Vol. C-25, no. 9. P. 875–884. https://doi.org/10.1109/TC.1976.1674712
- Jensen T., Toft B. Graph Coloring Problems. Wiley-Interscience, 1994. 320 p.
- Topics in Chromatic Graph Theory / ed. by L. W. Beineke, R. J. Wilson. Cambridge : Cambridge University Press, 2015. 370 p. (Encyclopedia of Mathematics and its Applications 156). https://doi.org/10.1017/CBO9781139519793
- Lewis R. M. R. A Guide to Graph Colouring. Algorithms and Applications. Springer, Cham, 2016. 253 p. https://doi.org/10.1007/978-3-319-25730-3
- Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. Москва : Наука, 1997. 368 с.
- Харари Ф. Теория графов. Москва : Мир, 1973. 296 с.
- Абросимов М. Б., Разумовский П. В. О генерации неизоморфных вершинных k-раскрасок // Прикладная дискретная математика. Приложение. 2017. № 10. С. 136–138. https://doi.org/10.17223/2226308X/10/53
- Разумовский П. В., Абросимов М. Б. О генерации неизоморфных k-раскрасок методом МакКея // Компьютерные науки и информационные технологии : материалы междунар. науч. конф. Саратов : ИЦ «Наука», 2018. С. 318–320.
- Абросимов М. Б., Разумовский П. В. О генерации неизоморфных раскрасок методом Рида – Фараджева // Прикладная дискретная математика. Приложение. 2019. № 12. С. 173–176. https://doi.org/10.17223/2226308X/12/48
- 1764 просмотра