Для цитирования:
Абросимов М. Б., Судани Х. Х., Лобов А. А. Построение минимальных рёберных расширений графа без проверки на изоморфизм // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2020. Т. 20, вып. 1. С. 105-115. DOI: 10.18500/1816-9791-2020-20-1-105-115, EDN: PXDRGJ
Построение минимальных рёберных расширений графа без проверки на изоморфизм
В 1993 г. Frank Harary и John P. Hayes предложили основанную на графах модель для исследования отказов связей элементов дискретных систем. Технической системе сопоставляется граф. Элементам системы соответствуют вершины графа, а связям между элементами — рёбра или дуги графа. Под отказом связи между элементами системы понимается удаление из графа системы соответствующего ребра (или дуги). Формализацией отказоустойчивой реализации системы является расширение графа. Граф G∗ называется рёберным k-расширением графа G, если после удаления любых k рёбер из графа G∗ граф G вкладывается в получившийся граф. Рёберное k-расширение n-вершинного графа G называется минимальным, если оно имеет n вершин и минимальное число рёбер среди всех рёберных k-расширений графа G с n вершинами. В работе предлагается алгоритм построения всех неизоморфных минимальных рёберных k-расширений заданного графа без проверки на изоморфизм методами канонических представителей и Рида – Фараджева.
- 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
- 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
- Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Сарат. ун-та, 2012. 192 с.
- Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 1997. 368 с.
- Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88, вып. 5. С. 643–650. DOI: https://doi.org/10.4213/mzm8403
- Абросимов М. Б., Камил И. А. К., Лобов А. А. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2019. Т. 19, вып. 4. С. 479–486. DOI: https://doi.org/10.18500/1816-9791-2019-19-4-479-486
- Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск : ИД Том. гос. ун-та, 2000. С. 59–64.
- Абросимов М. Б. Минимальные расширения 4-, 5-, 6- и 7-вершинных графов. Сарат. гос. ун-т. Саратов, 2000. 26 с. ; Деп. в ВИНИТИ 06.09.2000, № 2352-В00.
- 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
- McKay B. D. Graph formats. URL: http://users.cecs.anu.edu.au/bdm/data/formats.html (дата обращения: 01.05.2019).
- 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
- Поволжский региональный центр новых информационных технологий : [сайт]. URL: http://prcnit.sgu.ru (дата обращения: 01.05.2019).
- Мир графов. URL: http://graphworld.ru (дата обращения: 01.05.2019).
- 1313 просмотров