Образец для цитирования:
Абросимов М. Б., Камил И. А., Лобов А. А. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2019. Т. 19, вып. 4. С. 479-486. DOI: https://doi.org/10.18500/1816-9791-2019-19-4-479-486
Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей
В 1976 г. John P. Hayes предложил основанную на графах модель для исследования отказоустойчивости дискретных систем. Технической системе сопоставляется граф. Элементам системы соответствуют вершины графа, а связям между элементами — рёбра или дуги графа. Под отказом элемента системы понимается удаление из графа системы соответствующей вершины вместе со всеми её рёбрами. Формализацией отказоустойчивой реализации системы является расширение графа. Граф G* называется вершинным k-расширением графа G, если после удаления любых k вершин из графа G* граф G вкладывается в получившийся граф. Вершинное k-расширение графа G называется минимальным, если оно имеет наименьшее число вершин и рёбер среди всех вершинных k-расширений графа G. В работе предлагается алгоритм построения всех неизоморфных минимальных вершинных k-расширений заданного графа без проверки на изоморфизм методом канонических представителей.
1. Hayes J. P. A graph model for fault-tolerant computing system // IEEE Transactions on Computers, 1976. Vol. C-25, iss. 9. P. 875–884. DOI: https://doi.org/10.1109/ TC.1976.1674712
2. Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23. P. 135– 142. DOI: https://doi.org/10.1002/net.3230230207
3. Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Сарат. ун-та, 2012. 192 с.
4. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 1997. 368 с.
5. Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88, вып. 5. С. 643–650. DOI: https://doi.org/10.4213/mzm8403
6. Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур : докл. Третьей Всерос. конф. с междунар. участием. Томск, 2000. С. 59–64.
7. Абросимов М. Б. Минимальные расширения 4-, 5-, 6- и 7-вершинных графов. Сарат. гос. ун-т. Саратов, 2000. 26 с.; Деп. в ВИНИТИ 06.09.2000, № 2352-В00.
8. Brinkmann G. Isomorphism rejection in structure generation programs // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2000. Vol. 51. P. 25–38. DOI: https://doi.org/10.1090/dimacs/051/03
9. McKay B. D., Piperno A. Practical Graph Isomorphism, II // Journal of Symbolic Computation. 2014. Vol. 60. P. 94–112. DOI: https://doi.org/10.1016/j.jsc.2013.09.003
10. Поволжский региональный центр новых информационных технологий. URL: http://prcnit.sgu.ru (дата обращения: 01.05.2019).
11. Мир графов. URL: http://graphworld.ru (дата обращения: 01.05.2019).
