Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Разумовский П. В., Абросимов М. Б. Построение цветных графов без проверки на изоморфизм // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2021. Т. 21, вып. 2. С. 267-277. DOI: 10.18500/1816-9791-2021-21-2-267-277, EDN: TRQZAM

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
31.05.2021
Полный текст:
(downloads: 1360)
Язык публикации: 
русский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.17
EDN: 
TRQZAM

Построение цветных графов без проверки на изоморфизм

Авторы: 
Разумовский Петр Владимирович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Абросимов Михаил Борисович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

В работе рассматриваются графы, вершины или ребра которых раскрашены в заданное количество цветов — вершинные и реберные раскраски. Изучение раскрасок графов началось с середины XIX в., однако основное внимание уделяется правильным раскраскам, в которых накладывается ограничение, что цвета смежных вершин или ребер должны быть различными. В данной работе рассматриваются раскраски графов без каких-либо ограничений. Исследуется задача генерации всех неизоморфных вершинных и реберных k-раскрасок заданного графа без непосредственной проверки на изоморфизм. Задача о нахождении неизоморфных реберных k-раскрасок сводится к задаче построения всех вершинных k-раскрасок графа. В основе методов генерации графов без непосредственной проверки на изоморфизм лежит метод канонических представителей. Идея метода состоит в том, что предлагается способ кодирования графов и выбирается некоторое правило, по которому из всех изоморфных графов один граф объявляется каноническим. Строятся все коды и из них оставляются только канонические. Часто в качестве канонического выбирается представитель с наибольшим или наименьшим кодом. На практике порождение всех кодов требует больших вычислительных ресурсов, поэтому используются различные методы оптимизации перебора. В работе предлагаются два алгоритма решения задачи генерации вершинных k-раскрасок без проверки на изоморфизм методом МакКея и методом Рида – Фараджева. Производится сравнение разработанных алгоритмов генерации раскрасок на двух классах графов — цепях и циклах. Вычислительные эксперименты показывают, что для цепей и циклов алгоритм, построенный на основе метода Рида – Фараджева, работает быстрее. 

Благодарности: 
Работа выполнена при поддержке Минобрнауки России в рамках выполнения государственного задания (проект № FSRR-2020-0006).
Список источников: 
  1. 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
  2. McKay B. D., Piperno A. Nauty and Traces: Graph canonical labeling and automorphism group computation. URL: https://pallini.di.uniroma1.it/ (дата обращения: 01.05.2020).
  3. 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
  4. 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.
  5. 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.
  6. 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
  7. Jensen T., Toft B. Graph Coloring Problems. Wiley-Interscience, 1994. 320 p.
  8. 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
  9. 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
  10. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. Москва : Наука, 1997. 368 с.
  11. Харари Ф. Теория графов. Москва : Мир, 1973. 296 с.
  12. Абросимов М. Б., Разумовский П. В. О генерации неизоморфных вершинных k-раскрасок // Прикладная дискретная математика. Приложение. 2017. № 10. С. 136–138. https://doi.org/10.17223/2226308X/10/53
  13. Разумовский П. В., Абросимов М. Б. О генерации неизоморфных k-раскрасок методом МакКея // Компьютерные науки и информационные технологии : материалы междунар. науч. конф. Саратов : ИЦ «Наука», 2018. С. 318–320.
  14.  Абросимов М. Б., Разумовский П. В. О генерации неизоморфных раскрасок методом Рида – Фараджева // Прикладная дискретная математика. Приложение. 2019. № 12. С. 173–176. https://doi.org/10.17223/2226308X/12/48
Поступила в редакцию: 
10.06.2020
Принята к публикации: 
12.10.2020
Опубликована: 
31.05.2021