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

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

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


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

Абросимов М. Б., Камил Ихаб А. К., Лобов А. А. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2019. Т. 19, вып. 4. С. 479-486. DOI: 10.18500/1816-9791-2019-19-4-479-486

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

Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей

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

В 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).
Поступила в редакцию: 
20.05.2019
Принята к публикации: 
30.06.2019
Опубликована: 
02.12.2019