Образец для цитирования:

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


Опубликована онлайн: 
02.03.2020
Язык публикации: 
русский
Рубрика: 
УДК: 
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).

Полный текст в формате PDF: