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

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

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


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

Абросимов М. Б., Судани Х. Х., Лобов А. А. Построение минимальных рёберных расширений графа без проверки на изоморфизм // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2020. Т. 20, вып. 1. С. 105-115. DOI: 10.18500/1816-9791-2020-20-1-105-115

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

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

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

В 1993 г. Frank Harary и John P. Hayes предложили основанную на графах модель для исследования отказов связей элементов дискретных систем. Технической системе сопоставляется граф. Элементам системы соответствуют вершины графа, а связям между элементами — рёбра или дуги графа. Под отказом связи между элементами системы понимается удаление из графа системы соответствующего ребра (или дуги). Формализацией отказоустойчивой реализации системы является расширение графа. Граф G∗ называется рёберным k-расширением графа G, если после удаления любых k рёбер из графа G∗ граф G вкладывается в получившийся граф. Рёберное k-расширение n-вершинного графа G называется минимальным, если оно имеет n вершин и минимальное число рёбер среди всех рёберных k-расширений графа G с n вершинами. В работе предлагается алгоритм построения всех неизоморфных минимальных рёберных k-расширений заданного графа без проверки на изоморфизм методами канонических представителей и Рида – Фараджева.

Список источников: 
  1. Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Computers. 1976. Vol. C-25, № 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. Абросимов М. Б., Камил И. А. К., Лобов А. А. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2019. Т. 19, вып. 4. С. 479–486. DOI: https://doi.org/10.18500/1816-9791-2019-19-4-479-486
  7. Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск : ИД Том. гос. ун-та, 2000. С. 59–64.
  8. Абросимов М. Б. Минимальные расширения 4-, 5-, 6- и 7-вершинных графов. Сарат. гос. ун-т. Саратов, 2000. 26 с. ; Деп. в ВИНИТИ 06.09.2000, № 2352-В00.
  9. Brinkmann G. Isomorphism rejection in structure generation programs // Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2000. Vol. 51. P. 25–38. DOI: https://doi.org/10.1090/dimacs/051/03
  10. McKay B. D. Graph formats. URL: http://users.cecs.anu.edu.au/bdm/data/formats.html (дата обращения: 01.05.2019).
  11. 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
  12. Поволжский региональный центр новых информационных технологий : [сайт]. URL: http://prcnit.sgu.ru (дата обращения: 01.05.2019).
  13. Мир графов. URL: http://graphworld.ru (дата обращения: 01.05.2019).
Поступила в редакцию: 
20.10.2019
Принята к публикации: 
02.12.2019
Опубликована: 
02.03.2020